Edit: /usr/include/boost/graph/incremental_components.hpp (8224B)
//
//=======================================================================
// Copyright 1997-2001 University of Notre Dame.
// 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)
//=======================================================================
//
#ifndef BOOST_INCREMENTAL_COMPONENTS_HPP
#define BOOST_INCREMENTAL_COMPONENTS_HPP
#include
#include
#include
#include
#include
#include
namespace boost
{
// A connected component algorithm for the case when dynamically
// adding (but not removing) edges is common. The
// incremental_components() function is a preparing operation. Call
// same_component to check whether two vertices are in the same
// component, or use disjoint_set::find_set to determine the
// representative for a vertex.
// This version of connected components does not require a full
// Graph. Instead, it just needs an edge list, where the vertices of
// each edge need to be of integer type. The edges are assumed to
// be undirected. The other difference is that the result is stored in
// a container, instead of just a decorator. The container should be
// empty before the algorithm is called. It will grow during the
// course of the algorithm. The container must be a model of
// BackInsertionSequence and RandomAccessContainer
// (std::vector is a good choice). After running the algorithm the
// index container will map each vertex to the representative
// vertex of the component to which it belongs.
//
// Adapted from an implementation by Alex Stepanov. The disjoint
// sets data structure is from Tarjan's "Data Structures and Network
// Algorithms", and the application to connected components is
// similar to the algorithm described in Ch. 22 of "Intro to
// Algorithms" by Cormen, et. all.
//
// An implementation of disjoint sets can be found in
// boost/pending/disjoint_sets.hpp
template < class EdgeListGraph, class DisjointSets >
void incremental_components(EdgeListGraph& g, DisjointSets& ds)
{
typename graph_traits< EdgeListGraph >::edge_iterator e, end;
for (boost::tie(e, end) = edges(g); e != end; ++e)
ds.union_set(source(*e, g), target(*e, g));
}
template < class ParentIterator >
void compress_components(ParentIterator first, ParentIterator last)
{
for (ParentIterator current = first; current != last; ++current)
detail::find_representative_with_full_compression(
first, current - first);
}
template < class ParentIterator >
typename std::iterator_traits< ParentIterator >::difference_type
component_count(ParentIterator first, ParentIterator last)
{
std::ptrdiff_t count = 0;
for (ParentIterator current = first; current != last; ++current)
if (*current == current - first)
++count;
return count;
}
// This algorithm can be applied to the result container of the
// connected_components algorithm to normalize
// the components.
template < class ParentIterator >
void normalize_components(ParentIterator first, ParentIterator last)
{
for (ParentIterator current = first; current != last; ++current)
detail::normalize_node(first, current - first);
}
template < class VertexListGraph, class DisjointSets >
void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
{
typename graph_traits< VertexListGraph >::vertex_iterator v, vend;
for (boost::tie(v, vend) = vertices(G); v != vend; ++v)
ds.make_set(*v);
}
template < class Vertex, class DisjointSet >
inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
{
return ds.find_set(u) == ds.find_set(v);
}
// 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 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;
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()); }
// Beginning iterator for component indices
iterator begin() const { return (iterator(0)); }
// End iterator for component indices
iterator end() const { return (iterator(this->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 std::iterator_traits< 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