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