CSC301.01 2015F, Class 24: Graph ADTs

Overview

Preliminaries

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.

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.

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.)

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

    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
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

List
neighbors(Graph graph, Vertex v)
- Iterator 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