graph/detail/connected_components.hpp

//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// 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_GRAPH_DETAIL_CONNECTED_COMPONENTS_HPP
#define BOOST_GRAPH_DETAIL_CONNECTED_COMPONENTS_HPP

#if defined(__sgi) && !defined(__GNUC__)
#pragma set woff 1234
#endif

#include <boost/operators.hpp>

namespace boost {

  namespace detail {

    //=========================================================================
    // Implementation details of connected_components

    // This is used both in the connected_components algorithm and in
    // the kosaraju strong components algorithm during the second DFS
    // traversal.
    template <class ComponentsPA, class DFSVisitor>
    class components_recorder : public DFSVisitor
    {
      typedef typename property_traits<ComponentsPA>::value_type comp_type;
    public:
      components_recorder(ComponentsPA c,
                          comp_type& c_count,
                          DFSVisitor v)
        : DFSVisitor(v), m_component(c), m_count(c_count) {}

      template <class Vertex, class Graph>
      void start_vertex(Vertex u, Graph& g) {
        ++m_count;
        DFSVisitor::start_vertex(u, g);
      }
      template <class Vertex, class Graph>
      void discover_vertex(Vertex u, Graph& g) {
        put(m_component, u, m_count);
        DFSVisitor::discover_vertex(u, g);
      }
    protected:
      ComponentsPA m_component;
      comp_type& m_count;
    };

    template <class DiscoverTimeMap, class FinishTimeMap, class TimeT,
      class DFSVisitor>
    class time_recorder : public DFSVisitor
    {
    public:
      time_recorder(DiscoverTimeMap d, FinishTimeMap f, TimeT& t, DFSVisitor v)
        : DFSVisitor(v), m_discover_time(d), m_finish_time(f), m_t(t) {}

      template <class Vertex, class Graph>
      void discover_vertex(Vertex u, Graph& g) {
        put(m_discover_time, u, ++m_t);
        DFSVisitor::discover_vertex(u, g);
      }
      template <class Vertex, class Graph>
      void finish_vertex(Vertex u, Graph& g) {
        put(m_finish_time, u, ++m_t);
        DFSVisitor::discover_vertex(u, g);
      }
    protected:
      DiscoverTimeMap m_discover_time;
      FinishTimeMap m_finish_time;
      TimeT m_t;
    };
    template <class DiscoverTimeMap, class FinishTimeMap, class TimeT,
      class DFSVisitor>
    time_recorder<DiscoverTimeMap, FinishTimeMap, TimeT, DFSVisitor>
    record_times(DiscoverTimeMap d, FinishTimeMap f, TimeT& t, DFSVisitor vis)
    {
      return time_recorder<DiscoverTimeMap, FinishTimeMap, TimeT, DFSVisitor>
        (d, f, t, vis);
    }

    //=========================================================================
    // Implementation detail of dynamic_components


    //-------------------------------------------------------------------------
    // 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 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)
        push_front(next, header[component[k]], k);
    }


    template <class IndexContainer, class HeaderContainer>
    void
    construct_component_index(IndexContainer& index, HeaderContainer& header)
    {
      build_components_header(index.begin(),
                              std::back_inserter(header),
                              index.end() - index.begin());

      link_components(index.begin(), header.begin(),
                      index.end() - index.begin(),
                      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;
      }
      self& operator++() {
        node = next[node];
        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;
    }

  } // namespace detail

} // namespace detail

#if defined(__sgi) && !defined(__GNUC__)
#pragma reset woff 1234
#endif

#endif