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