[ceph.git] / ceph / src / boost / libs / graph_parallel / doc / html / strong_components.html

<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
<title>Parallel BGL Connected Components</title>
<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
</head>
<body>
<div class="document" id="logo-connected-components">
<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Connected Components</h1>

<!-- Copyright (C) 2004-2008 The Trustees of Indiana University.
Use, modification and distribution is subject to the Boost Software
License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt) -->
<pre class="literal-block">
template&lt;typename Graph, typename ComponentMap&gt;
inline typename property_traits&lt;ComponentMap&gt;::value_type
strong_components( const Graph&amp; g, ComponentMap c);

namespace graph {
  template&lt;typename Graph, typename VertexComponentMap&gt;
  void
  fleischer_hendrickson_pinar_strong_components(const Graph&amp; g, VertexComponentMap r);

  template&lt;typename Graph, typename ReverseGraph,
           typename ComponentMap, typename IsoMapFR, typename IsoMapRF&gt;
  inline typename property_traits&lt;ComponentMap&gt;::value_type
  fleischer_hendrickson_pinar_strong_components(const Graph&amp; g,
                                                ComponentMap c,
                                                const ReverseGraph&amp; gr,
                                                IsoMapFR fr, IsoMapRF rf);
}
</pre>
<p>The <tt class="docutils literal"><span class="pre">strong_components()</span></tt> function computes the strongly connected
components of a directed graph.  The distributed strong components
algorithm uses the <a class="reference external" href="http://www.boost.org/libs/graph/doc/strong_components.html">sequential strong components</a> algorithm to
identify components local to a processor.  The distributed portion of
the algorithm is built on the <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a>
algorithm and is based on the work of Fleischer, Hendrickson, and
Pinar <a class="citation-reference" href="#fhp00" id="id1">[FHP00]</a>. The interface is a superset of the interface to the
BGL <a class="reference external" href="http://www.boost.org/libs/graph/doc/strong_components.html">sequential strong components</a> algorithm. The number of
strongly-connected components in the graph is returned to all
processes.</p>
<p>The distributed strong components algorithm works on both <tt class="docutils literal"><span class="pre">directed</span></tt>
and <tt class="docutils literal"><span class="pre">bidirectional</span></tt> graphs.  In the bidirectional case, a reverse
graph adapter is used to produce the required reverse graph.  In
the directed case, a separate graph is constructed in which all the
edges are reversed.</p>
<div class="contents topic" id="contents">
<p class="topic-title first">Contents</p>
<ul class="simple">
<li><a class="reference internal" href="#where-defined" id="id2">Where Defined</a></li>
<li><a class="reference internal" href="#parameters" id="id3">Parameters</a></li>
<li><a class="reference internal" href="#complexity" id="id4">Complexity</a></li>
<li><a class="reference internal" href="#algorithm-description" id="id5">Algorithm Description</a></li>
<li><a class="reference internal" href="#bibliography" id="id6">Bibliography</a></li>
</ul>
</div>
<div class="section" id="where-defined">
<h1><a class="toc-backref" href="#id2">Where Defined</a></h1>
<p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/distributed/strong_components.hpp</span></tt>&gt;</p>
<p>also accessible from</p>
<p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/strong_components.hpp</span></tt>&gt;</p>
</div>
<div class="section" id="parameters">
<h1><a class="toc-backref" href="#id3">Parameters</a></h1>
<dl class="docutils">
<dt>IN:  <tt class="docutils literal"><span class="pre">const</span> <span class="pre">Graph&amp;</span> <span class="pre">g</span></tt></dt>
<dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>.  The graph
type must also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a> and be directed.</dd>
<dt>OUT:  <tt class="docutils literal"><span class="pre">ComponentMap</span> <span class="pre">c</span></tt></dt>
<dd>The algorithm computes how many strongly connected components are in the
graph, and assigns each component an integer label.  The algorithm
then records to which component each vertex in the graph belongs by
recording the component number in the component property map.  The
<tt class="docutils literal"><span class="pre">ComponentMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>.  The
value type must be the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph.  The key
type must be the graph's vertex descriptor type.</dd>
<dt>UTIL:  <tt class="docutils literal"><span class="pre">VertexComponentMap</span> <span class="pre">r</span></tt></dt>
<dd>The algorithm computes a mapping from each vertex to the
representative of the strong component, stored in this property map.
The <tt class="docutils literal"><span class="pre">VertexComponentMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>.
The value and key types must be the vertex descriptor of the graph.</dd>
<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">ReverseGraph&amp;</span> <span class="pre">gr</span></tt></dt>
<dd><p class="first">The reverse (or transpose) graph of <tt class="docutils literal"><span class="pre">g</span></tt>, such that for each
directed edge <em>(u, v)</em> in <tt class="docutils literal"><span class="pre">g</span></tt> there exists a directed edge
<em>(fr(v), fr(u))</em> in <tt class="docutils literal"><span class="pre">gr</span></tt> and for each edge <em>(v', u')</em> in <em>gr</em>
there exists an edge <em>(rf(u'), rf(v'))</em> in <tt class="docutils literal"><span class="pre">g</span></tt>. The functions
<em>fr</em> and <em>rf</em> map from vertices in the graph to the reverse graph
and vice-verse, and are represented as property map arguments. The
concept requirements on this graph type are equivalent to those on
the <tt class="docutils literal"><span class="pre">Graph</span></tt> type, but the types need not be the same.</p>
<p class="last"><strong>Default</strong>: Either a <tt class="docutils literal"><span class="pre">reverse_graph</span></tt> adaptor over the original
graph (if the graph type is bidirectional, i.e., models the
<a class="reference external" href="http://www.boost.org/libs/graph/doc/BidirectionalGraph.html">Bidirectional Graph</a> concept) or a <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency list</a>
constructed from the input graph.</p>
</dd>
<dt>IN: <tt class="docutils literal"><span class="pre">IsoMapFR</span> <span class="pre">fr</span></tt></dt>
<dd><p class="first">A property map that maps from vertices in the input graph <tt class="docutils literal"><span class="pre">g</span></tt> to
vertices in the reversed graph <tt class="docutils literal"><span class="pre">gr</span></tt>. The type <tt class="docutils literal"><span class="pre">IsoMapFR</span></tt> must
model the <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> concept and have the graph's
vertex descriptor as its key type and the reverse graph's vertex
descriptor as its value type.</p>
<p class="last"><strong>Default</strong>: An identity property map (if the graph type is
bidirectional) or a distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> (if the
graph type is directed).</p>
</dd>
<dt>IN: <tt class="docutils literal"><span class="pre">IsoMapRF</span> <span class="pre">rf</span></tt></dt>
<dd><p class="first">A property map that maps from vertices in the reversed graph <tt class="docutils literal"><span class="pre">gr</span></tt>
to vertices in the input graph <tt class="docutils literal"><span class="pre">g</span></tt>. The type <tt class="docutils literal"><span class="pre">IsoMapRF</span></tt> must
model the <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> concept and have the reverse
graph's vertex descriptor as its key type and the graph's vertex
descriptor as its value type.</p>
<p class="last"><strong>Default</strong>: An identity property map (if the graph type is
bidirectional) or a distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> (if the
graph type is directed).</p>
</dd>
</dl>
</div>
<div class="section" id="complexity">
<h1><a class="toc-backref" href="#id4">Complexity</a></h1>
<p>The local phase of the algorithm is <em>O(V + E)</em>.  The parallel phase of
the algorithm requires at most <em>O(V)</em> supersteps each containing two
breadth first searches which are <em>O(V + E)</em> each.</p>
</div>
<div class="section" id="algorithm-description">
<h1><a class="toc-backref" href="#id5">Algorithm Description</a></h1>
<p>Prior to executing the sequential phase of the algorithm, each process
identifies any completely local strong components which it labels and
removes from the vertex set considered in the parallel phase of the
algorithm.</p>
<p>The parallel phase of the distributed strong components algorithm
consists of series of supersteps.  Each superstep starts with one
or more vertex sets which are guaranteed to completely contain
any remaining strong components.  A <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a>
is performed starting from the first vertex in each vertex set.
All of these breadth first searches are performed in parallel by having
each processor call <tt class="docutils literal"><span class="pre">breadth_first_search()</span></tt> with a different starting
vertex, and if necessary inserting additional vertices into the
<tt class="docutils literal"><span class="pre">distributed</span> <span class="pre">queue</span></tt> used for breadth first search before invoking
the algorithm.  A second <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a> is
performed on the reverse graph in the same fashion.  For each initial
vertex set, the successor set (the vertices reached in the forward
breadth first search), and the predecessor set (the vertices reached
in the backward breadth first search) is computed.  The intersection
of the predecessor and successor sets form a strongly connected
component which is labeled as such.  The remaining vertices in the
initial vertex set are partitioned into three subsets each guaranteed
to completely contain any remaining strong components.  These three sets
are the vertices in the predecessor set not contained in the identified
strongly connected component, the vertices in the successor set not
in the strongly connected component, and the remaing vertices in the
initial vertex set not in the predecessor or successor sets.  Once
new vertex sets are identified, the algorithm begins a new superstep.
The algorithm halts when no vertices remain.</p>
<p>To boost performance in sparse graphs when identifying small components,
when less than a given portion of the initial number of vertices
remain in active vertex sets, a filtered graph adapter is used
to limit the graph seen by the breadth first search algorithm to the
active vertices.</p>
</div>
<div class="section" id="bibliography">
<h1><a class="toc-backref" href="#id6">Bibliography</a></h1>
<table class="docutils citation" frame="void" id="fhp00" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id1">[FHP00]</a></td><td>Lisa Fleischer, Bruce Hendrickson, and Ali Pinar. On
Identifying Strongly Connected Components in Parallel. In Parallel and
Distributed Processing (IPDPS), volume 1800 of Lecture Notes in
Computer Science, pages 505--511, 2000. Springer.</td></tr>
</tbody>
</table>
<hr class="docutils" />
<p>Copyright (C) 2004, 2005 The Trustees of Indiana University.</p>
<p>Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine</p>
<!--  -->
</div>
</div>
<div class="footer">
<hr class="footer" />
Generated on: 2009-05-31 00:21 UTC.
Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.

</div>
</body>
</html>
Commit	Line	Data
7c673cae FG	1	<?xml version="1.0" encoding="utf-8" ?>
	2	<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
	3	<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
	4	<head>
	5	<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
	6	<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
	7	<title>Parallel BGL Connected Components</title>
	8	<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
	9	</head>
	10	<body>
	11	<div class="document" id="logo-connected-components">
	12	<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Connected Components</h1>
	13
	14	<!-- Copyright (C) 2004-2008 The Trustees of Indiana University.
	15	Use, modification and distribution is subject to the Boost Software
	16	License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	17	http://www.boost.org/LICENSE_1_0.txt) -->
	18	<pre class="literal-block">
	19	template<typename Graph, typename ComponentMap>
	20	inline typename property_traits<ComponentMap>::value_type
	21	strong_components( const Graph& g, ComponentMap c);
	22
	23	namespace graph {
	24	template<typename Graph, typename VertexComponentMap>
	25	void
	26	fleischer_hendrickson_pinar_strong_components(const Graph& g, VertexComponentMap r);
	27
	28	template<typename Graph, typename ReverseGraph,
	29	typename ComponentMap, typename IsoMapFR, typename IsoMapRF>
	30	inline typename property_traits<ComponentMap>::value_type
	31	fleischer_hendrickson_pinar_strong_components(const Graph& g,
	32	ComponentMap c,
	33	const ReverseGraph& gr,
	34	IsoMapFR fr, IsoMapRF rf);
	35	}
	36	</pre>
	37	<p>The <tt class="docutils literal"><span class="pre">strong_components()</span></tt> function computes the strongly connected
	38	components of a directed graph. The distributed strong components
	39	algorithm uses the <a class="reference external" href="http://www.boost.org/libs/graph/doc/strong_components.html">sequential strong components</a> algorithm to
	40	identify components local to a processor. The distributed portion of
	41	the algorithm is built on the <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a>
	42	algorithm and is based on the work of Fleischer, Hendrickson, and
	43	Pinar <a class="citation-reference" href="#fhp00" id="id1">[FHP00]</a>. The interface is a superset of the interface to the
	44	BGL <a class="reference external" href="http://www.boost.org/libs/graph/doc/strong_components.html">sequential strong components</a> algorithm. The number of
	45	strongly-connected components in the graph is returned to all
	46	processes.</p>
	47	<p>The distributed strong components algorithm works on both <tt class="docutils literal"><span class="pre">directed</span></tt>
	48	and <tt class="docutils literal"><span class="pre">bidirectional</span></tt> graphs. In the bidirectional case, a reverse
	49	graph adapter is used to produce the required reverse graph. In
	50	the directed case, a separate graph is constructed in which all the
	51	edges are reversed.</p>
	52	<div class="contents topic" id="contents">
	53	<p class="topic-title first">Contents</p>
	54	<ul class="simple">
	55	<li><a class="reference internal" href="#where-defined" id="id2">Where Defined</a></li>
	56	<li><a class="reference internal" href="#parameters" id="id3">Parameters</a></li>
	57	<li><a class="reference internal" href="#complexity" id="id4">Complexity</a></li>
	58	<li><a class="reference internal" href="#algorithm-description" id="id5">Algorithm Description</a></li>
	59	<li><a class="reference internal" href="#bibliography" id="id6">Bibliography</a></li>
	60	</ul>
	61	</div>
	62	<div class="section" id="where-defined">
	63	<h1><a class="toc-backref" href="#id2">Where Defined</a></h1>
	64	<p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/strong_components.hpp</span></tt>></p>
65	<p>also accessible from</p>
66	<p><<tt class="docutils literal"><span class="pre">boost/graph/strong_components.hpp</span></tt>></p>
67	</div>
68	<div class="section" id="parameters">
69	<h1><a class="toc-backref" href="#id3">Parameters</a></h1>
70	<dl class="docutils">
71	<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">Graph&</span> <span class="pre">g</span></tt></dt>
72	<dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>. The graph
73	type must also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a> and be directed.</dd>
74	<dt>OUT: <tt class="docutils literal"><span class="pre">ComponentMap</span> <span class="pre">c</span></tt></dt>
75	<dd>The algorithm computes how many strongly connected components are in the
76	graph, and assigns each component an integer label. The algorithm
77	then records to which component each vertex in the graph belongs by
78	recording the component number in the component property map. The
79	<tt class="docutils literal"><span class="pre">ComponentMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. The
80	value type must be the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph. The key
81	type must be the graph's vertex descriptor type.</dd>
82	<dt>UTIL: <tt class="docutils literal"><span class="pre">VertexComponentMap</span> <span class="pre">r</span></tt></dt>
83	<dd>The algorithm computes a mapping from each vertex to the
84	representative of the strong component, stored in this property map.
85	The <tt class="docutils literal"><span class="pre">VertexComponentMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>.
86	The value and key types must be the vertex descriptor of the graph.</dd>
87	<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">ReverseGraph&</span> <span class="pre">gr</span></tt></dt>
88	<dd><p class="first">The reverse (or transpose) graph of <tt class="docutils literal"><span class="pre">g</span></tt>, such that for each
89	directed edge <em>(u, v)</em> in <tt class="docutils literal"><span class="pre">g</span></tt> there exists a directed edge
90	<em>(fr(v), fr(u))</em> in <tt class="docutils literal"><span class="pre">gr</span></tt> and for each edge <em>(v', u')</em> in <em>gr</em>
91	there exists an edge <em>(rf(u'), rf(v'))</em> in <tt class="docutils literal"><span class="pre">g</span></tt>. The functions
92	<em>fr</em> and <em>rf</em> map from vertices in the graph to the reverse graph
93	and vice-verse, and are represented as property map arguments. The
94	concept requirements on this graph type are equivalent to those on
95	the <tt class="docutils literal"><span class="pre">Graph</span></tt> type, but the types need not be the same.</p>
96	<p class="last"><strong>Default</strong>: Either a <tt class="docutils literal"><span class="pre">reverse_graph</span></tt> adaptor over the original
97	graph (if the graph type is bidirectional, i.e., models the
98	<a class="reference external" href="http://www.boost.org/libs/graph/doc/BidirectionalGraph.html">Bidirectional Graph</a> concept) or a <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency list</a>
99	constructed from the input graph.</p>
100	</dd>
101	<dt>IN: <tt class="docutils literal"><span class="pre">IsoMapFR</span> <span class="pre">fr</span></tt></dt>
102	<dd><p class="first">A property map that maps from vertices in the input graph <tt class="docutils literal"><span class="pre">g</span></tt> to
103	vertices in the reversed graph <tt class="docutils literal"><span class="pre">gr</span></tt>. The type <tt class="docutils literal"><span class="pre">IsoMapFR</span></tt> must
104	model the <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> concept and have the graph's
105	vertex descriptor as its key type and the reverse graph's vertex
106	descriptor as its value type.</p>
107	<p class="last"><strong>Default</strong>: An identity property map (if the graph type is
108	bidirectional) or a distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> (if the
109	graph type is directed).</p>
110	</dd>
111	<dt>IN: <tt class="docutils literal"><span class="pre">IsoMapRF</span> <span class="pre">rf</span></tt></dt>
112	<dd><p class="first">A property map that maps from vertices in the reversed graph <tt class="docutils literal"><span class="pre">gr</span></tt>
113	to vertices in the input graph <tt class="docutils literal"><span class="pre">g</span></tt>. The type <tt class="docutils literal"><span class="pre">IsoMapRF</span></tt> must
114	model the <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> concept and have the reverse
115	graph's vertex descriptor as its key type and the graph's vertex
116	descriptor as its value type.</p>
117	<p class="last"><strong>Default</strong>: An identity property map (if the graph type is
118	bidirectional) or a distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> (if the
119	graph type is directed).</p>
120	</dd>
121	</dl>
122	</div>
123	<div class="section" id="complexity">
124	<h1><a class="toc-backref" href="#id4">Complexity</a></h1>
125	<p>The local phase of the algorithm is <em>O(V + E)</em>. The parallel phase of
126	the algorithm requires at most <em>O(V)</em> supersteps each containing two
127	breadth first searches which are <em>O(V + E)</em> each.</p>
128	</div>
129	<div class="section" id="algorithm-description">
130	<h1><a class="toc-backref" href="#id5">Algorithm Description</a></h1>
131	<p>Prior to executing the sequential phase of the algorithm, each process
132	identifies any completely local strong components which it labels and
133	removes from the vertex set considered in the parallel phase of the
134	algorithm.</p>
135	<p>The parallel phase of the distributed strong components algorithm
136	consists of series of supersteps. Each superstep starts with one
137	or more vertex sets which are guaranteed to completely contain
138	any remaining strong components. A <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a>
139	is performed starting from the first vertex in each vertex set.
140	All of these breadth first searches are performed in parallel by having
141	each processor call <tt class="docutils literal"><span class="pre">breadth_first_search()</span></tt> with a different starting
142	vertex, and if necessary inserting additional vertices into the
143	<tt class="docutils literal"><span class="pre">distributed</span> <span class="pre">queue</span></tt> used for breadth first search before invoking
144	the algorithm. A second <a class="reference external" href="breadth_first_search.html">distributed breadth first search</a> is
145	performed on the reverse graph in the same fashion. For each initial
146	vertex set, the successor set (the vertices reached in the forward
147	breadth first search), and the predecessor set (the vertices reached
148	in the backward breadth first search) is computed. The intersection
149	of the predecessor and successor sets form a strongly connected
150	component which is labeled as such. The remaining vertices in the
151	initial vertex set are partitioned into three subsets each guaranteed
152	to completely contain any remaining strong components. These three sets
153	are the vertices in the predecessor set not contained in the identified
154	strongly connected component, the vertices in the successor set not
155	in the strongly connected component, and the remaing vertices in the
156	initial vertex set not in the predecessor or successor sets. Once
157	new vertex sets are identified, the algorithm begins a new superstep.
158	The algorithm halts when no vertices remain.</p>
159	<p>To boost performance in sparse graphs when identifying small components,
160	when less than a given portion of the initial number of vertices
161	remain in active vertex sets, a filtered graph adapter is used
162	to limit the graph seen by the breadth first search algorithm to the
163	active vertices.</p>
164	</div>
165	<div class="section" id="bibliography">
166	<h1><a class="toc-backref" href="#id6">Bibliography</a></h1>
167	<table class="docutils citation" frame="void" id="fhp00" rules="none">
168	<colgroup><col class="label" /><col /></colgroup>
169	<tbody valign="top">
170	<tr><td class="label"><a class="fn-backref" href="#id1">[FHP00]</a></td><td>Lisa Fleischer, Bruce Hendrickson, and Ali Pinar. On
171	Identifying Strongly Connected Components in Parallel. In Parallel and
172	Distributed Processing (IPDPS), volume 1800 of Lecture Notes in
173	Computer Science, pages 505--511, 2000. Springer.</td></tr>
174	</tbody>
175	</table>
176	<hr class="docutils" />
177	<p>Copyright (C) 2004, 2005 The Trustees of Indiana University.</p>
178	<p>Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine</p>
179	<!-- -->
180	</div>
181	</div>
182	<div class="footer">
183	<hr class="footer" />
184	Generated on: 2009-05-31 00:21 UTC.
185	Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
186
187	</div>
188	</body>
189	</html>