\documentclass[12pt]{article}

\input{cps130}

\begin{document}

\title{Graph Algorithms (16)}
\author{Michael L. Littman}
\date{October 27th, 1998}

\maketitle 

\section{TOPOLOGICAL SORT}

\subsection{Scheduling}

\ni Last year, I went to a
\href{http://www-aig.jpl.nasa.gov/public/NASA-ps97/index.html}{NASA
conference} and everyone was talking about planning (which is one of
my areas of research), and scheduling (something I know less about).

\ni Lots of applications (space-shuttle construction, science-mission
planning, communications scheduling) used the basic machinery I'm
about to describe.


\subsection{Dressing}

\ni Data available (arrow means ``must come before''):

\ul
\li socks: can't have shoes already on
\li shoes
\li shirt: can't have tie or pants already on
\li tie: can't have jacket already on
\li jacket
\li understuff: can't have pants already on
\li pants: can't have shoes or jacket already on
\el

\ni Note: shirt $\rightarrow$ jacket, understuff $\rightarrow$ shoes
already implied (transitive closure).

\ni Represent restrictions as a graph.

\subsection{Topological Sort}

\ni Fancy name.  Makes it sound hard: label nodes with depth and then
sort?

\ul
\li Take a directed acyclic graph (DAG).
\li Output a linear order of nodes such that all arrows are pointing
to the right.
\el

\ni Essentially a linear schedule so there are no conflicts during
dressing.  Example.

\ni {\bf Claim:} A (finite) DAG always has at least one node with no
incoming edges and one with no outgoing edges.  Proof by
contradiction.

\ans{Assume there is no node with no incoming edges.  That means that
we can always go back one step in the graph.  But, after doing this
$n$ times, we'll have to have repeated a node.  The path traveled is a
cycle, contradicting the assumption that we have an acyclic graph.}

\subsection{Data Structures and Notation}

\ni $G=(V,E)$ is a {\em graph\/}, with $V$ as its {\em vertices\/} (or
nodes), and $E$ as its {\em edges\/} (or links).

\ni By convention, $n = |V|$ and $m = |E|$.  What's the largest $m$
can be, assuming no edge appears more than once?

\ans{$m \le n^2$.}

\ni Often, we also have $m \ge n-1$ (connected, undirected graph).

\ni For $u \in V$, we write $\mbox{\em Adj}[u]$ to be the set of
vertices to which $u$ is directly connected (i.e., $v \in \mbox{\em
Adj}[u]$ if and only if $(u,v)\in E$ (adjacency list).

\ni Note: Matrices also useful for representing edges: $a_{u,v} = 1$
if $(u,v) \in E$ and $0$ otherwise (adjacency matrix).  If $A$ is
an adjacency matrix representing a graph $G$, which does $A^T$
represent?

\ans{A graph with all the edges reversed.}


\subsection{Topological Sort in Words}

\ni Each node gets a color.

\ul

\li White nodes haven't been dealt with yet.

\li Black nodes have been completely dealt with.

\li Gray nodes are in progress.

\el

\ni Flow:

\ul

\li Make all nodes white.

\li Pick a node $u$ to ``visit'' and make it gray.

\li Pick a child of $u$ to visit.

\li Continue until we run out of white kids.  

\li Add the last visited node to a list and backtrack.

\el

\subsection{Algorithm}

\begin{verbatim}
list<GraphVert*> * TopologicalSort( Graph G )
{
  for( unsigned int v=0; v < G.size(); v++ ) {

    G[v]->color = white;

    // make all edges G[u,v] = white; G[start,v] = white;
  }

  list<GraphVert*> * visited = new list<GraphVert*>();

  for( unsigned int v=0; v < G.size(); v++ ) {

    // G[start,v] = black;

    if( G[v]->color == white )
      Visit( v, G, visited );
  }
      
  return visited;
}

void Visit( int u, Graph G, list<GraphVert*> * visited )
{
  G[u]->color = gray;

  for( list<int>::iterator iter = G[u]->adj->begin();
       iter != G[u]->adj->end();
       iter++ )
  {
    int v = *iter;

    // G[u,v] = black;

    if( G[v]->color == white )
       Visit( v, G, visited );
  }
  
  visited->push_front( G[u] );
  G[u]->color = black;
}
\end{verbatim}


\subsection{Observations}

\ni Basically, a depth-first search of the graph (more on this later).

\ni Also related to a post-order traversal of the appropriately
defined depth-first tree.

\ni Can also define the topological sort in terms of a breadth-first
traversal.  This is actually nicer if you want to output all possible
topological sorts.


\subsection{Correctness}

\ni Algorithm terminates because {\tt Visit} only performs work on
white nodes and instantly makes the visted node non-white.  Thus,
impossible to recurse forever.

\ni Correctness proof by induction on the length of the constructed
list.

\ul

\li Inductive hypothesis: When a node is added to the list, all its
children are already in the list.  Therefore, all edges in the DAG
point to the right.

\li The first node added to the list will be one with no outgoing
edges.

\li Any node added to the list has no white kids.  In fact, it has no
gray kids, either (why?).

\ans{All the gray nodes are ancestors of the current node.  A gray kid
implies a cycle.}

\li Therefore, all its kids are black and have already been added to
the list.

\li Therefore, it's ok to add it to the front of the list.

\el

\subsection{Running Time: Standard Analysis}

\ni Even though this is a recursive routine, it's not convenient to
analyze it using recurrences.  Side effects!

\ni $n$ is number of nodes (pieces of clothing, construction activities)

\ni $m$ is the number of edges (constraints).

\ni Each node is visited only once (we never make a node white), and
for each node we loop over all its outgoing edges once.  Therefore, we
visit each edge once.

\ni Total work: $\Theta(n+m)$.

\subsection{Potential Function Analysis}

\ni Intuition is that all the work happens in calls to {\tt Visit} and
there can't be too many such calls because nodes and edges are turning
from white to gray to black.

\ul

\li Operation is a call to {\tt Visit}.

\li $\Phi(G)$ is the total number of white edges in $G$:
$$\sum_{u\in V} \chi(G[\mbox{start},u]=\mbox{\sc white})+
\sum_{v\in\mbox{\em Adj}[u]} \chi(G[u,v]=\mbox{\sc white}).$$

\li Each time we enter {\tt Visit}, an edge becomes black, decreasing
the potential function by one and ``paying for'' the non-recursive
work in the subroutine.  How do we know that an edge isn't turned
black twice?

\ans{Because {\tt visit} is only called when $u$ (the ``from'' node)
is gray.} 

\li Maximum value of the potential function is one contribution from
each edge and one from each node (because of ``start'').  So, running
time is: $O(n+m)$.

\el

\subsection{Summary}

\ni Simple algorithm, very fast and practical.  Comes up in all sorts
of settings.


\section{STRONGLY CONNECTED COMPONENTS}

\subsection{Airline Flight Planning}

\ni Given a route map of an airline, would like to know whether ``you
can't get there from here.''

% seattle chicago  pittsburgh philadelphia
% LAX     houston  atlanta    rdu

\ul

\li Seattle (SEA): ORD
\li Chicago (ORD): PIT, LAX, DFW
\li Pittsburgh (PIT): PHL, ATL
\li Philadelphia (PHL): PIT, RDU
\li Los Angeles (LAX): SEA, DFW
\li Dallas (DFW): ATL
\li Atlanta (ATL): DFW, RDU

\el


\subsection{Definitions}

\ni A {\em path\/} in a graph $G=(V,E)$ is a sequence of nodes $u_1,
\ldots, u_k$, such that for all $i\in [1,k-1]$, $(u_i, u_{i+1}) \in
E$.

\ni Graph $G$ is {\em strongly connected\/} if, for every $u$ and $v$
in $V$, there is some path from $u$ to $v$ and some path from $v$ to
$u$.

\ni A strongly connected {\em component\/} of a graph is a maximal
subset of nodes (along with their associated edges) that is strongly
connected.  Nodes share a strongly connected component if they are
interreachable.

\subsection{More Formal Statement}

\ni Input is a graph $G=(V,E)$ (possibly with cycles) of $n$ nodes and
$m$ directed edges.

\ni Output is a set of components $C$, and a mapping $c:V\rightarrow
C$ from nodes to components of interreachability, and edges $D$
between components denoting one-way reachability.  

\ni Properties:

\ul \li If there is some path from $u$ to $v$ and from $v$ to $u$,
then $c(u) = c(v)$.

\li If $u$ and $v$ are in different components and there is an edge
from $u$ to $v$, then $(c(u), c(v)) \in D$.

\li The {\em component graph\/} $G'=(C,D)$ is a DAG.

\el

\ni How would you do it?  Let's try an example.

\subsection{Algorithm}

\begin{verbatim}
vector<int> * StronglyConnectedComponents( Graph G )
{
  list<GraphVert*> * L = TopologicalSort( G );
  Graph G_t = *(transpose( G ));

  for( unsigned int v=0; v < G_t.size(); v++ )
    G_t[v]->color = white;

  vector<int> * components = new vector<int>( G.size() );
  int component = 1;

  for( list<GraphVert*>::iterator iter = L->begin();
       iter != L->end();
       iter++ )
  {
    list<GraphVert*> * l = new list<GraphVert*>();

    int v = (*iter)->num;
    if( G_t[v]->color == white )
    {
      Visit( v, G_t, l );

      for( list<GraphVert*>::iterator iter = l->begin();
	   iter != l->end();
	   iter++ )
	(*components)[ (*iter)->num ] = component;

      component++;
    }
  }

  return components;
}
\end{verbatim}

\ni Here, {\tt transpose(G)} is graph transpose or edge reversal.

\subsection{Example}

\ni Note that component graph is given a topological numbering!

\ni We left out the computation of the edges $D$ of the component
graph (HW).

\ni Note what happens when we ``topologically sort'' a cyclic graph. 

\subsection{Running Time Analysis}

\ni This is really just two topological sorts: $\Theta(n+m)$.

\ni The magic is in the fact that this works at all!

\ni Terminology: forward reachable, backward reachable.  If $u$ and
$v$ are in the same strongly connected component, then $v$ is both
forward reachable and backward reachable from $u$ (and vice versa).

\ni Argue that $G$ and $G^T$ have the same strongly connected
components.

\ans{Two nodes share the same strongly connected component if and only
if they are both forward and backward reachable from each other.  This
remains the same when we reverse edges.}

\ni What can we say about when to nodes in the same strongly connected
component turn black (with respect to top-level calls to {\tt Visit})?

\ans{They are visited in the same top-level call.}

% never break up a strongly connected component during a
% traversal (forward or backward).  Why?

\subsection{Analysis}

\ni Observations: If $u$ is gray when $v$ is blackened, then $v$ is
forward reachable from $u$.  If $u$ precedes $v$ in $L$, then $u$ was
either white or gray when $v$ was blackened.  If white, then $v$ is
not forward reachable from $u$.

\ni Let $u$ be the first node in $L$ (after the first call to {\tt
topological sort}).

\ul

\li It is only forward reachable by nodes in its same strongly
connected component.  Why?  Picture. 

\li So, any node $v$ that is backward reachable fom $u$ shares $u$'s
strongly connected component.

\li Also, any $v$ in $u$'s strongly connected component is backward
reachable from $u$ (of course).

\li {\tt Visit(v, G\_t, l)} returns all (and only) nodes backward
reachable from $u$.

\li So, we correctly identify (and blacken) component 1.

\li Remove all the component 1 nodes from $L$ and $G^T$.

\li Repeat!

\el

\subsection{Summary}

\ni Like topological sort, fast and relatively simple.

\ni Very useful for:

\ul

\li analyzing graphs,

\li breaking up computations.

\el

\end{document}
