robot/include/boost/graph/incremental_components.hpp

//
//=======================================================================
// 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 <boost/tuple/tuple.hpp>
#include <boost/graph/detail/incremental_components.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/smart_ptr/make_shared.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <iterator>

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