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