FM / distributed

/usr/include/boost/graph/distributed

Name	Size	Mode	Actions
adjlist/	-	0755	rm
detail/	-	0755	rm
adjacency_list.hpp	149777	0644	edit dl rm
betweenness_centrality.hpp	70132	0644	edit dl rm
boman_et_al_graph_coloring.hpp	12987	0644	edit dl rm
breadth_first_search.hpp	5209	0644	edit dl rm
compressed_sparse_row_graph.hpp	81805	0644	edit dl rm
concepts.hpp	7028	0644	edit dl rm
connected_components.hpp	28401	0644	edit dl rm
connected_components_parallel_search.hpp	15059	0644	edit dl rm
crauser_et_al_shortest_paths.hpp	25342	0644	edit dl rm
dehne_gotz_min_spanning_tree.hpp	38687	0644	edit dl rm
delta_stepping_shortest_paths.hpp	19415	0644	edit dl rm
depth_first_search.hpp	10437	0644	edit dl rm
dijkstra_shortest_paths.hpp	8719	0644	edit dl rm
distributed_graph_utility.hpp	4560	0644	edit dl rm
eager_dijkstra_shortest_paths.hpp	16294	0644	edit dl rm
filtered_graph.hpp	1943	0644	edit dl rm
fruchterman_reingold.hpp	12963	0644	edit dl rm
graphviz.hpp	8672	0644	edit dl rm
hohberg_biconnected_components.hpp	38093	0644	edit dl rm
local_subgraph.hpp	6057	0644	edit dl rm
mpi_process_group.hpp	26592	0644	edit dl rm
named_graph.hpp	48162	0644	edit dl rm
one_bit_color_map.hpp	4046	0644	edit dl rm
page_rank.hpp	8003	0644	edit dl rm
queue.hpp	10249	0644	edit dl rm
reverse_graph.hpp	1223	0644	edit dl rm
rmat_graph_generator.hpp	5913	0644	edit dl rm
selector.hpp	1375	0644	edit dl rm
shuffled_distribution.hpp	2833	0644	edit dl rm
strong_components.hpp	40396	0644	edit dl rm
st_connected.hpp	6158	0644	edit dl rm
two_bit_color_map.hpp	4041	0644	edit dl rm
unsafe_serialize.hpp	380	0644	edit dl rm
vertex_list_adaptor.hpp	16252	0644	edit dl rm

Edit: /usr/include/boost/graph/distributed/st_connected.hpp (6158B)

// 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
#ifndef BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
#define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP

#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/two_bit_color_map.hpp>
#include <boost/graph/distributed/queue.hpp>
#include <boost/pending/queue.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/parallel/container_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/parallel/algorithm.hpp>
#include <utility>
#include <boost/optional.hpp>

namespace boost { namespace graph { namespace distributed {

namespace detail {
  struct pair_and_or 
  {
    std::pair<bool, bool> 
    operator()(std::pair<bool, bool> x, std::pair<bool, bool> y) const
    {
      return std::pair<bool, bool>(x.first && y.first,
                                   x.second || y.second);
    }
  };

} // end namespace detail

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)
{
  using boost::graph::parallel::process_group;
  using boost::graph::parallel::process_group_type;
  using boost::parallel::all_reduce;

typedef typename property_traits<ColorMap>::value_type Color;
  typedef color_traits<Color> ColorTraits;
  typedef typename process_group_type<DistributedGraph>::type ProcessGroup;
  typedef typename ProcessGroup::process_id_type ProcessID;
  typedef typename graph_traits<DistributedGraph>::vertex_descriptor Vertex;

// Set all vertices to white (unvisited)
  BGL_FORALL_VERTICES_T(v, g, DistributedGraph)
    put(color, v, ColorTraits::white());

// "color" plays the role of a color map, with no synchronization.
  set_property_map_role(vertex_color, color);
  color.set_consistency_model(0);

// Vertices found from the source are grey
  put(color, s, ColorTraits::gray());

// Vertices found from the target are green
  put(color, t, ColorTraits::green());

ProcessGroup pg = process_group(g);
  ProcessID rank = process_id(pg);

// Build a local queue
  queue<Vertex> Q;
  if (get(owner, s) == rank) Q.push(s);
  if (get(owner, t) == rank) Q.push(t);

queue<Vertex> other_Q;

while (true) {
    bool found = false;

// Process all vertices in the local queue
    while (!found && !Q.empty()) {
      Vertex u = Q.top(); Q.pop();
      Color u_color = get(color, u);

BGL_FORALL_OUTEDGES_T(u, e, g, DistributedGraph) {
        Vertex v = target(e, g);
        Color v_color = get(color, v);
        if (v_color == ColorTraits::white()) {
          // We have not seen "v" before; mark it with the same color as u
          Color u_color = get(color, u);
          put(color, v, u_color);

// Either push v into the local queue or send it off to its
          // owner.
          ProcessID v_owner = get(owner, v);
          if (v_owner == rank) 
            other_Q.push(v);
          else
            send(pg, v_owner, 0, 
                 std::make_pair(v, u_color == ColorTraits::gray()));
        } else if (v_color != ColorTraits::black() && u_color != v_color) {
          // Colors have collided. We're done!
          found = true;
          break;
        }
      }

// u is done, so mark it black
      put(color, u, ColorTraits::black());
    }

// Ensure that all transmitted messages have been received.
    synchronize(pg);

// Move all of the send-to-self values into the local Q.
    other_Q.swap(Q);

if (!found) {
      // Receive all messages
      while (optional<std::pair<ProcessID, int> > msg = probe(pg)) {
        std::pair<Vertex, bool> data;
        receive(pg, msg->first, msg->second, data);
        
        // Determine the colors of u and v, the source and target
        // vertices (v is local).
        Vertex v = data.first;
        Color v_color = get(color, v);
        Color u_color = data.second? ColorTraits::gray() : ColorTraits::green();
        if (v_color == ColorTraits::white()) {
          // v had no color before, so give it u's color and push it
          // into the queue.
          Q.push(v);
          put(color, v, u_color);
        } else if (v_color != ColorTraits::black() && u_color != v_color) {
          // Colors have collided. We're done!
          found = true;
          break;
        }
      }
    }

// Check if either all queues are empty or 
    std::pair<bool, bool> results = all_reduce(pg, 
            boost::parallel::detail::make_untracked_pair(Q.empty(), found),
            detail::pair_and_or());

// If someone found the answer, we're done!
    if (results.second)
      return true;

// If all queues are empty, we're done.
    if (results.first)
      return false;
  }
}

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)
{
  return st_connected(g, s, t, color, get(vertex_owner, g));
}

template<typename DistributedGraph>
inline bool 
st_connected(const DistributedGraph& g, 
             typename graph_traits<DistributedGraph>::vertex_descriptor s,
             typename graph_traits<DistributedGraph>::vertex_descriptor t)
{
  return st_connected(g, s, t, 
                      make_two_bit_color_map(num_vertices(g),
                                             get(vertex_index, g)));
}

} } } // end namespace boost::graph::distributed

#endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP

cmd: