Subject: [Boost-commit] svn:boost r56015 - in trunk: boost/graph boost/graph/detail libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-09-04 10:49:25
Author: jewillco
Date: 2009-09-04 10:49:24 EDT (Fri, 04 Sep 2009)
New Revision: 56015
URL: http://svn.boost.org/trac/boost/changeset/56015
Log:
Added fixes to and a test for incremental_components from Michael Hansen; fixes #3250
Added:
trunk/libs/graph/test/incremental_components_test.cpp (contents, props changed)
Text files modified:
trunk/boost/graph/detail/incremental_components.hpp | 160 +++++++++---------------------
trunk/boost/graph/incremental_components.hpp | 184 +++++++++++++++++++++++-----------
trunk/libs/graph/doc/incremental_components.html | 211 +++++++++++++++++++--------------------
trunk/libs/graph/example/incremental-components-eg.cpp | 92 ++++++++++------
trunk/libs/graph/example/incremental_components.cpp | 99 ++++++++++--------
trunk/libs/graph/example/incremental_components.expected | 2
trunk/libs/graph/test/Jamfile.v2 | 1
7 files changed, 388 insertions(+), 361 deletions(-)
Modified: trunk/boost/graph/detail/incremental_components.hpp
==============================================================================
--- trunk/boost/graph/detail/incremental_components.hpp (original)
+++ trunk/boost/graph/detail/incremental_components.hpp 2009-09-04 10:49:24 EDT (Fri, 04 Sep 2009)
@@ -1,6 +1,7 @@
//=======================================================================
// Copyright 2002 Indiana University.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -11,129 +12,64 @@
#define BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP
#include <boost/operators.hpp>
-#include <boost/pending/disjoint_sets.hpp>
namespace boost {
namespace detail {
- //=========================================================================
- // Implementation detail of incremental_components
+ // Iterator for a component index linked list. The contents of
+ // each array element represent the next index in the list. A
+ // special value (the maximum index + 1) is used to terminate a
+ // list.
+ template <typename IndexRandomAccessIterator>
+ class component_index_iterator :
+ boost::forward_iterator_helper<component_index_iterator<IndexRandomAccessIterator>,
+ typename std::iterator_traits<IndexRandomAccessIterator>::value_type,
+ typename std::iterator_traits<IndexRandomAccessIterator>::difference_type,
+ typename std::iterator_traits<IndexRandomAccessIterator>::pointer,
+ typename std::iterator_traits<IndexRandomAccessIterator>::reference> {
+ private:
+ typedef component_index_iterator<IndexRandomAccessIterator> self;
- //-------------------------------------------------------------------------
- // Helper functions for the component_index class
-
- // Record the representative vertices in the header array.
- // Representative vertices now point to the component number.
-
- template <class Parent, class OutputIterator, class Integer>
- inline void
- build_components_header(Parent p,
- OutputIterator header,
- Integer num_nodes)
- {
- Parent component = p;
- Integer component_num = 0;
- for (Integer v = 0; v != num_nodes; ++v)
- if (p[v] == v) {
- *header++ = v;
- component[v] = component_num++;
- }
- }
-
-
- // Pushes x onto the front of the list. The list is represented in
- // an array.
- template <class Next, class T, class V>
- inline void array_push_front(Next next, T& head, V x)
- {
- T tmp = head;
- head = x;
- next[x] = tmp;
- }
-
-
- // Create a linked list of the vertices in each component
- // by reusing the representative array.
- template <class Parent1, class Parent2,
- class Integer>
- void
- link_components(Parent1 component, Parent2 header,
- Integer num_nodes, Integer num_components)
- {
- // Make the non-representative vertices point to their component
- Parent1 representative = component;
- for (Integer v = 0; v != num_nodes; ++v)
- if (component[v] >= num_components
- || header[component[v]] != v)
- component[v] = component[representative[v]];
-
- // initialize the "head" of the lists to "NULL"
- std::fill_n(header, num_components, num_nodes);
-
- // Add each vertex to the linked list for its component
- Parent1 next = component;
- for (Integer k = 0; k != num_nodes; ++k)
- array_push_front(next, header[component[k]], k);
- }
-
-
-
- template <class IndexContainer, class HeaderContainer>
- void
- construct_component_index(IndexContainer& index, HeaderContainer& header)
- {
- typedef typename IndexContainer::value_type Integer;
- build_components_header(index.begin(),
- std::back_inserter(header),
- Integer(index.end() - index.begin()));
-
- link_components(index.begin(), header.begin(),
- Integer(index.end() - index.begin()),
- Integer(header.end() - header.begin()));
- }
-
-
-
- template <class IndexIterator, class Integer, class Distance>
- class component_iterator
- : boost::forward_iterator_helper<
- component_iterator<IndexIterator,Integer,Distance>,
- Integer, Distance,Integer*, Integer&>
- {
public:
- typedef component_iterator self;
-
- IndexIterator next;
- Integer node;
-
typedef std::forward_iterator_tag iterator_category;
- typedef Integer value_type;
- typedef Integer& reference;
- typedef Integer* pointer;
- typedef Distance difference_type;
-
- component_iterator() {}
- component_iterator(IndexIterator x, Integer i)
- : next(x), node(i) {}
- Integer operator*() const {
- return node;
+ typedef typename std::iterator_traits<IndexRandomAccessIterator>::value_type value_type;
+ typedef typename std::iterator_traits<IndexRandomAccessIterator>::difference_type reference;
+ typedef typename std::iterator_traits<IndexRandomAccessIterator>::pointer pointer;
+ typedef typename std::iterator_traits<IndexRandomAccessIterator>::reference difference_type;
+
+ // Constructor for "begin" iterator
+ component_index_iterator(IndexRandomAccessIterator index_iterator,
+ value_type begin_index) :
+ m_index_iterator(index_iterator),
+ m_current_index(begin_index) { }
+
+ // Constructor for "end" iterator (end_index should be the linked
+ // list terminator).
+ component_index_iterator(value_type end_index) :
+ m_current_index(end_index) { }
+
+ inline value_type operator*() const {
+ return (m_current_index);
}
+
self& operator++() {
- node = next[node];
- return *this;
+ // Move to the next element in the linked list
+ m_current_index = m_index_iterator[m_current_index];
+ return (*this);
}
- };
-
- template <class IndexIterator, class Integer, class Distance>
- inline bool
- operator==(const component_iterator<IndexIterator, Integer, Distance>& x,
- const component_iterator<IndexIterator, Integer, Distance>& y)
- {
- return x.node == y.node;
- }
-
+
+ bool operator==(self& other_iterator) {
+ return (m_current_index == *other_iterator);
+ }
+
+ protected:
+ IndexRandomAccessIterator m_index_iterator;
+ value_type m_current_index;
+
+ }; // class component_index_iterator
+
} // namespace detail
} // namespace detail
Modified: trunk/boost/graph/incremental_components.hpp
==============================================================================
--- trunk/boost/graph/incremental_components.hpp (original)
+++ trunk/boost/graph/incremental_components.hpp 2009-09-04 10:49:24 EDT (Fri, 04 Sep 2009)
@@ -1,7 +1,8 @@
//
//=======================================================================
// Copyright 1997-2001 University of Notre Dame.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -14,6 +15,9 @@
#include <boost/detail/iterator.hpp>
#include <boost/graph/detail/incremental_components.hpp>
+#include <boost/iterator/counting_iterator.hpp>
+#include <boost/make_shared.hpp>
+#include <boost/pending/disjoint_sets.hpp>
namespace boost {
@@ -42,11 +46,6 @@
// similar to the algorithm described in Ch. 22 of "Intro to
// Algorithms" by Cormen, et. all.
//
- // RankContainer is a random accessable container (operator[] is
- // defined) with a value type that can represent an integer part of
- // a binary log of the value type of the corresponding
- // ParentContainer (char is always enough) its size_type is no less
- // than the size_type of the corresponding ParentContainer
// An implementation of disjoint sets can be found in
// boost/pending/disjoint_sets.hpp
@@ -101,70 +100,131 @@
return ds.find_set(u) == ds.find_set(v);
}
- // considering changing the so that it initializes with a pair of
- // vertex iterators and a parent PA.
-
- template <class IndexT>
- class component_index
- {
- public://protected: (avoid friends for now)
- typedef std::vector<IndexT> MyIndexContainer;
- MyIndexContainer header;
- MyIndexContainer index;
- typedef typename MyIndexContainer::size_type SizeT;
- typedef typename MyIndexContainer::const_iterator IndexIter;
+ // Class that builds a quick-access indexed linked list that allows
+ // for fast iterating through a parent component's children.
+ template <typename IndexType>
+ class component_index {
+
+ private:
+ typedef std::vector<IndexType> IndexContainer;
+
public:
- typedef detail::component_iterator<IndexIter, IndexT, SizeT>
+ typedef counting_iterator<IndexType> iterator;
+ typedef iterator const_iterator;
+ typedef IndexType value_type;
+ typedef IndexType size_type;
+
+ typedef detail::component_index_iterator<typename IndexContainer::iterator>
component_iterator;
- class component {
- friend class component_index;
- protected:
- IndexT number;
- const component_index<IndexT>* comp_ind_ptr;
- component(IndexT i, const component_index<IndexT>* p)
- : number(i), comp_ind_ptr(p) {}
- public:
- typedef component_iterator iterator;
- typedef component_iterator const_iterator;
- typedef IndexT value_type;
- iterator begin() const {
- return iterator( comp_ind_ptr->index.begin(),
- (comp_ind_ptr->header)[number] );
- }
- iterator end() const {
- return iterator( comp_ind_ptr->index.begin(),
- comp_ind_ptr->index.size() );
- }
- };
- typedef SizeT size_type;
- typedef component value_type;
-
-#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
- template <class Iterator>
- component_index(Iterator first, Iterator last)
- : index(std::distance(first, last))
- {
- std::copy(first, last, index.begin());
- detail::construct_component_index(index, header);
+
+ public:
+ template <typename ParentIterator,
+ typename ElementIndexMap>
+ component_index(ParentIterator parent_start,
+ ParentIterator parent_end,
+ const ElementIndexMap& index_map) :
+ m_num_elements(std::distance(parent_start, parent_end)),
+ m_components(make_shared<IndexContainer>()),
+ m_index_list(make_shared<IndexContainer>(m_num_elements)) {
+
+ build_index_lists(parent_start, index_map);
+
+ } // component_index
+
+ template <typename ParentIterator>
+ component_index(ParentIterator parent_start,
+ ParentIterator parent_end) :
+ m_num_elements(std::distance(parent_start, parent_end)),
+ m_components(make_shared<IndexContainer>()),
+ m_index_list(make_shared<IndexContainer>(m_num_elements)) {
+
+ build_index_lists(parent_start, boost::identity_property_map());
+
+ } // component_index
+
+ // Returns the number of components
+ inline std::size_t size() const {
+ return (m_components->size());
}
-#else
- template <class Iterator>
- component_index(Iterator first, Iterator last)
- : index(first, last)
- {
- detail::construct_component_index(index, header);
+
+ // Beginning iterator for component indices
+ iterator begin() const {
+ return (iterator(0));
}
-#endif
- component operator[](IndexT i) const {
- return component(i, this);
+ // End iterator for component indices
+ iterator end() const {
+ return (iterator(this->size()));
}
- SizeT size() const {
- return header.size();
+
+ // Returns a pair of begin and end iterators for the child
+ // elements of component [component_index].
+ std::pair<component_iterator, component_iterator>
+ operator[](IndexType component_index) const {
+
+ IndexType first_index = (*m_components)[component_index];
+
+ return (std::make_pair
+ (component_iterator(m_index_list->begin(), first_index),
+ component_iterator(m_num_elements)));
}
-
- };
+ private:
+ template <typename ParentIterator,
+ typename ElementIndexMap>
+ void build_index_lists(ParentIterator parent_start,
+ const ElementIndexMap& index_map) {
+
+ typedef typename ParentIterator::value_type Element;
+ typename IndexContainer::iterator index_list =
+ m_index_list->begin();
+
+ // First pass - find root elements, construct index list
+ for (IndexType element_index = 0; element_index < m_num_elements;
+ ++element_index) {
+
+ Element parent_element = parent_start[element_index];
+ IndexType parent_index = get(index_map, parent_element);
+
+ if (element_index != parent_index) {
+ index_list[element_index] = parent_index;
+ }
+ else {
+ m_components->push_back(element_index);
+
+ // m_num_elements is the linked list terminator
+ index_list[element_index] = m_num_elements;
+ }
+ }
+
+ // Second pass - build linked list
+ for (IndexType element_index = 0; element_index < m_num_elements;
+ ++element_index) {
+
+ Element parent_element = parent_start[element_index];
+ IndexType parent_index = get(index_map, parent_element);
+
+ if (element_index != parent_index) {
+
+ // Follow list until a component parent is found
+ while (index_list[parent_index] != m_num_elements) {
+ parent_index = index_list[parent_index];
+ }
+
+ // Push element to the front of the linked list
+ index_list[element_index] = index_list[parent_index];
+ index_list[parent_index] = element_index;
+ }
+ }
+
+ } // build_index_lists
+
+ protected:
+ IndexType m_num_elements;
+ shared_ptr<IndexContainer> m_components, m_index_list;
+
+ }; // class component_index
+
} // namespace boost
#endif // BOOST_INCREMENTAL_COMPONENTS_HPP
Modified: trunk/libs/graph/doc/incremental_components.html
==============================================================================
--- trunk/libs/graph/doc/incremental_components.html (original)
+++ trunk/libs/graph/doc/incremental_components.html 2009-09-04 10:49:24 EDT (Fri, 04 Sep 2009)
@@ -8,6 +8,18 @@
-->
<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"
@@ -88,58 +100,77 @@
href="../example/incremental_components.cpp"><TT>examples/incremental_components.cpp</TT></a>.
<P>
-<PRE>
-typedef adjacency_list <vecS, vecS, undirectedS> Graph;
-typedef graph_traits<Graph>::vertex_descriptor Vertex;
-typedef graph_traits<Graph>::vertices_size_type size_type;
-
-const int N = 6;
-Graph G(N);
-
-std::vector<size_type> rank(num_vertices(G));
-std::vector<Vertex> parent(num_vertices(G));
-typedef size_type* Rank;
-typedef Vertex* Parent;
-disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
-
-initialize_incremental_components(G, ds);
-incremental_components(G, ds);
-
-graph_traits<Graph>::edge_descriptor e;
-bool flag;
-boost::tie(e,flag) = add_edge(0, 1, G);
-ds.union_set(0,1);
-
-boost::tie(e,flag) = add_edge(1, 4, G);
-ds.union_set(1,4);
-
-boost::tie(e,flag) = add_edge(4, 0, G);
-ds.union_set(4,0);
-
-boost::tie(e,flag) = add_edge(2, 5, G);
-ds.union_set(2,5);
-
-cout << "An undirected graph:" << endl;
-print_graph(G, get(vertex_index, G));
-cout << endl;
-
-graph_traits<Graph>::vertex_iterator i,end;
-for (boost::tie(i, end) = vertices(G); i != end; ++i)
- cout << "representative[" << *i << "] = " <<
- ds.find_set(*i) << endl;;
-cout << endl;
-
-typedef component_index<unsigned int> Components;
-Components components(&parent[0], &parent[0] + parent.size());
-
-for (Components::size_type c = 0; c < components.size(); ++c) {
- cout << "component " << c << " contains: ";
- Components::value_type::iterator
- j = components[c].begin(),
- jend = components[c].end();
- for ( ; j != jend; ++j)
- cout << *j << " ";
- cout << endl;
+<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>
@@ -298,12 +329,14 @@
</PRE>
<P>
-The is a class that provides an STL container-like view for the
-components of the graph. Each component is a container-like object,
-and the <TT>component_index</TT> object provides access to the
-component objects via <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.
+<tt>component_index</tt> is a class that 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>
@@ -325,81 +358,47 @@
</tr>
<tr>
-<td><tt>size_type</tt></td>
-<td>The type used for representing the number of components.</td>
-</tr>
-
-
-<tr>
-<td><tt>value_type</tt></td>
-<td>
-The type for a component object. The component type has the following members.
-</td>
-</tr>
-
-<tr>
-<td><tt>value_type::value_type</tt></td>
+<td><tt>value_type/size_type</tt></td>
<td>
-The value type of a component object is a vertex ID.
+The type for a component index (same as <tt>Index</tt>).
</td>
</tr>
<tr>
-<td><tt>value_type::iterator</tt></td>
+<td><tt>size_type size()</tt></td>
<td>
-This iterator can be used to traverse all of the vertices
-in the component. This iterator dereferences to give a vertex ID.
+Returns the number of components in the graph.
</td>
</tr>
-<tr>
-<td><tt>value_type::const_iterator</tt></td>
-<td>
-The const iterator.
-</td>
-</tr>
<tr>
-<td><tt>value_type::iterator value_type::begin() const</tt></td>
+<td><tt>iterator/const_iterator</tt></td>
<td>
-Return an iterator pointing to the first vertex in the component.
+Iterators used to traverse the available component indices [0 to <tt>size()</tt>).
</td>
</tr>
<tr>
-<td><tt>value_type::iterator value_type::end() const</tt></td>
+<td><tt>iterator begin() const</tt></td>
<td>
-Return an iterator pointing past the end of the last vertex in the
-component.
-</td>
-<tr>
-
-<tr>
-<td>
-<tt>
-template <class ComponentsContainer>
-component_index(const ComponentsContainer& c)
-</tt>
-</td>
-<td>
-Construct the <TT>component_index</TT> using the information
-from the components container <TT>c</TT> which was the result
-of executing <TT>connected_components_on_edgelist</TT>.
+Returns an iterator at the start of the component indices (0).
</td>
</tr>
<tr>
-<td><tt>value_type operator[](size_type i)</tt></td>
+<td><tt>iterator end() const</tt></td>
<td>
-Returns the <TT>i</TT>th component in the graph.
+Returns an iterator past the end of the component indices (<tt>size()</tt>).
</td>
</tr>
-
+
<tr>
-<td><tt>size_type component_index::size()</tt></td>
+<td><tt>std::pair<component_iterator, component_iterator> operator[size_type index] const</tt></td>
<td>
-Returns the number of components in the graph.
+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>
Modified: trunk/libs/graph/example/incremental-components-eg.cpp
==============================================================================
--- trunk/libs/graph/example/incremental-components-eg.cpp (original)
+++ trunk/libs/graph/example/incremental-components-eg.cpp 2009-09-04 10:49:24 EDT (Fri, 04 Sep 2009)
@@ -1,64 +1,84 @@
//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
//
// 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)
//=======================================================================
-#include <boost/config.hpp>
+
#include <iostream>
#include <vector>
-#include <algorithm>
-#include <utility>
+
+#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
-#include <boost/pending/disjoint_sets.hpp>
#include <boost/graph/incremental_components.hpp>
+#include <boost/pending/disjoint_sets.hpp>
-int
-main(int, char *[])
+using namespace boost;
+
+int main(int argc, char* argv[])
{
- using namespace boost;
+ typedef adjacency_list <vecS, vecS, undirectedS> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef graph_traits<Graph>::edge_descriptor Edge;
+ typedef graph_traits<Graph>::vertices_size_type VertexIndex;
+
// Create a graph
- typedef adjacency_list < vecS, vecS, undirectedS > Graph;
- typedef graph_traits < Graph >::vertex_descriptor Vertex;
- const int N = 6;
- Graph G(N);
- add_edge(0, 1, G);
- add_edge(1, 4, G);
- // create the disjoint-sets object, which requires rank and parent vertex properties
- std::vector < Vertex > rank(num_vertices(G));
- std::vector < Vertex > parent(num_vertices(G));
- typedef graph_traits<Graph>::vertices_size_type* Rank;
+ const int VERTEX_COUNT = 6;
+ Graph graph(VERTEX_COUNT);
+
+ add_edge(0, 1, graph);
+ add_edge(1, 4, graph);
+
+ // reate the disjoint-sets object, which requires rank and parent
+ // vertex properties.
+ std::vector<Vertex> 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]);
+ disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
- // determine the connected components, storing the results in the disjoint-sets object
- initialize_incremental_components(G, ds);
- incremental_components(G, ds);
+ // Determine the connected components, storing the results in the
+ // disjoint-sets object.
+ initialize_incremental_components(graph, ds);
+ incremental_components(graph, ds);
// Add a couple more edges and update the disjoint-sets
- graph_traits < Graph >::edge_descriptor e;
- bool flag;
- tie(e, flag) = add_edge(4, 0, G);
+ add_edge(4, 0, graph);
+ add_edge(2, 5, graph);
+
ds.union_set(4, 0);
- tie(e, flag) = add_edge(2, 5, G);
ds.union_set(2, 5);
- graph_traits < Graph >::vertex_iterator iter, end;
- for (tie(iter, end) = vertices(G); iter != end; ++iter)
- std::cout << "representative[" << *iter << "] = " <<
- ds.find_set(*iter) << 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 < unsigned int >Components;
+ // Generate component index. NOTE: We would need to pass in a vertex
+ // index map into the component_index constructor if our graph type
+ // used listS instead of vecS (identity_property_map is used by
+ // default).
+ typedef component_index<VertexIndex> Components;
Components components(parent.begin(), parent.end());
- for (Components::size_type i = 0; i < components.size(); ++i) {
- std::cout << "component " << i << " contains: ";
- for (Components::value_type::iterator j = components[i].begin();
- j != components[i].end(); ++j)
- std::cout << *j << " ";
+
+ // Iterate through the component indices
+ BOOST_FOREACH(VertexIndex component_index, components) {
+ std::cout << "component " << component_index << " contains: ";
+
+ // Iterate through the child vertex indices for [component_index]
+ BOOST_FOREACH(VertexIndex child_index,
+ components[component_index]) {
+ std::cout << child_index << " ";
+ }
+
std::cout << std::endl;
}
- return EXIT_SUCCESS;
+ return (0);
}
Modified: trunk/libs/graph/example/incremental_components.cpp
==============================================================================
--- trunk/libs/graph/example/incremental_components.cpp (original)
+++ trunk/libs/graph/example/incremental_components.cpp 2009-09-04 10:49:24 EDT (Fri, 04 Sep 2009)
@@ -1,20 +1,20 @@
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
//
// 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)
//=======================================================================
-#include <boost/config.hpp>
#include <iostream>
#include <vector>
-#include <algorithm>
-#include <utility>
-#include <boost/graph/graph_utility.hpp>
+
+#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
-#include <boost/pending/disjoint_sets.hpp>
+#include <boost/graph/graph_utility.hpp>
#include <boost/graph/incremental_components.hpp>
+#include <boost/pending/disjoint_sets.hpp>
/*
@@ -45,64 +45,75 @@
*/
-using namespace std;
+using namespace boost;
-int main(int , char* [])
+int main(int argc, char* argv[])
{
- using namespace boost;
typedef adjacency_list <vecS, vecS, undirectedS> Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef graph_traits<Graph>::vertices_size_type size_type;
+ typedef graph_traits<Graph>::vertices_size_type VertexIndex;
+
+ const int VERTEX_COUNT = 6;
+ Graph graph(VERTEX_COUNT);
- const int N = 6;
- Graph G(N);
+ std::vector<VertexIndex> rank(num_vertices(graph));
+ std::vector<Vertex> parent(num_vertices(graph));
- std::vector<size_type> rank(num_vertices(G));
- std::vector<Vertex> parent(num_vertices(G));
- typedef size_type* Rank;
+ typedef VertexIndex* Rank;
typedef Vertex* Parent;
- disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
- initialize_incremental_components(G, ds);
- incremental_components(G, ds);
+ disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
+
+ initialize_incremental_components(graph, ds);
+ incremental_components(graph, ds);
- graph_traits<Graph>::edge_descriptor e;
+ graph_traits<Graph>::edge_descriptor edge;
bool flag;
- boost::tie(e,flag) = add_edge(0, 1, G);
+
+ boost::tie(edge, flag) = add_edge(0, 1, graph);
ds.union_set(0,1);
- boost::tie(e,flag) = add_edge(1, 4, G);
+ boost::tie(edge, flag) = add_edge(1, 4, graph);
ds.union_set(1,4);
- boost::tie(e,flag) = add_edge(4, 0, G);
+ boost::tie(edge, flag) = add_edge(4, 0, graph);
ds.union_set(4,0);
- boost::tie(e,flag) = add_edge(2, 5, G);
+ boost::tie(edge, flag) = add_edge(2, 5, graph);
ds.union_set(2,5);
- cout << "An undirected graph:" << endl;
- print_graph(G, get(vertex_index, G));
- cout << endl;
+ std::cout << "An undirected graph:" << std::endl;
+ print_graph(graph, get(boost::vertex_index, graph));
+ std::cout << std::endl;
- graph_traits<Graph>::vertex_iterator i,end;
- for (boost::tie(i, end) = vertices(G); i != end; ++i)
- cout << "representative[" << *i << "] = " <<
- ds.find_set(*i) << endl;;
- cout << endl;
-
- typedef component_index<unsigned int> Components;
- Components components(&parent[0], &parent[0] + parent.size());
-
- for (Components::size_type c = 0; c < components.size(); ++c) {
- cout << "component " << c << " contains: ";
- Components::value_type::iterator
- j = components[c].begin(),
- jend = components[c].end();
- for ( ; j != jend; ++j)
- cout << *j << " ";
- cout << 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
+ // explicitly 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;
+ return (0);
}
Modified: trunk/libs/graph/example/incremental_components.expected
==============================================================================
--- trunk/libs/graph/example/incremental_components.expected (original)
+++ trunk/libs/graph/example/incremental_components.expected 2009-09-04 10:49:24 EDT (Fri, 04 Sep 2009)
@@ -13,6 +13,6 @@
representative[4] = 1
representative[5] = 5
-component 0 contains: 4 1 0
+component 0 contains: 1 4 0
component 1 contains: 3
component 2 contains: 5 2
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2009-09-04 10:49:24 EDT (Fri, 04 Sep 2009)
@@ -121,6 +121,7 @@
[ run mcgregor_subgraphs_test.cpp ]
[ compile grid_graph_cc.cpp ]
[ run grid_graph_test.cpp ]
+ [ run incremental_components_test.cpp ]
$(optional_tests)
;
Added: trunk/libs/graph/test/incremental_components_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/incremental_components_test.cpp 2009-09-04 10:49:24 EDT (Fri, 04 Sep 2009)
@@ -0,0 +1,162 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen, Andrew Lumsdaine
+//
+// 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)
+//=======================================================================
+
+#include <iostream>
+#include <map>
+#include <set>
+
+#include <boost/foreach.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/incremental_components.hpp>
+#include <boost/graph/random.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/property_map.hpp>
+#include <boost/random.hpp>
+#include <boost/test/minimal.hpp>
+
+using namespace boost;
+
+typedef adjacency_list<vecS, vecS, undirectedS> VectorGraph;
+
+typedef adjacency_list<listS, listS, undirectedS,
+ property<vertex_index_t, unsigned int> > ListGraph;
+
+template <typename Graph>
+void test_graph(const Graph& graph) {
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+ typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
+
+ typedef typename property_map<Graph, vertex_index_t>::type IndexPropertyMap;
+
+ typedef std::map<vertex_descriptor, vertices_size_type> RankMap;
+ typedef associative_property_map<RankMap> RankPropertyMap;
+
+ typedef std::vector<vertex_descriptor> ParentMap;
+ typedef iterator_property_map<typename ParentMap::iterator,
+ IndexPropertyMap, vertex_descriptor, vertex_descriptor&> IndexParentMap;
+
+ RankMap rank_map;
+ RankPropertyMap rank_property_map(rank_map);
+
+ ParentMap parent_map(num_vertices(graph));
+ IndexParentMap index_parent_map(parent_map.begin());
+
+ // Create disjoint sets of vertices from the graph
+ disjoint_sets<RankPropertyMap, IndexParentMap>
+ vertex_sets(rank_property_map, index_parent_map);
+
+ initialize_incremental_components(graph, vertex_sets);
+ incremental_components(graph, vertex_sets);
+
+ // Build component index from the graph's vertices, its index map,
+ // and the disjoint sets.
+ typedef component_index<vertices_size_type> Components;
+ Components vertex_components(parent_map.begin(),
+ parent_map.end(),
+ get(boost::vertex_index, graph));
+
+ // Create a reverse-lookup map for vertex indices
+ std::vector<vertex_descriptor> reverse_index_map(num_vertices(graph));
+
+ BOOST_FOREACH(vertex_descriptor vertex, vertices(graph)) {
+ reverse_index_map[get(get(boost::vertex_index, graph), vertex)] = vertex;
+ }
+
+ // Verify that components are really connected
+ BOOST_FOREACH(vertices_size_type component_index,
+ vertex_components) {
+
+ std::set<vertex_descriptor> component_vertices;
+
+ BOOST_FOREACH(vertices_size_type child_index,
+ vertex_components[component_index]) {
+
+ vertex_descriptor child_vertex = reverse_index_map[child_index];
+ component_vertices.insert(child_vertex);
+
+ } // foreach child_index
+
+ // Verify that children are connected to each other in some
+ // manner, but not to vertices outside their component.
+ BOOST_FOREACH(vertex_descriptor child_vertex,
+ component_vertices) {
+
+ // Skip orphan vertices
+ if (out_degree(child_vertex, graph) == 0) {
+ continue;
+ }
+
+ // Make sure at least one edge exists between [child_vertex] and
+ // another vertex in the component.
+ bool edge_exists = false;
+
+ BOOST_FOREACH(edge_descriptor child_edge,
+ out_edges(child_vertex, graph)) {
+
+ if (component_vertices.count(target(child_edge, graph)) > 0) {
+ edge_exists = true;
+ break;
+ }
+
+ } // foreach child_edge
+
+ BOOST_REQUIRE(edge_exists);
+
+ } // foreach child_vertex
+
+ } // foreach component_index
+
+} // test_graph
+
+int test_main(int argc, char* argv[])
+{
+ std::size_t vertices_to_generate = 100,
+ edges_to_generate = 50,
+ random_seed = time(0);
+
+ // Parse command-line arguments
+
+ if (argc > 1) {
+ vertices_to_generate = lexical_cast<std::size_t>(argv[1]);
+ }
+
+ if (argc > 2) {
+ edges_to_generate = lexical_cast<std::size_t>(argv[2]);
+ }
+
+ if (argc > 3) {
+ random_seed = lexical_cast<std::size_t>(argv[3]);
+ }
+
+ minstd_rand generator(random_seed);
+
+ // Generate random vector and list graphs
+ VectorGraph vector_graph;
+ generate_random_graph(vector_graph, vertices_to_generate,
+ edges_to_generate, generator, false);
+
+ test_graph(vector_graph);
+
+ ListGraph list_graph;
+ generate_random_graph(list_graph, vertices_to_generate,
+ edges_to_generate, generator, false);
+
+ // Assign indices to list_graph's vertices
+ graph_traits<ListGraph>::vertices_size_type index = 0;
+ BOOST_FOREACH(graph_traits<ListGraph>::vertex_descriptor vertex,
+ vertices(list_graph)) {
+ put(get(boost::vertex_index, list_graph), vertex, index++);
+ }
+
+ test_graph(list_graph);
+
+ return 0;
+
+}