// Copyright 2005 The Trustees of Indiana University. | |
// Use, modification and distribution is subject to 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) | |
// Authors: Douglas Gregor | |
// Andrew Lumsdaine | |
// An implementation of Walter Hohberg's distributed biconnected | |
// components algorithm, from: | |
// | |
// Walter Hohberg. How to Find Biconnected Components in Distributed | |
// Networks. J. Parallel Distrib. Comput., 9(4):374-386, 1990. | |
// | |
#ifndef BOOST_GRAPH_DISTRIBUTED_HOHBERG_BICONNECTED_COMPONENTS_HPP | |
#define BOOST_GRAPH_DISTRIBUTED_HOHBERG_BICONNECTED_COMPONENTS_HPP | |
#ifndef BOOST_GRAPH_USE_MPI | |
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
#endif | |
/* You can define PBGL_HOHBERG_DEBUG to an integer value (1, 2, or 3) | |
* to enable debugging information. 1 includes only the phases of the | |
* algorithm and messages as their are received. 2 and 3 add | |
* additional levels of detail about internal data structures related | |
* to the algorithm itself. | |
* | |
* #define PBGL_HOHBERG_DEBUG 1 | |
*/ | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/graph/parallel/container_traits.hpp> | |
#include <boost/graph/parallel/process_group.hpp> | |
#include <boost/static_assert.hpp> | |
#include <boost/mpi/operations.hpp> | |
#include <boost/type_traits/is_convertible.hpp> | |
#include <boost/graph/graph_concepts.hpp> | |
#include <boost/graph/iteration_macros.hpp> | |
#include <boost/optional.hpp> | |
#include <utility> // for std::pair | |
#include <boost/assert.hpp> | |
#include <algorithm> // for std::find, std::mismatch | |
#include <vector> | |
#include <boost/graph/parallel/algorithm.hpp> | |
#include <boost/graph/distributed/connected_components.hpp> | |
namespace boost { namespace graph { namespace distributed { | |
namespace hohberg_detail { | |
enum message_kind { | |
/* A header for the PATH message, stating which edge the message | |
is coming on and how many vertices will be following. The data | |
structure communicated will be a path_header. */ | |
msg_path_header, | |
/* A message containing the vertices that make up a path. It will | |
always follow a msg_path_header and will contain vertex | |
descriptors, only. */ | |
msg_path_vertices, | |
/* A header for the TREE message, stating the value of gamma and | |
the number of vertices to come in the following | |
msg_tree_vertices. */ | |
msg_tree_header, | |
/* A message containing the vertices that make up the set of | |
vertices in the same bicomponent as the sender. It will always | |
follow a msg_tree_header and will contain vertex descriptors, | |
only. */ | |
msg_tree_vertices, | |
/* Provides a name for the biconnected component of the edge. */ | |
msg_name | |
}; | |
// Payload for a msg_path_header message. | |
template<typename EdgeDescriptor> | |
struct path_header | |
{ | |
// The edge over which the path is being communicated | |
EdgeDescriptor edge; | |
// The length of the path, i.e., the number of vertex descriptors | |
// that will be coming in the next msg_path_vertices message. | |
std::size_t path_length; | |
template<typename Archiver> | |
void serialize(Archiver& ar, const unsigned int /*version*/) | |
{ | |
ar & edge & path_length; | |
} | |
}; | |
// Payload for a msg_tree_header message. | |
template<typename Vertex, typename Edge> | |
struct tree_header | |
{ | |
// The edge over which the tree is being communicated | |
Edge edge; | |
// Gamma, which is the eta of the sender. | |
Vertex gamma; | |
// The length of the list of vertices in the bicomponent, i.e., | |
// the number of vertex descriptors that will be coming in the | |
// next msg_tree_vertices message. | |
std::size_t bicomp_length; | |
template<typename Archiver> | |
void serialize(Archiver& ar, const unsigned int /*version*/) | |
{ | |
ar & edge & gamma & bicomp_length; | |
} | |
}; | |
// Payload for the msg_name message. | |
template<typename EdgeDescriptor> | |
struct name_header | |
{ | |
// The edge being communicated and named. | |
EdgeDescriptor edge; | |
// The 0-based name of the component | |
std::size_t name; | |
template<typename Archiver> | |
void serialize(Archiver& ar, const unsigned int /*version*/) | |
{ | |
ar & edge & name; | |
} | |
}; | |
/* Computes the branch point between two paths. The branch point is | |
the last position at which both paths are equivalent, beyond | |
which the paths diverge. Both paths must have length > 0 and the | |
initial elements of the paths must be equal. This is guaranteed | |
in Hohberg's algorithm because all paths start at the | |
leader. Returns the value at the branch point. */ | |
template<typename T> | |
T branch_point(const std::vector<T>& p1, const std::vector<T>& p2) | |
{ | |
BOOST_ASSERT(!p1.empty()); | |
BOOST_ASSERT(!p2.empty()); | |
BOOST_ASSERT(p1.front() == p2.front()); | |
typedef typename std::vector<T>::const_iterator iterator; | |
iterator mismatch_pos; | |
if (p1.size() <= p2.size()) | |
mismatch_pos = std::mismatch(p1.begin(), p1.end(), p2.begin()).first; | |
else | |
mismatch_pos = std::mismatch(p2.begin(), p2.end(), p1.begin()).first; | |
--mismatch_pos; | |
return *mismatch_pos; | |
} | |
/* Computes the infimum of vertices a and b in the given path. The | |
infimum is the largest element that is on the paths from a to the | |
root and from b to the root. */ | |
template<typename T> | |
T infimum(const std::vector<T>& parent_path, T a, T b) | |
{ | |
using std::swap; | |
typedef typename std::vector<T>::const_iterator iterator; | |
iterator first = parent_path.begin(), last = parent_path.end(); | |
#if defined(PBGL_HOHBERG_DEBUG) and PBGL_HOHBERG_DEBUG > 2 | |
std::cerr << "infimum("; | |
for (iterator i = first; i != last; ++i) { | |
if (i != first) std::cerr << ' '; | |
std::cerr << local(*i) << '@' << owner(*i); | |
} | |
std::cerr << ", " << local(a) << '@' << owner(a) << ", " | |
<< local(b) << '@' << owner(b) << ") = "; | |
#endif | |
if (a == b) { | |
#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
std::cerr << local(a) << '@' << owner(a) << std::endl; | |
#endif | |
return a; | |
} | |
// Try to find a or b, whichever is closest to the end | |
--last; | |
while (*last != a) { | |
// If we match b, swap the two so we'll be looking for b later. | |
if (*last == b) { swap(a,b); break; } | |
if (last == first) { | |
#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
std::cerr << local(*first) << '@' << owner(*first) << std::endl; | |
#endif | |
return *first; | |
} | |
else --last; | |
} | |
// Try to find b (which may originally have been a) | |
while (*last != b) { | |
if (last == first) { | |
#if defined(PBGL_HOHBERG_DEBUG) and PBGL_HOHBERG_DEBUG > 2 | |
std::cerr << local(*first) << '@' << owner(*first) << std::endl; | |
#endif | |
return *first; | |
} | |
else --last; | |
} | |
#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
std::cerr << local(*last) << '@' << owner(*last) << std::endl; | |
#endif | |
// We've found b; it's the infimum. | |
return *last; | |
} | |
} // end namespace hohberg_detail | |
/* A message that will be stored for each edge by Hohberg's algorithm. */ | |
template<typename Graph> | |
struct hohberg_message | |
{ | |
typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
typedef typename graph_traits<Graph>::edge_descriptor Edge; | |
// Assign from a path message | |
void assign(const std::vector<Vertex>& path) | |
{ | |
gamma = graph_traits<Graph>::null_vertex(); | |
path_or_bicomp = path; | |
} | |
// Assign from a tree message | |
void assign(Vertex gamma, const std::vector<Vertex>& in_same_bicomponent) | |
{ | |
this->gamma = gamma; | |
path_or_bicomp = in_same_bicomponent; | |
} | |
bool is_path() const { return gamma == graph_traits<Graph>::null_vertex(); } | |
bool is_tree() const { return gamma != graph_traits<Graph>::null_vertex(); } | |
/// The "gamma" of a tree message, or null_vertex() for a path message | |
Vertex gamma; | |
// Either the path for a path message or the in_same_bicomponent | |
std::vector<Vertex> path_or_bicomp; | |
}; | |
/* An abstraction of a vertex processor in Hohberg's algorithm. The | |
hohberg_vertex_processor class is responsible for processing | |
messages transmitted to it via its edges. */ | |
template<typename Graph> | |
class hohberg_vertex_processor | |
{ | |
typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
typedef typename graph_traits<Graph>::edge_descriptor Edge; | |
typedef typename graph_traits<Graph>::degree_size_type degree_size_type; | |
typedef typename graph_traits<Graph>::edges_size_type edges_size_type; | |
typedef typename boost::graph::parallel::process_group_type<Graph>::type | |
ProcessGroup; | |
typedef std::vector<Vertex> path_t; | |
typedef typename path_t::iterator path_iterator; | |
public: | |
hohberg_vertex_processor() | |
: phase(1), | |
parent(graph_traits<Graph>::null_vertex()), | |
eta(graph_traits<Graph>::null_vertex()) | |
{ | |
} | |
// Called to initialize a leader in the algorithm, which involves | |
// sending out the initial path messages and being ready to receive | |
// them. | |
void initialize_leader(Vertex alpha, const Graph& g); | |
/// Handle a path message on edge e. The path will be destroyed by | |
/// this operation. | |
void | |
operator()(Edge e, path_t& path, const Graph& g); | |
/// Handle a tree message on edge e. in_same_bicomponent will be | |
/// destroyed by this operation. | |
void | |
operator()(Edge e, Vertex gamma, path_t& in_same_bicomponent, | |
const Graph& g); | |
// Handle a name message. | |
void operator()(Edge e, edges_size_type name, const Graph& g); | |
// Retrieve the phase | |
unsigned char get_phase() const { return phase; } | |
// Start the naming phase. The current phase must be 3 (echo), and | |
// the offset contains the offset at which this processor should | |
// begin when labelling its bicomponents. The offset is just a | |
// parallel prefix sum of the number of bicomponents in each | |
// processor that precedes it (globally). | |
void | |
start_naming_phase(Vertex alpha, const Graph& g, edges_size_type offset); | |
/* Determine the number of bicomponents that we will be naming | |
* ourselves. | |
*/ | |
edges_size_type num_starting_bicomponents(Vertex alpha, const Graph& g); | |
// Fill in the edge component map with biconnected component | |
// numbers. | |
template<typename ComponentMap> | |
void fill_edge_map(Vertex alpha, const Graph& g, ComponentMap& component); | |
protected: | |
/* Start the echo phase (phase 3) where we propagate information up | |
the tree. */ | |
void echo_phase(Vertex alpha, const Graph& g); | |
/* Retrieve the index of edge in the out-edges list of target(e, g). */ | |
std::size_t get_edge_index(Edge e, const Graph& g); | |
/* Retrieve the index of the edge incidence on v in the out-edges | |
list of vertex u. */ | |
std::size_t get_incident_edge_index(Vertex u, Vertex v, const Graph& g); | |
/* Keeps track of which phase of the algorithm we are in. There are | |
* four phases plus the "finished" phase: | |
* | |
* 1) Building the spanning tree | |
* 2) Discovering cycles | |
* 3) Echoing back up the spanning tree | |
* 4) Labelling biconnected components | |
* 5) Finished | |
*/ | |
unsigned char phase; | |
/* The parent of this vertex in the spanning tree. This value will | |
be graph_traits<Graph>::null_vertex() for the leader. */ | |
Vertex parent; | |
/* The farthest ancestor up the tree that resides in the same | |
biconnected component as we do. This information is approximate: | |
we might not know about the actual farthest ancestor, but this is | |
the farthest one we've seen so far. */ | |
Vertex eta; | |
/* The number of edges that have not yet transmitted any messages to | |
us. This starts at the degree of the vertex and decreases as we | |
receive messages. When this counter hits zero, we're done with | |
the second phase of the algorithm. In Hohberg's paper, the actual | |
remaining edge set E is stored with termination when all edges | |
have been removed from E, but we only need to detect termination | |
so the set E need not be explicitly represented. */ | |
degree_size_type num_edges_not_transmitted; | |
/* The path from the root of the spanning tree to this vertex. This | |
vector will always store only the parts of the path leading up to | |
this vertex, and not the vertex itself. Thus, it will be empty | |
for the leader. */ | |
std::vector<Vertex> path_from_root; | |
/* Structure containing all of the extra data we need to keep around | |
PER EDGE. This information can not be contained within a property | |
map, because it can't be shared among vertices without breaking | |
the algorithm. Decreasing the size of this structure will drastically */ | |
struct per_edge_data | |
{ | |
hohberg_message<Graph> msg; | |
std::vector<Vertex> M; | |
bool is_tree_edge; | |
degree_size_type partition; | |
}; | |
/* Data for each edge in the graph. This structure will be indexed | |
by the position of the edge in the out_edges() list. */ | |
std::vector<per_edge_data> edge_data; | |
/* The mapping from local partition numbers (0..n-1) to global | |
partition numbers. */ | |
std::vector<edges_size_type> local_to_global_partitions; | |
friend class boost::serialization::access; | |
// We cannot actually serialize a vertex processor, nor would we | |
// want to. However, the fact that we're putting instances into a | |
// distributed_property_map means that we need to have a serialize() | |
// function available. | |
template<typename Archiver> | |
void serialize(Archiver&, const unsigned int /*version*/) | |
{ | |
BOOST_ASSERT(false); | |
} | |
}; | |
template<typename Graph> | |
void | |
hohberg_vertex_processor<Graph>::initialize_leader(Vertex alpha, | |
const Graph& g) | |
{ | |
using namespace hohberg_detail; | |
ProcessGroup pg = process_group(g); | |
typename property_map<Graph, vertex_owner_t>::const_type | |
owner = get(vertex_owner, g); | |
path_header<Edge> header; | |
header.path_length = 1; | |
BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
header.edge = e; | |
send(pg, get(owner, target(e, g)), msg_path_header, header); | |
send(pg, get(owner, target(e, g)), msg_path_vertices, alpha); | |
} | |
num_edges_not_transmitted = degree(alpha, g); | |
edge_data.resize(num_edges_not_transmitted); | |
phase = 2; | |
} | |
template<typename Graph> | |
void | |
hohberg_vertex_processor<Graph>::operator()(Edge e, path_t& path, | |
const Graph& g) | |
{ | |
using namespace hohberg_detail; | |
typename property_map<Graph, vertex_owner_t>::const_type | |
owner = get(vertex_owner, g); | |
#ifdef PBGL_HOHBERG_DEBUG | |
// std::cerr << local(source(e, g)) << '@' << owner(source(e, g)) << " -> " | |
// << local(target(e, g)) << '@' << owner(target(e, g)) << ": path("; | |
// for (std::size_t i = 0; i < path.size(); ++i) { | |
// if (i > 0) std::cerr << ' '; | |
// std::cerr << local(path[i]) << '@' << owner(path[i]); | |
// } | |
std::cerr << "), phase = " << (int)phase << std::endl; | |
#endif | |
// Get access to edge-specific data | |
if (edge_data.empty()) | |
edge_data.resize(degree(target(e, g), g)); | |
per_edge_data& edata = edge_data[get_edge_index(e, g)]; | |
// Record the message. We'll need it in phase 3. | |
edata.msg.assign(path); | |
// Note: "alpha" refers to the vertex "processor" receiving the | |
// message. | |
Vertex alpha = target(e, g); | |
switch (phase) { | |
case 1: | |
{ | |
num_edges_not_transmitted = degree(alpha, g) - 1; | |
edata.is_tree_edge = true; | |
parent = path.back(); | |
eta = parent; | |
edata.M.clear(); edata.M.push_back(parent); | |
// Broadcast the path from the root to our potential children in | |
// the spanning tree. | |
path.push_back(alpha); | |
path_header<Edge> header; | |
header.path_length = path.size(); | |
ProcessGroup pg = process_group(g); | |
BGL_FORALL_OUTEDGES_T(alpha, oe, g, Graph) { | |
// Skip the tree edge we just received | |
if (target(oe, g) != source(e, g)) { | |
header.edge = oe; | |
send(pg, get(owner, target(oe, g)), msg_path_header, header); | |
send(pg, get(owner, target(oe, g)), msg_path_vertices, &path[0], | |
header.path_length); | |
} | |
} | |
path.pop_back(); | |
// Swap the old path in, to save some extra copying. Nobody | |
path_from_root.swap(path); | |
// Once we have received our place in the spanning tree, move on | |
// to phase 2. | |
phase = 2; | |
// If we only had only edge, skip to phase 3. | |
if (num_edges_not_transmitted == 0) | |
echo_phase(alpha, g); | |
return; | |
} | |
case 2: | |
{ | |
--num_edges_not_transmitted; | |
edata.is_tree_edge = false; | |
// Determine if alpha (our vertex) is in the path | |
path_iterator pos = std::find(path.begin(), path.end(), alpha); | |
if (pos != path.end()) { | |
// Case A: There is a cycle alpha beta ... gamma alpha | |
// M(e) <- {beta, gammar} | |
edata.M.clear(); | |
++pos; | |
// If pos == path.end(), we have a self-loop | |
if (pos != path.end()) { | |
// Add beta | |
edata.M.push_back(*pos); | |
++pos; | |
} | |
// If pos == path.end(), we have a self-loop or beta == gamma | |
// (parallel edge). Otherwise, add gamma. | |
if (pos != path.end()) edata.M.push_back(path.back()); | |
} else { | |
// Case B: There is a cycle but we haven't seen alpha yet. | |
// M(e) = {parent, path.back()} | |
edata.M.clear(); | |
edata.M.push_back(path.back()); | |
if (parent != path.back()) edata.M.push_back(parent); | |
// eta = inf(eta, bra(pi_t, pi)) | |
eta = infimum(path_from_root, eta, branch_point(path_from_root, path)); | |
} | |
if (num_edges_not_transmitted == 0) | |
echo_phase(alpha, g); | |
break; | |
} | |
default: | |
// std::cerr << "Phase is " << int(phase) << "\n"; | |
BOOST_ASSERT(false); | |
} | |
} | |
template<typename Graph> | |
void | |
hohberg_vertex_processor<Graph>::operator()(Edge e, Vertex gamma, | |
path_t& in_same_bicomponent, | |
const Graph& g) | |
{ | |
using namespace hohberg_detail; | |
#ifdef PBGL_HOHBERG_DEBUG | |
std::cerr << local(source(e, g)) << '@' << owner(source(e, g)) << " -> " | |
<< local(target(e, g)) << '@' << owner(target(e, g)) << ": tree(" | |
<< local(gamma) << '@' << owner(gamma) << ", "; | |
for (std::size_t i = 0; i < in_same_bicomponent.size(); ++i) { | |
if (i > 0) std::cerr << ' '; | |
std::cerr << local(in_same_bicomponent[i]) << '@' | |
<< owner(in_same_bicomponent[i]); | |
} | |
std::cerr << ", " << local(source(e, g)) << '@' << owner(source(e, g)) | |
<< "), phase = " << (int)phase << std::endl; | |
#endif | |
// Get access to edge-specific data | |
per_edge_data& edata = edge_data[get_edge_index(e, g)]; | |
// Record the message. We'll need it in phase 3. | |
edata.msg.assign(gamma, in_same_bicomponent); | |
// Note: "alpha" refers to the vertex "processor" receiving the | |
// message. | |
Vertex alpha = target(e, g); | |
Vertex beta = source(e, g); | |
switch (phase) { | |
case 2: | |
--num_edges_not_transmitted; | |
edata.is_tree_edge = true; | |
if (gamma == alpha) { | |
// Case C | |
edata.M.swap(in_same_bicomponent); | |
} else { | |
// Case D | |
edata.M.clear(); | |
edata.M.push_back(parent); | |
if (beta != parent) edata.M.push_back(beta); | |
eta = infimum(path_from_root, eta, gamma); | |
} | |
if (num_edges_not_transmitted == 0) | |
echo_phase(alpha, g); | |
break; | |
default: | |
BOOST_ASSERT(false); | |
} | |
} | |
template<typename Graph> | |
void | |
hohberg_vertex_processor<Graph>::operator()(Edge e, edges_size_type name, | |
const Graph& g) | |
{ | |
using namespace hohberg_detail; | |
#ifdef PBGL_HOHBERG_DEBUG | |
std::cerr << local(source(e, g)) << '@' << owner(source(e, g)) << " -> " | |
<< local(target(e, g)) << '@' << owner(target(e, g)) << ": name(" | |
<< name << "), phase = " << (int)phase << std::endl; | |
#endif | |
BOOST_ASSERT(phase == 4); | |
typename property_map<Graph, vertex_owner_t>::const_type | |
owner = get(vertex_owner, g); | |
// Send name messages along the spanning tree edges that are in the | |
// same bicomponent as the edge to our parent. | |
ProcessGroup pg = process_group(g); | |
Vertex alpha = target(e, g); | |
std::size_t idx = 0; | |
BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
per_edge_data& edata = edge_data[idx++]; | |
if (edata.is_tree_edge | |
&& find(edata.M.begin(), edata.M.end(), parent) != edata.M.end() | |
&& target(e, g) != parent) { | |
// Notify our children in the spanning tree of this name | |
name_header<Edge> header; | |
header.edge = e; | |
header.name = name; | |
send(pg, get(owner, target(e, g)), msg_name, header); | |
} else if (target(e, g) == parent) { | |
// Map from local partition numbers to global bicomponent numbers | |
local_to_global_partitions[edata.partition] = name; | |
} | |
} | |
// Final stage | |
phase = 5; | |
} | |
template<typename Graph> | |
typename hohberg_vertex_processor<Graph>::edges_size_type | |
hohberg_vertex_processor<Graph>:: | |
num_starting_bicomponents(Vertex alpha, const Graph& g) | |
{ | |
edges_size_type not_mapped = (std::numeric_limits<edges_size_type>::max)(); | |
edges_size_type result = 0; | |
std::size_t idx = 0; | |
BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
per_edge_data& edata = edge_data[idx++]; | |
if (edata.is_tree_edge | |
&& find(edata.M.begin(), edata.M.end(), parent) == edata.M.end()) { | |
// Map from local partition numbers to global bicomponent numbers | |
if (local_to_global_partitions[edata.partition] == not_mapped) | |
local_to_global_partitions[edata.partition] = result++; | |
} | |
} | |
#ifdef PBGL_HOHBERG_DEBUG | |
std::cerr << local(alpha) << '@' << owner(alpha) << " has " << result | |
<< " bicomponents originating at it." << std::endl; | |
#endif | |
return result; | |
} | |
template<typename Graph> | |
template<typename ComponentMap> | |
void | |
hohberg_vertex_processor<Graph>:: | |
fill_edge_map(Vertex alpha, const Graph& g, ComponentMap& component) | |
{ | |
std::size_t idx = 0; | |
BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
per_edge_data& edata = edge_data[idx++]; | |
local_put(component, e, local_to_global_partitions[edata.partition]); | |
#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
std::cerr << "component(" | |
<< local(source(e, g)) << '@' << owner(source(e, g)) << " -> " | |
<< local(target(e, g)) << '@' << owner(target(e, g)) << ") = " | |
<< local_to_global_partitions[edata.partition] | |
<< " (partition = " << edata.partition << " of " | |
<< local_to_global_partitions.size() << ")" << std::endl; | |
#endif | |
} | |
} | |
template<typename Graph> | |
void | |
hohberg_vertex_processor<Graph>:: | |
start_naming_phase(Vertex alpha, const Graph& g, edges_size_type offset) | |
{ | |
using namespace hohberg_detail; | |
BOOST_ASSERT(phase == 4); | |
typename property_map<Graph, vertex_owner_t>::const_type | |
owner = get(vertex_owner, g); | |
// Send name messages along the spanning tree edges of the | |
// components that we get to number. | |
ProcessGroup pg = process_group(g); | |
bool has_more_children_to_name = false; | |
// Map from local partition numbers to global bicomponent numbers | |
edges_size_type not_mapped = (std::numeric_limits<edges_size_type>::max)(); | |
for (std::size_t i = 0; i < local_to_global_partitions.size(); ++i) { | |
if (local_to_global_partitions[i] != not_mapped) | |
local_to_global_partitions[i] += offset; | |
} | |
std::size_t idx = 0; | |
BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
per_edge_data& edata = edge_data[idx++]; | |
if (edata.is_tree_edge | |
&& find(edata.M.begin(), edata.M.end(), parent) == edata.M.end()) { | |
// Notify our children in the spanning tree of this new name | |
name_header<Edge> header; | |
header.edge = e; | |
header.name = local_to_global_partitions[edata.partition]; | |
send(pg, get(owner, target(e, g)), msg_name, header); | |
} else if (edata.is_tree_edge) { | |
has_more_children_to_name = true; | |
} | |
#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
std::cerr << "M[" << local(source(e, g)) << '@' << owner(source(e, g)) | |
<< " -> " << local(target(e, g)) << '@' << owner(target(e, g)) | |
<< "] = "; | |
for (std::size_t i = 0; i < edata.M.size(); ++i) { | |
std::cerr << local(edata.M[i]) << '@' << owner(edata.M[i]) << ' '; | |
} | |
std::cerr << std::endl; | |
#endif | |
} | |
// See if we're done. | |
if (!has_more_children_to_name) | |
// Final stage | |
phase = 5; | |
} | |
template<typename Graph> | |
void | |
hohberg_vertex_processor<Graph>::echo_phase(Vertex alpha, const Graph& g) | |
{ | |
using namespace hohberg_detail; | |
typename property_map<Graph, vertex_owner_t>::const_type | |
owner = get(vertex_owner, g); | |
/* We're entering the echo phase. */ | |
phase = 3; | |
if (parent != graph_traits<Graph>::null_vertex()) { | |
Edge edge_to_parent; | |
#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1 | |
std::cerr << local(alpha) << '@' << owner(alpha) << " echo: parent = " | |
<< local(parent) << '@' << owner(parent) << ", eta = " | |
<< local(eta) << '@' << owner(eta) << ", Gamma = "; | |
#endif | |
std::vector<Vertex> bicomp; | |
std::size_t e_index = 0; | |
BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
if (target(e, g) == parent && parent == eta) { | |
edge_to_parent = e; | |
if (find(bicomp.begin(), bicomp.end(), alpha) == bicomp.end()) { | |
#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1 | |
std::cerr << local(alpha) << '@' << owner(alpha) << ' '; | |
#endif | |
bicomp.push_back(alpha); | |
} | |
} else { | |
if (target(e, g) == parent) edge_to_parent = e; | |
per_edge_data& edata = edge_data[e_index]; | |
if (edata.msg.is_path()) { | |
path_iterator pos = std::find(edata.msg.path_or_bicomp.begin(), | |
edata.msg.path_or_bicomp.end(), | |
eta); | |
if (pos != edata.msg.path_or_bicomp.end()) { | |
++pos; | |
if (pos != edata.msg.path_or_bicomp.end() | |
&& find(bicomp.begin(), bicomp.end(), *pos) == bicomp.end()) { | |
#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1 | |
std::cerr << local(*pos) << '@' << owner(*pos) << ' '; | |
#endif | |
bicomp.push_back(*pos); | |
} | |
} | |
} else if (edata.msg.is_tree() && edata.msg.gamma == eta) { | |
for (path_iterator i = edata.msg.path_or_bicomp.begin(); | |
i != edata.msg.path_or_bicomp.end(); ++i) { | |
if (find(bicomp.begin(), bicomp.end(), *i) == bicomp.end()) { | |
#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1 | |
std::cerr << local(*i) << '@' << owner(*i) << ' '; | |
#endif | |
bicomp.push_back(*i); | |
} | |
} | |
} | |
} | |
++e_index; | |
} | |
#ifdef PBGL_HOHBERG_DEBUG | |
std::cerr << std::endl; | |
#endif | |
// Send tree(eta, bicomp) to parent | |
tree_header<Vertex, Edge> header; | |
header.edge = edge_to_parent; | |
header.gamma = eta; | |
header.bicomp_length = bicomp.size(); | |
ProcessGroup pg = process_group(g); | |
send(pg, get(owner, parent), msg_tree_header, header); | |
send(pg, get(owner, parent), msg_tree_vertices, &bicomp[0], | |
header.bicomp_length); | |
} | |
// Compute the partition of edges such that iff two edges e1 and e2 | |
// are in different subsets then M(e1) is disjoint from M(e2). | |
// Start by putting each edge in a different partition | |
std::vector<degree_size_type> parent_vec(edge_data.size()); | |
degree_size_type idx = 0; | |
for (idx = 0; idx < edge_data.size(); ++idx) | |
parent_vec[idx] = idx; | |
// Go through each edge e, performing a union() on the edges | |
// incident on all vertices in M[e]. | |
idx = 0; | |
BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
per_edge_data& edata = edge_data[idx++]; | |
// Compute union of vertices in M | |
if (!edata.M.empty()) { | |
degree_size_type e1 = get_incident_edge_index(alpha, edata.M.front(), g); | |
while (parent_vec[e1] != e1) e1 = parent_vec[e1]; | |
for (std::size_t i = 1; i < edata.M.size(); ++i) { | |
degree_size_type e2 = get_incident_edge_index(alpha, edata.M[i], g); | |
while (parent_vec[e2] != e2) e2 = parent_vec[e2]; | |
parent_vec[e2] = e1; | |
} | |
} | |
} | |
edges_size_type not_mapped = (std::numeric_limits<edges_size_type>::max)(); | |
// Determine the number of partitions | |
for (idx = 0; idx < parent_vec.size(); ++idx) { | |
if (parent_vec[idx] == idx) { | |
edge_data[idx].partition = local_to_global_partitions.size(); | |
local_to_global_partitions.push_back(not_mapped); | |
} | |
} | |
// Assign partition numbers to each edge | |
for (idx = 0; idx < parent_vec.size(); ++idx) { | |
degree_size_type rep = parent_vec[idx]; | |
while (rep != parent_vec[rep]) rep = parent_vec[rep]; | |
edge_data[idx].partition = edge_data[rep].partition; | |
} | |
// Enter the naming phase (but don't send anything yet). | |
phase = 4; | |
} | |
template<typename Graph> | |
std::size_t | |
hohberg_vertex_processor<Graph>::get_edge_index(Edge e, const Graph& g) | |
{ | |
std::size_t result = 0; | |
BGL_FORALL_OUTEDGES_T(target(e, g), oe, g, Graph) { | |
if (source(e, g) == target(oe, g)) return result; | |
++result; | |
} | |
BOOST_ASSERT(false); | |
} | |
template<typename Graph> | |
std::size_t | |
hohberg_vertex_processor<Graph>::get_incident_edge_index(Vertex u, Vertex v, | |
const Graph& g) | |
{ | |
std::size_t result = 0; | |
BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { | |
if (target(e, g) == v) return result; | |
++result; | |
} | |
BOOST_ASSERT(false); | |
} | |
template<typename Graph, typename InputIterator, typename ComponentMap, | |
typename VertexProcessorMap> | |
typename graph_traits<Graph>::edges_size_type | |
hohberg_biconnected_components | |
(const Graph& g, | |
ComponentMap component, | |
InputIterator first, InputIterator last, | |
VertexProcessorMap vertex_processor) | |
{ | |
using namespace boost::graph::parallel; | |
using namespace hohberg_detail; | |
using boost::parallel::all_reduce; | |
typename property_map<Graph, vertex_owner_t>::const_type | |
owner = get(vertex_owner, g); | |
// The graph must be undirected | |
BOOST_STATIC_ASSERT( | |
(is_convertible<typename graph_traits<Graph>::directed_category, | |
undirected_tag>::value)); | |
// The graph must model Incidence Graph | |
function_requires< IncidenceGraphConcept<Graph> >(); | |
typedef typename graph_traits<Graph>::edges_size_type edges_size_type; | |
typedef typename graph_traits<Graph>::degree_size_type degree_size_type; | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; | |
// Retrieve the process group we will use for communication | |
typedef typename process_group_type<Graph>::type process_group_type; | |
process_group_type pg = process_group(g); | |
// Keeps track of the edges that we know to be tree edges. | |
std::vector<edge_descriptor> tree_edges; | |
// The leaders send out a path message to initiate the algorithm | |
while (first != last) { | |
vertex_descriptor leader = *first; | |
if (process_id(pg) == get(owner, leader)) | |
vertex_processor[leader].initialize_leader(leader, g); | |
++first; | |
} | |
synchronize(pg); | |
// Will hold the number of bicomponents in the graph. | |
edges_size_type num_bicomponents = 0; | |
// Keep track of the path length that we should expect, based on the | |
// level in the breadth-first search tree. At present, this is only | |
// used as a sanity check. TBD: This could be used to decrease the | |
// amount of communication required per-edge (by about 4 bytes). | |
std::size_t path_length = 1; | |
typedef std::vector<vertex_descriptor> path_t; | |
typedef typename path_t::iterator path_iterator; | |
unsigned char minimum_phase = 5; | |
do { | |
while (optional<std::pair<int, int> > msg = probe(pg)) { | |
switch (msg->second) { | |
case msg_path_header: | |
{ | |
// Receive the path header | |
path_header<edge_descriptor> header; | |
receive(pg, msg->first, msg->second, header); | |
BOOST_ASSERT(path_length == header.path_length); | |
// Receive the path itself | |
path_t path(path_length); | |
receive(pg, msg->first, msg_path_vertices, &path[0], path_length); | |
edge_descriptor e = header.edge; | |
vertex_processor[target(e, g)](e, path, g); | |
} | |
break; | |
case msg_path_vertices: | |
// Should be handled in msg_path_header case, unless we're going | |
// stateless. | |
BOOST_ASSERT(false); | |
break; | |
case msg_tree_header: | |
{ | |
// Receive the tree header | |
tree_header<vertex_descriptor, edge_descriptor> header; | |
receive(pg, msg->first, msg->second, header); | |
// Receive the tree itself | |
path_t in_same_bicomponent(header.bicomp_length); | |
receive(pg, msg->first, msg_tree_vertices, &in_same_bicomponent[0], | |
header.bicomp_length); | |
edge_descriptor e = header.edge; | |
vertex_processor[target(e, g)](e, header.gamma, in_same_bicomponent, | |
g); | |
} | |
break; | |
case msg_tree_vertices: | |
// Should be handled in msg_tree_header case, unless we're | |
// going stateless. | |
BOOST_ASSERT(false); | |
break; | |
case msg_name: | |
{ | |
name_header<edge_descriptor> header; | |
receive(pg, msg->first, msg->second, header); | |
edge_descriptor e = header.edge; | |
vertex_processor[target(e, g)](e, header.name, g); | |
} | |
break; | |
default: | |
BOOST_ASSERT(false); | |
} | |
} | |
++path_length; | |
// Compute minimum phase locally | |
minimum_phase = 5; | |
unsigned char maximum_phase = 1; | |
BGL_FORALL_VERTICES_T(v, g, Graph) { | |
minimum_phase = (std::min)(minimum_phase, vertex_processor[v].get_phase()); | |
maximum_phase = (std::max)(maximum_phase, vertex_processor[v].get_phase()); | |
} | |
#ifdef PBGL_HOHBERG_DEBUG | |
if (process_id(pg) == 0) | |
std::cerr << "<---------End of stage------------->" << std::endl; | |
#endif | |
// Compute minimum phase globally | |
minimum_phase = all_reduce(pg, minimum_phase, boost::mpi::minimum<char>()); | |
#ifdef PBGL_HOHBERG_DEBUG | |
if (process_id(pg) == 0) | |
std::cerr << "Minimum phase = " << (int)minimum_phase << std::endl; | |
#endif | |
if (minimum_phase == 4 | |
&& all_reduce(pg, maximum_phase, boost::mpi::maximum<char>()) == 4) { | |
#ifdef PBGL_HOHBERG_DEBUG | |
if (process_id(pg) == 0) | |
std::cerr << "<---------Naming phase------------->" << std::endl; | |
#endif | |
// Compute the biconnected component number offsets for each | |
// vertex. | |
std::vector<edges_size_type> local_offsets; | |
local_offsets.reserve(num_vertices(g)); | |
edges_size_type num_local_bicomponents = 0; | |
BGL_FORALL_VERTICES_T(v, g, Graph) { | |
local_offsets.push_back(num_local_bicomponents); | |
num_local_bicomponents += | |
vertex_processor[v].num_starting_bicomponents(v, g); | |
} | |
synchronize(pg); | |
// Find our the number of bicomponent names that will originate | |
// from each process. This tells us how many bicomponents are in | |
// the entire graph and what our global offset is for computing | |
// our own biconnected component names. | |
std::vector<edges_size_type> all_bicomponents(num_processes(pg)); | |
all_gather(pg, &num_local_bicomponents, &num_local_bicomponents + 1, | |
all_bicomponents); | |
num_bicomponents = 0; | |
edges_size_type my_global_offset = 0; | |
for (std::size_t i = 0; i < all_bicomponents.size(); ++i) { | |
if (i == (std::size_t)process_id(pg)) | |
my_global_offset = num_bicomponents; | |
num_bicomponents += all_bicomponents[i]; | |
} | |
std::size_t index = 0; | |
BGL_FORALL_VERTICES_T(v, g, Graph) { | |
edges_size_type offset = my_global_offset + local_offsets[index++]; | |
vertex_processor[v].start_naming_phase(v, g, offset); | |
} | |
} | |
synchronize(pg); | |
} while (minimum_phase < 5); | |
// Number the edges appropriately. | |
BGL_FORALL_VERTICES_T(v, g, Graph) | |
vertex_processor[v].fill_edge_map(v, g, component); | |
return num_bicomponents; | |
} | |
template<typename Graph, typename ComponentMap, typename InputIterator> | |
typename graph_traits<Graph>::edges_size_type | |
hohberg_biconnected_components | |
(const Graph& g, ComponentMap component, | |
InputIterator first, InputIterator last) | |
{ | |
std::vector<hohberg_vertex_processor<Graph> > | |
vertex_processors(num_vertices(g)); | |
return hohberg_biconnected_components | |
(g, component, first, last, | |
make_iterator_property_map(vertex_processors.begin(), | |
get(vertex_index, g))); | |
} | |
template<typename Graph, typename ComponentMap, typename ParentMap> | |
typename graph_traits<Graph>::edges_size_type | |
hohberg_biconnected_components(const Graph& g, ComponentMap component, | |
ParentMap parent) | |
{ | |
// We need the connected components of the graph, but we don't care | |
// about component numbers. | |
connected_components(g, dummy_property_map(), parent); | |
// Each root in the parent map is a leader | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
std::vector<vertex_descriptor> leaders; | |
BGL_FORALL_VERTICES_T(v, g, Graph) | |
if (get(parent, v) == v) leaders.push_back(v); | |
return hohberg_biconnected_components(g, component, | |
leaders.begin(), leaders.end()); | |
} | |
template<typename Graph, typename ComponentMap> | |
typename graph_traits<Graph>::edges_size_type | |
hohberg_biconnected_components(const Graph& g, ComponentMap component) | |
{ | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
std::vector<vertex_descriptor> parents(num_vertices(g)); | |
return hohberg_biconnected_components | |
(g, component, make_iterator_property_map(parents.begin(), | |
get(vertex_index, g))); | |
} | |
} } } // end namespace boost::graph::distributed | |
#endif // BOOST_GRAPH_DISTRIBUTED_HOHBERG_BICONNECTED_COMPONENTS_HPP |