CSC152 2006S, Class 51: Graphs

Admin:
* Those of you who have studied this topic in combinatorics should not volunteer too much.
* Reminder: Visitor on Friday.
* EC for attending talk Thursday at 7:30 p.m.
* EC for attending baseball game at 2ish tomorrow
* EC for attending paper-sculpture-dance thing on May 11
* Double EC for setting Danny Zamora on fire (THIS IS A JOKE, DON'T ARREST FOR TERRORISM) (AND BUSH SUCKS)
* EC for Orchestra Concert on Sunday
* EC for attending art show
* EC for attending Emanate concert if they ever get their act together and decide upon a time
* Are there questions on the exam?

Overview:
* Introduction: Modeling in CS.
* One Modeling ADT: The Graph.
* Some Graph Problems.
* A Graph ADT.
* Solving the Reachability Problem.
* Coding the Solution.

The kind of picture we draw for lots of problems should be
represented as an ADT.  We call it a "Graph".

* The "places" we call "vertices" (each one is a vertex) (some call them vertexes)
* The connections between places we call "edges" (some folks call them edgi)
* Edges can be directed (one-direction) or undirected (two-direction)
* Edges may have an associated value which we call the "weight" (or cost)

General version of "Get Ian A home cheap": Shortest path
* Given a weighted, directed, graph, and two vertices, source and destination
* Find the sequence of edges that connects source to destination
* Which has the lowest total sum of edge weights

Weightless version of shortest path: Reachability
* Given a directed graph and two vertices, source and destiation,
* Determine whether there is a path from source to destination

The seven bridges of some place Kings town (Koenigsburg)
* Can you cross all of the bridges and return to your starting point?
* In general: Can you visit all of the vertices exactly once and return to your starting point?
* Sam thinks that there is no known efficient solution to this problem.

Variant of "cycle": Traveling Salescritter Problem
* In a weighted, directed graph, find the smallest cycle
* No known efficient solution

In order to code any algorithms we develop, we must have a
graph ADT.

What methods belong in that ADT?  (Suppose weighted and directed.)

* makeEdge(Vertex source, Vertex target, int weight)
  * Simplifying assumption: Use integers to represent vertices
  * makeEdge(int source, int target, int weight)
* removeEdge(int source, int target)

* isEdge(int source, int target)
* Iterator<Integer> getSources(int vertex)
* Iterator<Integer> getTargets(int vertex)
* int weightOf(int source, int target)

* compare weight of edges
  int cheapestEdge(int source)

How do we deal with the "creation" of vertices?
* When someone refers to a vertex, create it.
* Require the client to specify the vertices in advance [0..n-1]

Let's write 

boolean reachable(WDG g, int source, int target)
* For each unmarked successor that follows source
  * Mark the successor
  * If successor = target, return true
  * If not, recurse
* If we ran through all the successors, return false

* Problem: Might recursive infinitely