EIC code displayed by LXR master/​include/​boost/​graph/​detail/​connected_components.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-18 09:37:10

 //=======================================================================
 // 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

This page was automatically generated by the 2.3.7 LXR engine. The LXR team