[Boost-commit] svn:boost r56015 - in trunk: boost/graph boost/graph/detail libs/graph/doc libs/graph/example libs/graph/test

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 &lt;vecS, vecS, undirectedS&gt; Graph;
-typedef graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
-typedef graph_traits&lt;Graph&gt;::vertices_size_type size_type;
-
-const int N = 6;
-Graph G(N);
-
-std::vector&lt;size_type&gt; rank(num_vertices(G));
-std::vector&lt;Vertex&gt; parent(num_vertices(G));
-typedef size_type* Rank;
-typedef Vertex* Parent;
-disjoint_sets&lt;Rank, Parent&gt;  ds(&amp;rank[0], &amp;parent[0]);
-
-initialize_incremental_components(G, ds);
-incremental_components(G, ds);
-
-graph_traits&lt;Graph&gt;::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 &lt;&lt; &quot;An undirected graph:&quot; &lt;&lt; endl;
-print_graph(G, get(vertex_index, G));
-cout &lt;&lt; endl;
-
-graph_traits&lt;Graph&gt;::vertex_iterator i,end;
-for (boost::tie(i, end) = vertices(G); i != end; ++i)
-  cout &lt;&lt; &quot;representative[&quot; &lt;&lt; *i &lt;&lt; &quot;] = &quot; &lt;&lt; 
-    ds.find_set(*i) &lt;&lt; endl;;
-cout &lt;&lt; endl;
-
-typedef component_index&lt;unsigned int&gt; Components;
-Components components(&amp;parent[0], &amp;parent[0] + parent.size());
-
-for (Components::size_type c = 0; c &lt; components.size(); ++c) {
-  cout &lt;&lt; &quot;component &quot; &lt;&lt; c &lt;&lt; &quot; contains: &quot;;
-  Components::value_type::iterator
-    j = components[c].begin(),
-    jend = components[c].end();
-  for ( ; j != jend; ++j)
-    cout &lt;&lt; *j &lt;&lt; &quot; &quot;;
-  cout &lt;&lt; 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 &lt;class ComponentsContainer&gt;
-component_index(const ComponentsContainer&amp; 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&lt;component_iterator, component_iterator&gt; 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;
+
+}