115 lines
4.0 KiB
OpenEdge ABL
115 lines
4.0 KiB
OpenEdge ABL
\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}
|