421 lines
10 KiB
HTML
421 lines
10 KiB
HTML
<HTML>
|
|
<!--
|
|
Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
|
|
|
|
Distributed under 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)
|
|
-->
|
|
<Head>
|
|
<Title>Boost Graph Library: Incremental Connected Components</Title>
|
|
<style type="text/css">
|
|
<!--
|
|
.code
|
|
{
|
|
border-left-style: groove;
|
|
border-left-width: 1px;
|
|
padding-left: 2em;
|
|
}
|
|
|
|
-->
|
|
</style>
|
|
|
|
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
|
|
ALINK="#ff0000">
|
|
<IMG SRC="../../../boost.png"
|
|
ALT="C++ Boost" width="277" height="86">
|
|
|
|
<BR Clear>
|
|
|
|
<H1>Incremental Connected Components</H1>
|
|
|
|
<P>
|
|
This section describes a family of functions and classes that work
|
|
together to calculate the connected components of an undirected graph.
|
|
The algorithm used here is based on the disjoint-sets (fast
|
|
union-find) data structure [<A
|
|
HREF="bibliography.html#clr90">8</A>,<A
|
|
HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>]
|
|
which is a good method to use for situations where the graph is
|
|
growing (edges are being added) and the connected components
|
|
information needs to be updated repeatedly. This method does not cover
|
|
the situation where edges are both added and removed from the graph,
|
|
hence it is called <b><i>incremental</i></b><a
|
|
href="bibliography.html#eppstein97:dynamic_graph">[42]</a> (and not
|
|
fully dynamic). The disjoint-sets class is described in Section <A
|
|
HREF="../../disjoint_sets/disjoint_sets.html">Disjoint Sets</A>.
|
|
|
|
<P>
|
|
The following five operations are the primary functions that you will
|
|
use to calculate and maintain the connected components. The objects
|
|
used here are a graph <TT>g</TT>, a disjoint-sets structure <TT>ds</TT>,
|
|
and vertices <TT>u</TT> and <TT>v</TT>.
|
|
|
|
<P>
|
|
|
|
<UL>
|
|
<LI><TT>initialize_incremental_components(g, ds)</TT>
|
|
<BR>
|
|
Basic initialization of the disjoint-sets structure. Each
|
|
vertex in the graph <TT>g</TT> is in its own set.
|
|
</LI>
|
|
<LI><TT>incremental_components(g, ds)</TT>
|
|
<BR>
|
|
The connected components are calculated based on the edges in the graph
|
|
<TT>g</TT> and the information is embedded in <TT>ds</TT>.
|
|
</LI>
|
|
<LI><TT>ds.find_set(v)</TT>
|
|
<BR>
|
|
Extracts the component information for vertex <TT>v</TT> from the
|
|
disjoint-sets.
|
|
</LI>
|
|
<LI><TT>ds.union_set(u, v)</TT>
|
|
<BR>
|
|
Update the disjoint-sets structure when edge <i>(u,v)</i> is added to the graph.
|
|
</LI>
|
|
</UL>
|
|
|
|
<P>
|
|
|
|
<H3>Complexity</H3>
|
|
|
|
<P>
|
|
The time complexity for the whole process is <i>O(V + E
|
|
alpha(E,V))</i> where <i>E</i> is the total number of edges in the
|
|
graph (by the end of the process) and <i>V</i> is the number of
|
|
vertices. <i>alpha</i> is the inverse of Ackermann's function which
|
|
has explosive recursively exponential growth. Therefore its inverse
|
|
function grows <I>very</I> slowly. For all practical purposes
|
|
<i>alpha(m,n) <= 4</i> which means the time complexity is only
|
|
slightly larger than <i>O(V + E)</i>.
|
|
|
|
<P>
|
|
|
|
<H3>Example</H3>
|
|
|
|
<P>
|
|
Maintain the connected components of a graph while adding edges using
|
|
the disjoint-sets data structure. The full source code for this
|
|
example can be found in <a
|
|
href="../example/incremental_components.cpp"><TT>examples/incremental_components.cpp</TT></a>.
|
|
|
|
<P>
|
|
<PRE class="code">
|
|
using namespace boost;
|
|
|
|
int main(int argc, char* argv[])
|
|
{
|
|
typedef adjacency_list <vecS, vecS, undirectedS> Graph;
|
|
typedef graph_traits<Graph>::vertex_descriptor Vertex;
|
|
typedef graph_traits<Graph>::vertices_size_type VertexIndex;
|
|
|
|
const int VERTEX_COUNT = 6;
|
|
Graph graph(VERTEX_COUNT);
|
|
|
|
std::vector<VertexIndex> rank(num_vertices(graph));
|
|
std::vector<Vertex> parent(num_vertices(graph));
|
|
|
|
typedef VertexIndex* Rank;
|
|
typedef Vertex* Parent;
|
|
|
|
disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
|
|
|
|
initialize_incremental_components(graph, ds);
|
|
incremental_components(graph, ds);
|
|
|
|
graph_traits<Graph>::edge_descriptor edge;
|
|
bool flag;
|
|
|
|
boost::tie(edge, flag) = add_edge(0, 1, graph);
|
|
ds.union_set(0,1);
|
|
|
|
boost::tie(edge, flag) = add_edge(1, 4, graph);
|
|
ds.union_set(1,4);
|
|
|
|
boost::tie(edge, flag) = add_edge(4, 0, graph);
|
|
ds.union_set(4,0);
|
|
|
|
boost::tie(edge, flag) = add_edge(2, 5, graph);
|
|
ds.union_set(2,5);
|
|
|
|
std::cout << "An undirected graph:" << std::endl;
|
|
print_graph(graph, get(boost::vertex_index, graph));
|
|
std::cout << std::endl;
|
|
|
|
BOOST_FOREACH(Vertex current_vertex, vertices(graph)) {
|
|
std::cout << "representative[" << current_vertex << "] = " <<
|
|
ds.find_set(current_vertex) << std::endl;
|
|
}
|
|
|
|
std::cout << std::endl;
|
|
|
|
typedef component_index<VertexIndex> Components;
|
|
|
|
// NOTE: Because we're using vecS for the graph type, we're
|
|
// effectively using identity_property_map for a vertex index map.
|
|
// If we were to use listS instead, the index map would need to be
|
|
// explicity passed to the component_index constructor.
|
|
Components components(parent.begin(), parent.end());
|
|
|
|
// Iterate through the component indices
|
|
BOOST_FOREACH(VertexIndex current_index, components) {
|
|
std::cout << "component " << current_index << " contains: ";
|
|
|
|
// Iterate through the child vertex indices for [current_index]
|
|
BOOST_FOREACH(VertexIndex child_index,
|
|
components[current_index]) {
|
|
std::cout << child_index << " ";
|
|
}
|
|
|
|
std::cout << std::endl;
|
|
}
|
|
|
|
return (0);
|
|
}
|
|
</PRE>
|
|
|
|
<P>
|
|
<hr>
|
|
<p>
|
|
|
|
<H2><A NAME="sec:initialize-incremental-components"></A>
|
|
<TT>initialize_incremental_components</TT>
|
|
</H2>
|
|
|
|
<P>
|
|
<DIV ALIGN="left">
|
|
<TABLE CELLPADDING=3 border>
|
|
<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH>
|
|
<TD ALIGN="LEFT">undirected</TD>
|
|
</TR>
|
|
<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
|
|
<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD>
|
|
</TR>
|
|
<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
|
|
<TD></TD>
|
|
</TR>
|
|
</TABLE>
|
|
</DIV>
|
|
|
|
<P>
|
|
<PRE>
|
|
template <class VertexListGraph, class DisjointSets>
|
|
void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
|
|
</PRE>
|
|
|
|
<P>
|
|
This prepares the disjoint-sets data structure for the incremental
|
|
connected components algorithm by making each vertex in the graph a
|
|
member of its own component (or set).
|
|
|
|
<P>
|
|
|
|
<H3>Where Defined</H3>
|
|
|
|
<P>
|
|
<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
|
|
|
|
<p>
|
|
<hr>
|
|
<P>
|
|
|
|
<H2><A NAME="sec:incremental-components"></A>
|
|
<TT>incremental_components</TT>
|
|
</H2>
|
|
|
|
<P>
|
|
<DIV ALIGN="left">
|
|
<TABLE CELLPADDING=3 border>
|
|
<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH>
|
|
<TD ALIGN="LEFT">undirected</TD>
|
|
</TR>
|
|
<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
|
|
<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD>
|
|
</TR>
|
|
<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
|
|
<TD ALIGN="LEFT"><i>O(E)</i></TD>
|
|
</TR>
|
|
</TABLE>
|
|
</DIV>
|
|
|
|
<p>
|
|
<PRE>
|
|
template <class EdgeListGraph, class DisjointSets>
|
|
void incremental_components(EdgeListGraph& g, DisjointSets& ds)
|
|
</PRE>
|
|
|
|
<P>
|
|
This function calculates the connected components of the graph,
|
|
embedding the results in the disjoint-sets data structure.
|
|
|
|
<P>
|
|
|
|
<H3>Where Defined</H3>
|
|
|
|
<P>
|
|
<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
|
|
|
|
<P>
|
|
|
|
<H3>Requirements on Types</H3>
|
|
|
|
<P>
|
|
|
|
<UL>
|
|
<LI>The graph type must be a model of <a href="./EdgeListGraph.html">EdgeListGraph</a>.
|
|
</LI>
|
|
</UL>
|
|
|
|
<P>
|
|
<hr>
|
|
<p>
|
|
|
|
<H2><A NAME="sec:same-component">
|
|
<TT>same_component</TT></A>
|
|
</H2>
|
|
|
|
<P>
|
|
<DIV ALIGN="left">
|
|
<TABLE CELLPADDING=3 border>
|
|
<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
|
|
<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD>
|
|
</TR>
|
|
<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
|
|
<TD ALIGN="LEFT"><i>O(alpha(E,V))</i></TD>
|
|
</TR>
|
|
</TABLE>
|
|
</DIV>
|
|
|
|
<P>
|
|
<PRE>
|
|
template <class Vertex, class DisjointSet>
|
|
bool same_component(Vertex u, Vertex v, DisjointSet& ds)
|
|
</PRE>
|
|
|
|
<P>
|
|
This function determines whether <TT>u</TT> and <TT>v</TT> are in the same
|
|
component.
|
|
|
|
<P>
|
|
|
|
<H3>Where Defined</H3>
|
|
|
|
<P>
|
|
<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
|
|
|
|
<P>
|
|
|
|
<H3>Requirements on Types</H3>
|
|
|
|
<P>
|
|
|
|
<UL>
|
|
<LI><TT>Vertex</TT> must be compatible with the rank and parent
|
|
property maps of the <TT>DisjointSets</TT> data structure.
|
|
</LI>
|
|
</UL>
|
|
|
|
<P>
|
|
<hr>
|
|
<p>
|
|
|
|
<H2><A NAME="sec:component-index"></A>
|
|
<TT>component_index</TT>
|
|
</H2>
|
|
|
|
<p>
|
|
<PRE>
|
|
component_index<Index>
|
|
</PRE>
|
|
|
|
<P>
|
|
The <tt>component_index</tt> class provides an STL
|
|
container-like view for the components of the graph. Each component is
|
|
a container-like object, and access is provided via
|
|
the <TT>operator[]</TT>. A <TT>component_index</TT> object is
|
|
initialized with the parents property in the disjoint-sets calculated
|
|
from the <TT>incremental_components()</TT> function. Optionally, a
|
|
vertex -> index property map is passed in
|
|
(<tt>identity_property_map</tt> is used by default).
|
|
|
|
<P>
|
|
|
|
<H3>Where Defined</H3>
|
|
|
|
<P>
|
|
<a href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
|
|
|
|
<P>
|
|
|
|
<H3>Members</H3>
|
|
|
|
<P>
|
|
|
|
<table border>
|
|
|
|
<tr>
|
|
<th>Member</th> <th>Description</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td><tt>value_type/size_type</tt></td>
|
|
<td>
|
|
The type for a component index (same as <tt>Index</tt>).
|
|
</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td><tt>size_type size()</tt></td>
|
|
<td>
|
|
Returns the number of components in the graph.
|
|
</td>
|
|
</tr>
|
|
|
|
|
|
<tr>
|
|
<td><tt>iterator/const_iterator</tt></td>
|
|
<td>
|
|
Iterators used to traverse the available component indices [0 to <tt>size()</tt>).
|
|
</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td><tt>iterator begin() const</tt></td>
|
|
<td>
|
|
Returns an iterator at the start of the component indices (0).
|
|
</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td><tt>iterator end() const</tt></td>
|
|
<td>
|
|
Returns an iterator past the end of the component indices (<tt>size()</tt>).
|
|
</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td><tt>std::pair<component_iterator, component_iterator> operator[size_type index] const</tt></td>
|
|
<td>
|
|
Returns a pair of iterators for the component at <tt>index</tt> where <tt>index</tt> is in [0, <tt>size()</tt>).
|
|
</td>
|
|
</tr>
|
|
|
|
</table>
|
|
|
|
<br>
|
|
<HR>
|
|
<TABLE>
|
|
<TR valign=top>
|
|
<TD nowrap>Copyright © 2000-2001</TD><TD>
|
|
<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
|
|
Indiana University (<A
|
|
HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
|
|
<A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
|
|
<A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
|
|
Indiana University (<A
|
|
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
|
|
</TD></TR></TABLE>
|
|
|
|
</BODY>
|
|
</HTML>
|