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/breadth_first_search.hpp (5209B)

// 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_PARALLEL_BFS_HPP
#define BOOST_GRAPH_PARALLEL_BFS_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/breadth_first_search.hpp>
#include <boost/graph/overloading.hpp>
#include <boost/graph/distributed/concepts.hpp>
#include <boost/graph/distributed/detail/filtered_queue.hpp>
#include <boost/graph/distributed/queue.hpp>
#include <boost/dynamic_bitset.hpp>
#include <boost/pending/queue.hpp>
#include <boost/graph/parallel/properties.hpp>
#include <boost/graph/parallel/container_traits.hpp>

namespace boost {
  namespace detail {
    /** @brief A unary predicate that decides when to push into a
     *         breadth-first search queue.
     *
     *  This predicate stores a color map that is used to determine
     *  when to push. If it is provided with a key for which the color
     *  is white, it darkens the color to gray and returns true (so
     *  that the value will be pushed appropriately); if the color is
     *  not white, it returns false so that the vertex will be
     *  ignored.
     */
    template<typename ColorMap>
    struct darken_and_push
    {
      typedef typename property_traits<ColorMap>::key_type argument_type;
      typedef bool result_type;

explicit darken_and_push(const ColorMap& color) : color(color) { }

bool operator()(const argument_type& value) const
      {
        typedef color_traits<typename property_traits<ColorMap>::value_type>
          Color;
        if (get(color, value) == Color::white()) {
          put(color, value, Color::gray());
          return true;
        } else {
          return false;
        }
      }

ColorMap color;
    };

template<typename IndexMap>
    struct has_not_been_seen
    {
      typedef bool result_type;

has_not_been_seen() { }

has_not_been_seen(std::size_t n, IndexMap index_map)
        : seen(n), index_map(index_map) {}

template<typename Key>
      result_type operator()(Key key)
      {
        bool result = seen[get(index_map, key)];
        seen[get(index_map, key)] = true;
        return !result;
      }

void swap(has_not_been_seen& other)
      {
        using std::swap;
        swap(seen, other.seen);
        swap(index_map, other.index_map);
      }

private:
      dynamic_bitset<> seen;
      IndexMap index_map;
    };

template<typename IndexMap>
    inline void
    swap(has_not_been_seen<IndexMap>& x, has_not_been_seen<IndexMap>& y)
    {
      x.swap(y);
    }

template <class DistributedGraph, class ColorMap, class BFSVisitor,
              class BufferRef, class VertexIndexMap>
    inline void
    parallel_bfs_helper
      (DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       ColorMap color,
       BFSVisitor vis,
       BufferRef Q,
       VertexIndexMap)
    {
      set_property_map_role(vertex_color, color);
      color.set_consistency_model(0);
      breadth_first_search(g, s, Q.ref, vis, color);
    }

template <class DistributedGraph, class ColorMap, class BFSVisitor,
              class VertexIndexMap>
    void parallel_bfs_helper
      (DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       ColorMap color,
       BFSVisitor vis,
       boost::param_not_found,
       VertexIndexMap vertex_index)
    {
      using boost::graph::parallel::process_group;

typedef graph_traits<DistributedGraph> Traits;
      typedef typename Traits::vertex_descriptor Vertex;
      typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type 
        process_group_type;

set_property_map_role(vertex_color, color);
      color.set_consistency_model(0);

// Buffer default
      typedef typename property_map<DistributedGraph, vertex_owner_t>
        ::const_type vertex_owner_map;
      typedef boost::graph::distributed::distributed_queue<
                process_group_type, vertex_owner_map, queue<Vertex>, 
                detail::darken_and_push<ColorMap> > queue_t;
      queue_t Q(process_group(g),
                get(vertex_owner, g),
                detail::darken_and_push<ColorMap>(color));
      breadth_first_search(g, s, Q, vis, color);
    }

template <class DistributedGraph, class ColorMap, class BFSVisitor,
              class P, class T, class R>
    void bfs_helper
      (DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       ColorMap color,
       BFSVisitor vis,
       const bgl_named_params<P, T, R>& params,
       boost::mpl::true_)
        {
            parallel_bfs_helper
        (g, s, color, vis, get_param(params, buffer_param_t()),
         choose_const_pmap(get_param(params, vertex_index),  g, vertex_index));
        }
  }
}

#endif // BOOST_GRAPH_PARALLEL_BFS_HPP

// Copyright 2004 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 #ifndef BOOST_GRAPH_PARALLEL_BFS_HPP #define BOOST_GRAPH_PARALLEL_BFS_HPP #ifndef BOOST_GRAPH_USE_MPI #error "Parallel BGL files should not be included unless has been included" #endif #include #include #include #include #include #include #include #include #include namespace boost { namespace detail { /** @brief A unary predicate that decides when to push into a * breadth-first search queue. * * This predicate stores a color map that is used to determine * when to push. If it is provided with a key for which the color * is white, it darkens the color to gray and returns true (so * that the value will be pushed appropriately); if the color is * not white, it returns false so that the vertex will be * ignored. */ template struct darken_and_push { typedef typename property_traits::key_type argument_type; typedef bool result_type; explicit darken_and_push(const ColorMap& color) : color(color) { } bool operator()(const argument_type& value) const { typedef color_traits::value_type> Color; if (get(color, value) == Color::white()) { put(color, value, Color::gray()); return true; } else { return false; } } ColorMap color; }; template struct has_not_been_seen { typedef bool result_type; has_not_been_seen() { } has_not_been_seen(std::size_t n, IndexMap index_map) : seen(n), index_map(index_map) {} template result_type operator()(Key key) { bool result = seen[get(index_map, key)]; seen[get(index_map, key)] = true; return !result; } void swap(has_not_been_seen& other) { using std::swap; swap(seen, other.seen); swap(index_map, other.index_map); } private: dynamic_bitset<> seen; IndexMap index_map; }; template inline void swap(has_not_been_seen& x, has_not_been_seen& y) { x.swap(y); } template inline void parallel_bfs_helper (DistributedGraph& g, typename graph_traits::vertex_descriptor s, ColorMap color, BFSVisitor vis, BufferRef Q, VertexIndexMap) { set_property_map_role(vertex_color, color); color.set_consistency_model(0); breadth_first_search(g, s, Q.ref, vis, color); } template void parallel_bfs_helper (DistributedGraph& g, typename graph_traits::vertex_descriptor s, ColorMap color, BFSVisitor vis, boost::param_not_found, VertexIndexMap vertex_index) { using boost::graph::parallel::process_group; typedef graph_traits Traits; typedef typename Traits::vertex_descriptor Vertex; typedef typename boost::graph::parallel::process_group_type::type process_group_type; set_property_map_role(vertex_color, color); color.set_consistency_model(0); // Buffer default typedef typename property_map ::const_type vertex_owner_map; typedef boost::graph::distributed::distributed_queue< process_group_type, vertex_owner_map, queue, detail::darken_and_push > queue_t; queue_t Q(process_group(g), get(vertex_owner, g), detail::darken_and_push(color)); breadth_first_search(g, s, Q, vis, color); } template void bfs_helper (DistributedGraph& g, typename graph_traits::vertex_descriptor s, ColorMap color, BFSVisitor vis, const bgl_named_params& params, boost::mpl::true_) { parallel_bfs_helper (g, s, color, vis, get_param(params, buffer_param_t()), choose_const_pmap(get_param(params, vertex_index), g, vertex_index)); } } } #endif // BOOST_GRAPH_PARALLEL_BFS_HPP