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