CSC301.01 2015F, Class 24: Graph ADTs
=====================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Designing a graph ADT.
* Different perspectives on graph ADTs.
* Building graphs.
* Accessing values.
* Implementing graphs (if time).

Preliminaries
-------------

### Admin

* Reminder!  My goal is often as much *process* as *product*.  I care
  about not just what you come up with, but also how you compare different 
  approaches.

### Upcoming Work

* HW (Due Monday): 5-1, 5-2, 5-6, 5-7, 5-13, 5-20, 5-23, 5-28

### Extra Credit

#### Academic

* Any visit to the current show in the Faulconer gallery.
* Any of the Grinnell Prize Week Activities this week.
* Conversation about Study Abroad at AIT in Hungary: Wednesday at 4:00 in 3821.
* Convocation Thursday at 11: Contesting Muhammad: Contermporary Controversies
  in Historical Perspective
* CS Extras Thursday at 4:15pm in 3821: Algorithms for Assembling the Tree
  of Life. (Plus grad school at UIowa!)
* What's the Deal with the Digital Liberal Arts?  Thursday at 4:15 in
  the D-Lab.  With Autumnal snacks!
* CS Table next Tuesday: Why is everyone so mean on the Internet?
* Sexual Misconduct at Grinnell College: Results from the 2013 and 2015
  Sexual Conduct Surveys.  1-3 pm, November 8, JRC 101.
* R.L. Stephens II events Thursday and Friday.

#### Peer Support

* Women's Soccer, Wednesday, 4 p.m. vs. UW-Platteville
* Men's Soccer, Thursday, 4 p.m. vs. Coe
* Women's Soccer, Saturday, 11 a.m. vs. Beloit (Senior day!)
* Men's Soccer, Saturday, 1:30 p.m. vs. Beloit (Senior day!)
* Halloween Day on Saturday

### Questions

Designing a graph ADT
---------------------

* Three aspects:
    * Philosophy: (e.g. "lists are collections of values that you can iterate";
      "arrays are collections of values that you can index by integer")
    * Use cases: I use lists so that I can call on on every student in the
      class at least once
    * Methods: The ways that programmers access the data.  
      Specify: Name, Parameters, Return Type, Purpose, Subtleties
* Think about
    * Building graphs
    * Accessing graphs
* Focus on the key operations; we'll build the big operations based
  on these key operations.
* You can think about directed or nondirected, weighted or unweighted
  graphs.  (Mostly, the operations will be similar.)

Different perspectives on graph ADTs
------------------------------------

* Model: Build then process vs. Build while processing
* Delete?
* Most common use cases don't involve changing the graph

Philosophy
----------

* Model connected relationships: Friendships, Heteronormative partnerings
* A collection of values with (meaningful) connections
* A collection of values in which we can find and define relationships
  with versatility

Building graphs
---------------

        typedef struct graph *Graph;

* insert(Graph graph, Vertex newVertex)
    * Option 1: Mutate the graph
    * Option 2: Return the new graph
    * What if the vertex already exists
* insert(Graph graph, Vertex source, Array<Vertex> sinks)
    * May be more complicated if the vertex is already there
    * Doesn't make it easy to include weights
* insertEdge(Graph graph, Vertex source, Vertex target, int weight)
    * Option 1: Mutate the graph
    * Option 2: Return the new graph
    * What if the edge already exists?
    * What if the vertex doesn't exist
* Observation: We need to be more careful about preconditions/postconditions/
  exceptions.
* For implementation issues, it is sometimes easiest to require the
  client to add all the vertices and then all the edges

Accessing values
----------------

* List<Vertex> neighbors(Graph graph, Vertex v)
    * Iterator<Vertex> neighbors(Graph graph, Vertex v)
    * processNeighbors(Graph graph, Vertex v, vertexFun vf)
* allVertices(Graph graph)
    * Similar options
* edges(Graph graph, Vertex v)
    * Similar options
* allEdges(Graph graph)
    * Similar design options
* mark(Graph graph, Vertex vertex, Symbol symbol) 
    * May not be part of graph ADT
* mark(Graph graph, Edge edge, Symbol symbol)
    * May not be part of graph ADT
* weight(Graph graph, Vertex source, Vertex target) 
    * Finds the weight of the edge from soruce to target
    * throws exception/signals error if there's not an edge

Implementing graphs (if time)
-----------------------------

* Option 1: Each vertex is a node with an array of links to other
  nodes.
* Option 2: List of vertices, List of edges
* Option 2a: Set of vertices, Set of edges
* Option 2c: Array of vertices, Array of edges
* Option 2c: Hash of vertices, Hash of edges
* Option 3: Array of vertices, each vertex stores list of 
  <neighbor/weight> pairs.