http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/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