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/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>
#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 boost::detail::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