Reminders: hw3 is due Friday (written) / Saturday (program).
The hw3 turnin is now enabled, see most recent class email.
Part of Friday, and all of Monday, will be review for the
midterm exam on Wednesday.

Today we consider digraphs (directed graphs), where we may have an
edge from u to v without necessarily an edge from v to u.  We will
usually represent a Digraph with adjacency lists (usually just the
"out" edge lists).

Exercise: given adjacency list representation of digraph G, compute
   the adjacency list representation of reverse(G) (graph with same
   vertices, but all edges reversed) in linear time, O(V+E).

In digraphs we have many revised notions: indegree, outdegree,
directed paths, directed cycles, and weak versus strong connectivity.
We see that DFS and BFS still work (if we start a DFS or BFS traversal
from s, we still mark everything reachable by a directed path starting
at s, and the BFS paths are shortest).

However, the situation is a bit more complicated.  For example,
in a DFS, we now see these kinds of edges:

   * tree edges (to a child in the tree)
   * back edges (to an ancestor in the tree, closer to s)
   * forward edges (to a descendant, but not a tree edge)
   * cross edges (to an already marked non-ancestor, a "cousin")

Note "cross edges" cannot occur in undirected graphs.  It turns
out that every edge can be classified as one of these four cases,
during the DFS.  During a BFS we do not see forward edges
(unless we count parallel edges).

In particular we will consider two problems, both of which (it turns
out) can be solved as applications of DFS, in O(V+E) time:

  * Topological Sort (either detect a directed cycle, or
    order the vertices so all edges go left-to-right)
    Sketch: do DFS traversal of entire graph, then use
            "reverse post order"

  * SCC's: compute the strongly connected components
    Solution: find reverse post order in reverse(G),
       then do DFS traversals in G using that root order,
       each tree will span a single SCC in G.

Slides:
   42DirectedGraphs.pdf

Movies:
   42DemoDepthFirstSearch.mov
   42DemoKosarajuSharir.mov
   42DemoTopologicalSort.mov

Code:
   ../book/Topological.java
   ../book/KosarajuSharirSCC.java

We'll probably not get into the SCC algorithm until Friday, then
we'll go into review mode.