123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420 |
- <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>
|