strong_components.w

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

\documentclass[11pt]{report}

\input{defs}


\setlength\overfullrule{5pt}
\tolerance=10000
\sloppy
\hfuzz=10pt

\makeindex

\begin{document}

\title{A Generic Programming Implementation of Strongly Connected Components}
\author{Jeremy G. Siek}

\maketitle

\section{Introduction}

This paper describes the implementation of the
\code{strong\_components()} function of the Boost Graph Library.  The
function computes the strongly connects components of a directed graph
using Tarjan's DFS-based
algorithm~\cite{tarjan72:dfs_and_linear_algo}.

A \keyword{strongly connected component} (SCC) of a directed graph
$G=(V,E)$ is a maximal set of vertices $U$ which is in $V$ such that
for every pair of vertices $u$ and $v$ in $U$, we have both a path
from $u$ to $v$ and path from $v$ to $u$. That is to say that $u$ and
$v$ are reachable from each other.

cross edge (u,v) is an edge from one subtree to another subtree
 -> discover_time[u] > discover_time[v]

Lemma 10.  Let $v$ and $w$ be vertices in $G$ which are in the same
SCC and let $F$ be any depth-first forest of $G$. Then $v$ and $w$
have a common ancestor in $F$. Also, if $u$ is the common ancestor of
$u$ and $v$ with the latest discover time then $w$ is also in the same
SCC as $u$ and $v$.

Proof. 

If there is a path from $v$ to $w$ and if they are in different DFS
trees, then the discover time for $w$ must be earlier than for $v$.
Otherwise, the tree that contains $v$ would have extended along the
path to $w$, putting $v$ and $w$ in the same tree.


The following is an informal description of Tarjan's algorithm for
computing strongly connected components. It is basically a variation
on depth-first search, with extra actions being taken at the
``discover vertex'' and ``finish vertex'' event points. It may help to
think of the actions taken at the ``discover vertex'' event point as
occuring ``on the way down'' a DFS-tree (from the root towards the
leaves), and actions taken a the ``finish vertex'' event point as
occuring ``on the way back up''.

There are three things that need to happen on the way down. For each
vertex $u$ visited we record the discover time $d[u]$, push vertex $u$
onto a auxiliary stack, and set $root[u] = u$.  The root field will
end up mapping each vertex to the topmost vertex in the same strongly
connected component.  By setting $root[u] = u$ we are starting with
each vertex in a component by itself.

Now to describe what happens on the way back up. Suppose we have just
finished visiting all of the vertices adjacent to some vertex $u$.  We
then scan each of the adjacent vertices again, checking the root of
each for which one has the earliest discover time, which we will call
root $a$. We then compare $a$ with vertex $u$ and consider the
following cases:

\begin{enumerate}
\item If $d[a] < d[u]$ then we know that $a$ is really an ancestor of
  $u$ in the DFS tree and therefore we have a cycle and $u$ must be in
  a SCC with $a$. We then set $root[u] = a$ and continue our way back up
  the DFS.
  
\item If $a = u$ then we know that $u$ must be the topmost vertex of a
  subtree that defines a SCC.  All of the vertices in this subtree are
  further down on the stack than vertex $u$ so we pop the vertices off
  of the stack until we reach $u$ and mark each one as being in the
  same component.
  
\item If $d[a] > d[u]$ then the adjacent vertices are in different
  strongly connected components. We continue our way back up the
  DFS.

\end{enumerate}



@d Build a list of vertices for each strongly connected component
@{
template <typename Graph, typename ComponentMap, typename ComponentLists>
void build_component_lists
  (const Graph& g,
   typename graph_traits<Graph>::vertices_size_type num_scc,
   ComponentMap component_number,
   ComponentLists& components)
{
  components.resize(num_scc);
  typename graph_traits<Graph>::vertex_iterator vi, vi_end;
  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
    components[component_number[*vi]].push_back(*vi);
}
@}


\bibliographystyle{abbrv}
\bibliography{jtran,ggcl,optimization,generic-programming,cad}

\end{document}