robot/include/boost/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