ISE 390 -- Programming Challenges -- Week 9 Notes

This Weeks Goals: 

	To review the basic principles of graph algorithms and data
		structures, specifically path based problems such as
		breadth-first-search and shortest path.


Breadth-First Search

	BFS is essentially the same idea/algorithm as DFS, except that
	the next node to explore is pulled off a queue instead of a stack.
	Thus the nodes are accessed in a first-in-first-out order.

	BFS builds a tree from the root node representing the minimum number
	of edges it takes to get from the root to every other vertex.

	Note that this gives the shortest path in the graph *only* if
	the graphs unweighted.

Applications of BFS/DFS Search 

	Note that breadth-first search (BFS) will also work for some of
	these, but not others.  As we will see, BFS is appropriate (1)
	if all we care about is visiting all vertices and edges of the
	graph, and don't care about order, or (2) we are interested in
	shortest paths on unweighted graphs.

Important Graph Algorithms

(1) Shortest paths in unweighted graphs -- do BFS

(2) Shortest paths in weighted graphs -- BFS does not work.
	Do Dijkstra's algorithm or Floyd-Warshall

ShortestPath-Dijkstra($G,s,t$) 
	$known = \{s\}$ 
	for $i=1$ to $n$, $dist[i]=\infty$ 
	for each edge $(s, v)$, $dist[v]=w(s, v)$ 
	$last=s$ 
	while ($last \neq t$) 
		select $v_{next}$, the unknown vertex minimizing $dist[v]$ 
		for each edge $(v_{next},x)$,
			$dist[x]=\min[dist[x], dist[v_{next}]+w(v_{next},x)]$ 
		$last=v_{next}$ 
		$known = known \cup \{v_{next}\}$


(2) Topological sorting -- order the vertices from 1 to n such that
all directed edges go from left to right; thus we can process each
node before any of its predecessors.

	Topological sort algorithm: any node of indegree 0 can be first;
	deleting it must leave another such node.

(3) Strongly connected components -- partition the graph into chunks
	such that there are directed paths between all pairs of vertices
	within a chunk.

	Strong components algorithm -- use DFS to find a directed
		cycle in the graph (any back edge plus the down path
		in the DFS tree gives a cycle).  All vertices in this
		cycle are in a component.  Shrink these to a vertex
		and repeat.

(4) Minimum spanning trees -- connect the vertices by the smallest
	amount of wire, roadway, or edge weight.

	The two main algorithms are Kruskal's and Prim's

Prim-MST(G) 
	Select an arbitrary vertex $s$ to start the tree from. 
	While (there are still nontree vertices) 
		Select the edge of minimum weight between a tree and
			nontree vertex 
		Add the selected edge and vertex to the tree $T_{prim}$.



The following code fragments have been lifted from Sedgewick's "Algorithms
in C++" book:



/* Read a graph into an adjacency list */

struct node
  { int v; struct node *next; };
int V, E;
struct node *adj[maxV], *z;
 
void adjlist()
  {
    int j, x, y; struct node *t;
    cin >> V >> E;
    z = new node;  z->next = z;
    for (j = 1; j <= V; j++) adj[j] = z;
    for (j = 1; j <= E; j++)
      {
        cin >> v1 >> v2;
        x = index(v1); y = index(v2);
        t = new node; 
          t->v = x; t->next = adj[y]; adj[y] = t;
        t = new node;
          t->v = y; t->next = adj[x]; adj[x] = t;
      }
  }

Queue queue(maxV);
void visit(int k) // BFS, adjacency lists
  {
    struct node *t;
    queue.put(k);
    while (!queue.empty())
      {
        k = queue.get(); val[k] = ++id;
        for (t = adj[k]; t != z; t = t->next)
          if (val[t->v] == unseen) 
            { queue.put(t->v); val[t->v] = -1; }
      }
  }
 

/* BFS with adjacency lists */

void search()
  {
    int k;
    queue.init()
    for (k = 1; k <= V; k++) val[k] = unseen;
    for (k = 1; k <= V; k++) 
      if (val[k] == unseen) visit(k);
  }
 
/* Floyd-Warshall Algorithm to find all-pairs shortest path */

for (y = 1; y <= V; y++)
 for (x = 1; x <= V; x++) 
  if (a[x][y])
   for (j = 1; j <= V; j++) 
    if (a[y][j] > 0)
     if (!a[x][j] || (a[x][y]+a[y][j] < a[x][j]))
      a[x][j] = a[x][y] + a[y][j];



Assigned Problems:

157 -- Find the shortest path in a transportation graph.  Some syntactic
	complications since the graph is specified in a non-standard
	fashion (as the union of "lines")

196 -- Implement a simple spreadsheet program.  Topological sorting
	of the formula cell graph is necessary to do it "right", although
	there may be a simple hack based on knowing the maximum number of
	cells and the acyclicity of the graph.

336 -- Find the nodes reachable in a given number of hops from the source.
	Is this a weighted or unweighted graph, and what does that mean?

314 -- Plot the motion of the robot where it costs time to turn and
	there are obstacles on the grid.  How do we modify Dijkstra's
	algorithm for turn costs?

318 -- Given a graph of domino paths, figure out where the last domino
	will fall.   This is a BFS/shortest path type problem, where the
	goal is to visit every edge in a reasonable order.