Chris@16: //=======================================================================
Chris@16: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: #ifndef BOOST_GRAPH_DETAIL_CONNECTED_COMPONENTS_HPP
Chris@16: #define BOOST_GRAPH_DETAIL_CONNECTED_COMPONENTS_HPP
Chris@16: 
Chris@16: #if defined(__sgi) && !defined(__GNUC__)
Chris@16: #pragma set woff 1234
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/operators.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Implementation details of connected_components
Chris@16: 
Chris@16:     // This is used both in the connected_components algorithm and in
Chris@16:     // the kosaraju strong components algorithm during the second DFS
Chris@16:     // traversal.
Chris@16:     template <class ComponentsPA, class DFSVisitor>
Chris@16:     class components_recorder : public DFSVisitor
Chris@16:     {
Chris@16:       typedef typename property_traits<ComponentsPA>::value_type comp_type;
Chris@16:     public:
Chris@16:       components_recorder(ComponentsPA c, 
Chris@16:                           comp_type& c_count, 
Chris@16:                           DFSVisitor v)
Chris@16:         : DFSVisitor(v), m_component(c), m_count(c_count) {}
Chris@16: 
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void start_vertex(Vertex u, Graph& g) {
Chris@16:         ++m_count;
Chris@16:         DFSVisitor::start_vertex(u, g);
Chris@16:       }
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void discover_vertex(Vertex u, Graph& g) {
Chris@16:         put(m_component, u, m_count);
Chris@16:         DFSVisitor::discover_vertex(u, g);
Chris@16:       }
Chris@16:     protected:
Chris@16:       ComponentsPA m_component;
Chris@16:       comp_type& m_count;
Chris@16:     };
Chris@16: 
Chris@16:     template <class DiscoverTimeMap, class FinishTimeMap, class TimeT, 
Chris@16:       class DFSVisitor>
Chris@16:     class time_recorder : public DFSVisitor
Chris@16:     {
Chris@16:     public:
Chris@16:       time_recorder(DiscoverTimeMap d, FinishTimeMap f, TimeT& t, DFSVisitor v)
Chris@16:         : DFSVisitor(v), m_discover_time(d), m_finish_time(f), m_t(t) {}
Chris@16: 
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void discover_vertex(Vertex u, Graph& g) {
Chris@16:         put(m_discover_time, u, ++m_t);
Chris@16:         DFSVisitor::discover_vertex(u, g);
Chris@16:       }
Chris@16:       template <class Vertex, class Graph>
Chris@16:       void finish_vertex(Vertex u, Graph& g) {
Chris@16:         put(m_finish_time, u, ++m_t);
Chris@16:         DFSVisitor::discover_vertex(u, g);
Chris@16:       }
Chris@16:     protected:
Chris@16:       DiscoverTimeMap m_discover_time;
Chris@16:       FinishTimeMap m_finish_time;
Chris@16:       TimeT m_t;
Chris@16:     };
Chris@16:     template <class DiscoverTimeMap, class FinishTimeMap, class TimeT, 
Chris@16:       class DFSVisitor>
Chris@16:     time_recorder<DiscoverTimeMap, FinishTimeMap, TimeT, DFSVisitor>
Chris@16:     record_times(DiscoverTimeMap d, FinishTimeMap f, TimeT& t, DFSVisitor vis)
Chris@16:     {
Chris@16:       return time_recorder<DiscoverTimeMap, FinishTimeMap, TimeT, DFSVisitor>
Chris@16:         (d, f, t, vis);
Chris@16:     }
Chris@16: 
Chris@16:     //=========================================================================
Chris@16:     // Implementation detail of dynamic_components
Chris@16: 
Chris@16: 
Chris@16:     //-------------------------------------------------------------------------
Chris@16:     // Helper functions for the component_index class
Chris@16:     
Chris@16:     // Record the representative vertices in the header array.
Chris@16:     // Representative vertices now point to the component number.
Chris@16:     
Chris@16:     template <class Parent, class OutputIterator, class Integer>
Chris@16:     inline void
Chris@16:     build_components_header(Parent p, 
Chris@16:                             OutputIterator header,
Chris@16:                             Integer num_nodes)
Chris@16:     {
Chris@16:       Parent component = p;
Chris@16:       Integer component_num = 0;
Chris@16:       for (Integer v = 0; v != num_nodes; ++v) 
Chris@16:         if (p[v] == v) {
Chris@16:           *header++ = v;
Chris@16:           component[v] = component_num++;
Chris@16:         }
Chris@16:     }
Chris@16:     
Chris@16:     
Chris@16:     // Pushes x onto the front of the list. The list is represented in
Chris@16:     // an array.
Chris@16:     template <class Next, class T, class V>
Chris@16:     inline void push_front(Next next, T& head, V x)
Chris@16:     {
Chris@16:       T tmp = head;
Chris@16:       head = x;
Chris@16:       next[x] = tmp;
Chris@16:     }
Chris@16:     
Chris@16:     
Chris@16:     // Create a linked list of the vertices in each component
Chris@16:     // by reusing the representative array.
Chris@16:     template <class Parent1, class Parent2, 
Chris@16:               class Integer>
Chris@16:     void
Chris@16:     link_components(Parent1 component, Parent2 header, 
Chris@16:                     Integer num_nodes, Integer num_components)
Chris@16:     {
Chris@16:       // Make the non-representative vertices point to their component
Chris@16:       Parent1 representative = component;
Chris@16:       for (Integer v = 0; v != num_nodes; ++v)
Chris@16:         if (component[v] >= num_components || header[component[v]] != v)
Chris@16:           component[v] = component[representative[v]];
Chris@16:       
Chris@16:       // initialize the "head" of the lists to "NULL"
Chris@16:       std::fill_n(header, num_components, num_nodes);
Chris@16:       
Chris@16:       // Add each vertex to the linked list for its component
Chris@16:       Parent1 next = component;
Chris@16:       for (Integer k = 0; k != num_nodes; ++k)
Chris@16:         push_front(next, header[component[k]], k);
Chris@16:     }
Chris@16:     
Chris@16: 
Chris@16:     
Chris@16:     template <class IndexContainer, class HeaderContainer>
Chris@16:     void
Chris@16:     construct_component_index(IndexContainer& index, HeaderContainer& header)
Chris@16:     {
Chris@16:       build_components_header(index.begin(), 
Chris@16:                               std::back_inserter(header),
Chris@16:                               index.end() - index.begin());
Chris@16:       
Chris@16:       link_components(index.begin(), header.begin(),
Chris@16:                       index.end() - index.begin(), 
Chris@16:                       header.end() - header.begin());
Chris@16:     }
Chris@16:     
Chris@16:     
Chris@16:     
Chris@16:     template <class IndexIterator, class Integer, class Distance>
Chris@16:     class component_iterator 
Chris@16:       : boost::forward_iterator_helper< 
Chris@16:     component_iterator<IndexIterator,Integer,Distance>,
Chris@16:               Integer, Distance,Integer*, Integer&>
Chris@16:     {
Chris@16:     public:
Chris@16:       typedef component_iterator self;
Chris@16:       
Chris@16:       IndexIterator next;
Chris@16:       Integer node;
Chris@16:       
Chris@16:       typedef std::forward_iterator_tag iterator_category;
Chris@16:       typedef Integer value_type;
Chris@16:       typedef Integer& reference;
Chris@16:       typedef Integer* pointer;
Chris@16:       typedef Distance difference_type;
Chris@16:       
Chris@16:       component_iterator() {}
Chris@16:       component_iterator(IndexIterator x, Integer i) 
Chris@16:         : next(x), node(i) {}
Chris@16:       Integer operator*() const {
Chris@16:         return node;
Chris@16:       }
Chris@16:       self& operator++() {
Chris@16:         node = next[node];
Chris@16:         return *this;
Chris@16:       }
Chris@16:     };
Chris@16:     
Chris@16:     template <class IndexIterator, class Integer, class Distance>
Chris@16:     inline bool 
Chris@16:     operator==(const component_iterator<IndexIterator, Integer, Distance>& x,
Chris@16:                const component_iterator<IndexIterator, Integer, Distance>& y)
Chris@16:     {
Chris@16:       return x.node == y.node;
Chris@16:     }
Chris@16:   
Chris@16:   } // namespace detail
Chris@16:   
Chris@16: } // namespace detail
Chris@16: 
Chris@16: #if defined(__sgi) && !defined(__GNUC__)
Chris@16: #pragma reset woff 1234
Chris@16: #endif
Chris@16: 
Chris@16: #endif