...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
namespace graph { namespace distributed { template<typename DistributedGraph, typename ColorMap> inline bool st_connected(const DistributedGraph& g, typename graph_traits<DistributedGraph>::vertex_descriptor s, typename graph_traits<DistributedGraph>::vertex_descriptor t, ColorMap color) template<typename DistributedGraph> inline bool st_connected(const DistributedGraph& g, typename graph_traits<DistributedGraph>::vertex_descriptor s, typename graph_traits<DistributedGraph>::vertex_descriptor t) template<typename DistributedGraph, typename ColorMap, typename OwnerMap> bool st_connected(const DistributedGraph& g, typename graph_traits<DistributedGraph>::vertex_descriptor s, typename graph_traits<DistributedGraph>::vertex_descriptor t, ColorMap color, OwnerMap owner) } }
The st_connected() function determines whether there exists a path from s to t in a graph g. If a path exists the function returns true, otherwise it returns false.
This algorithm is currently level-synchronized, meaning that all vertices in a given level of the search tree will be processed (potentially in parallel) before any vertices from a successive level in the tree are processed. This is not necessary for the correctness of the algorithm but rather is an implementation detail. This algorithm could be rewritten fully-asynchronously using triggers which would remove the level-synchronized behavior.
<boost/graph/distributed/st_connected.hpp>
IN: vertex_descriptor s
IN: vertex_descriptor t
This algorithm performs O(V + E) work in d/2 + 1 BSP supersteps, where d is the shortest distance from s to t. Over all supersteps, O(E) messages of constant size will be transmitted.
The algorithm consists of two simultaneous breadth-first traversals from s and t respectively. The algorithm utilizes a single queue for both traversals with the traversal from s being denoted by a gray entry in the color map and the traversal from t being denoted by a green entry. The traversal method is similar to breadth-first search except that no visitor event points are called. When any process detects a collision in the two traversals (by attempting to set a gray vertex to green or vice-versa), it signals all processes to terminate on the next superstep and all processes return true. If the queues on all processes are empty and no collision is detected then all processes terminate and return false.
Copyright (C) 2009 The Trustees of Indiana University.
Authors: Nick Edmonds and Andrew Lumsdaine