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/dijkstra_shortest_paths.hpp (8719B)

// 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_DIJKSTRA_HPP
#define BOOST_GRAPH_PARALLEL_DIJKSTRA_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/dijkstra_shortest_paths.hpp>
#include <boost/graph/overloading.hpp>
#include <boost/graph/distributed/concepts.hpp>
#include <boost/graph/parallel/properties.hpp>
#include <boost/graph/distributed/crauser_et_al_shortest_paths.hpp>
#include <boost/graph/distributed/eager_dijkstra_shortest_paths.hpp>

namespace boost {

namespace graph { namespace detail {

template<typename Lookahead>
    struct parallel_dijkstra_impl2
    {
      template<typename DistributedGraph, typename DijkstraVisitor,
               typename PredecessorMap, typename DistanceMap, 
               typename WeightMap, typename IndexMap, typename ColorMap, 
               typename Compare, typename Combine, typename DistInf, 
               typename DistZero>
      static void 
      run(const DistributedGraph& g,
          typename graph_traits<DistributedGraph>::vertex_descriptor s,
          PredecessorMap predecessor, DistanceMap distance, 
          typename property_traits<DistanceMap>::value_type lookahead,
          WeightMap weight, IndexMap index_map, ColorMap color_map,
          Compare compare, Combine combine, DistInf inf, DistZero zero,
          DijkstraVisitor vis)
      {
        eager_dijkstra_shortest_paths(g, s, predecessor, distance, lookahead,
                                      weight, index_map, color_map, compare,
                                      combine, inf, zero, vis);
      }
    };

template<>
    struct parallel_dijkstra_impl2< ::boost::param_not_found >
    {
      template<typename DistributedGraph, typename DijkstraVisitor,
               typename PredecessorMap, typename DistanceMap, 
               typename WeightMap, typename IndexMap, typename ColorMap, 
               typename Compare, typename Combine, typename DistInf, 
               typename DistZero>
      static void 
      run(const DistributedGraph& g,
          typename graph_traits<DistributedGraph>::vertex_descriptor s,
          PredecessorMap predecessor, DistanceMap distance, 
          ::boost::param_not_found,
          WeightMap weight, IndexMap index_map, ColorMap color_map,
          Compare compare, Combine combine, DistInf inf, DistZero zero,
          DijkstraVisitor vis)
      {
        crauser_et_al_shortest_paths(g, s, predecessor, distance, weight,
                                     index_map, color_map, compare, combine,
                                     inf, zero, vis);
      }
    };

template<typename ColorMap>
    struct parallel_dijkstra_impl
    {
      template<typename DistributedGraph, typename DijkstraVisitor,
               typename PredecessorMap, typename DistanceMap, 
               typename Lookahead, typename WeightMap, typename IndexMap,
               typename Compare, typename Combine, 
               typename DistInf, typename DistZero>
      static void 
      run(const DistributedGraph& g,
          typename graph_traits<DistributedGraph>::vertex_descriptor s,
          PredecessorMap predecessor, DistanceMap distance, 
          Lookahead lookahead,
          WeightMap weight, IndexMap index_map, ColorMap color_map,
          Compare compare, Combine combine, DistInf inf, DistZero zero,
          DijkstraVisitor vis)
      {
        graph::detail::parallel_dijkstra_impl2<Lookahead>
          ::run(g, s, predecessor, distance, lookahead, weight, index_map,
                color_map, compare, combine, inf, zero, vis);
      }
    };
    
    template<>
    struct parallel_dijkstra_impl< ::boost::param_not_found >
    {
    private:
      template<typename DistributedGraph, typename DijkstraVisitor,
               typename PredecessorMap, typename DistanceMap, 
               typename Lookahead, typename WeightMap, typename IndexMap,
               typename ColorMap, typename Compare, typename Combine, 
               typename DistInf, typename DistZero>
      static void 
      run_impl(const DistributedGraph& g,
               typename graph_traits<DistributedGraph>::vertex_descriptor s,
               PredecessorMap predecessor, DistanceMap distance, 
               Lookahead lookahead, WeightMap weight, IndexMap index_map, 
               ColorMap color_map, Compare compare, Combine combine, 
               DistInf inf, DistZero zero, DijkstraVisitor vis)
      {
        BGL_FORALL_VERTICES_T(u, g, DistributedGraph)
          BGL_FORALL_OUTEDGES_T(u, e, g, DistributedGraph)
            local_put(color_map, target(e, g), white_color);

graph::detail::parallel_dijkstra_impl2<Lookahead>
          ::run(g, s, predecessor, distance, lookahead, weight, index_map,
                color_map, compare, combine, inf, zero, vis);
      }

public:
      template<typename DistributedGraph, typename DijkstraVisitor,
               typename PredecessorMap, typename DistanceMap, 
               typename Lookahead, typename WeightMap, typename IndexMap,
               typename Compare, typename Combine, 
               typename DistInf, typename DistZero>
      static void 
      run(const DistributedGraph& g,
          typename graph_traits<DistributedGraph>::vertex_descriptor s,
          PredecessorMap predecessor, DistanceMap distance, 
          Lookahead lookahead, WeightMap weight, IndexMap index_map, 
          ::boost::param_not_found,
          Compare compare, Combine combine, DistInf inf, DistZero zero,
          DijkstraVisitor vis)
      {
        typedef typename graph_traits<DistributedGraph>::vertices_size_type
          vertices_size_type;

vertices_size_type n = num_vertices(g);
        std::vector<default_color_type> colors(n, white_color);

run_impl(g, s, predecessor, distance, lookahead, weight, index_map,
                 make_iterator_property_map(colors.begin(), index_map),
                 compare, combine, inf, zero, vis);
      }
    };
  } } // end namespace graph::detail

/** Dijkstra's single-source shortest paths algorithm for distributed
   * graphs.
   *
   * Also implements the heuristics of:
   *
   *   Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
   *   Sanders. A Parallelization of Dijkstra's Shortest Path
   *   Algorithm. In Lubos Brim, Jozef Gruska, and Jiri Zlatuska,
   *   editors, Mathematical Foundations of Computer Science (MFCS),
   *   volume 1450 of Lecture Notes in Computer Science, pages
   *   722--731, 1998. Springer.
   */
  template<typename DistributedGraph, typename DijkstraVisitor,
           typename PredecessorMap, typename DistanceMap,
           typename WeightMap, typename IndexMap, typename Compare,
           typename Combine, typename DistInf, typename DistZero,
           typename T, typename Tag, typename Base>
  inline
  void
  dijkstra_shortest_paths
    (const DistributedGraph& g,
     typename graph_traits<DistributedGraph>::vertex_descriptor s,
     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
     IndexMap index_map,
     Compare compare, Combine combine, DistInf inf, DistZero zero,
     DijkstraVisitor vis,
     const bgl_named_params<T, Tag, Base>& params
     BOOST_GRAPH_ENABLE_IF_MODELS_PARM(DistributedGraph,distributed_graph_tag))
  {
    typedef typename graph_traits<DistributedGraph>::vertices_size_type
      vertices_size_type;

// Build a distributed property map for vertex colors, if we need it
    bool use_default_color_map 
      = is_default_param(get_param(params, vertex_color));
    vertices_size_type n = use_default_color_map? num_vertices(g) : 1;
    std::vector<default_color_type> color(n, white_color);
    typedef iterator_property_map<std::vector<default_color_type>::iterator,
                                  IndexMap> DefColorMap;
    DefColorMap color_map(color.begin(), index_map);

typedef typename get_param_type< vertex_color_t, bgl_named_params<T, Tag, Base> >::type color_map_type;

graph::detail::parallel_dijkstra_impl<color_map_type>
      ::run(g, s, predecessor, distance, 
            get_param(params, lookahead_t()),
            weight, index_map,
            get_param(params, vertex_color),
            compare, combine, inf, zero, vis);
  }
} // end namespace boost

#endif // BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP

// Copyright (C) 2004-2006 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_DIJKSTRA_HPP #define BOOST_GRAPH_PARALLEL_DIJKSTRA_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 namespace boost { namespace graph { namespace detail { template struct parallel_dijkstra_impl2 { template static void run(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, PredecessorMap predecessor, DistanceMap distance, typename property_traits::value_type lookahead, WeightMap weight, IndexMap index_map, ColorMap color_map, Compare compare, Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis) { eager_dijkstra_shortest_paths(g, s, predecessor, distance, lookahead, weight, index_map, color_map, compare, combine, inf, zero, vis); } }; template<> struct parallel_dijkstra_impl2< ::boost::param_not_found > { template static void run(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, PredecessorMap predecessor, DistanceMap distance, ::boost::param_not_found, WeightMap weight, IndexMap index_map, ColorMap color_map, Compare compare, Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis) { crauser_et_al_shortest_paths(g, s, predecessor, distance, weight, index_map, color_map, compare, combine, inf, zero, vis); } }; template struct parallel_dijkstra_impl { template static void run(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, PredecessorMap predecessor, DistanceMap distance, Lookahead lookahead, WeightMap weight, IndexMap index_map, ColorMap color_map, Compare compare, Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis) { graph::detail::parallel_dijkstra_impl2 ::run(g, s, predecessor, distance, lookahead, weight, index_map, color_map, compare, combine, inf, zero, vis); } }; template<> struct parallel_dijkstra_impl< ::boost::param_not_found > { private: template static void run_impl(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, PredecessorMap predecessor, DistanceMap distance, Lookahead lookahead, WeightMap weight, IndexMap index_map, ColorMap color_map, Compare compare, Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis) { BGL_FORALL_VERTICES_T(u, g, DistributedGraph) BGL_FORALL_OUTEDGES_T(u, e, g, DistributedGraph) local_put(color_map, target(e, g), white_color); graph::detail::parallel_dijkstra_impl2 ::run(g, s, predecessor, distance, lookahead, weight, index_map, color_map, compare, combine, inf, zero, vis); } public: template static void run(const DistributedGraph& g, typename graph_traits::vertex_descriptor s, PredecessorMap predecessor, DistanceMap distance, Lookahead lookahead, WeightMap weight, IndexMap index_map, ::boost::param_not_found, Compare compare, Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis) { typedef typename graph_traits::vertices_size_type vertices_size_type; vertices_size_type n = num_vertices(g); std::vector colors(n, white_color); run_impl(g, s, predecessor, distance, lookahead, weight, index_map, make_iterator_property_map(colors.begin(), index_map), compare, combine, inf, zero, vis); } }; } } // end namespace graph::detail /** Dijkstra's single-source shortest paths algorithm for distributed * graphs. * * Also implements the heuristics of: * * Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter * Sanders. A Parallelization of Dijkstra's Shortest Path * Algorithm. In Lubos Brim, Jozef Gruska, and Jiri Zlatuska, * editors, Mathematical Foundations of Computer Science (MFCS), * volume 1450 of Lecture Notes in Computer Science, pages * 722--731, 1998. Springer. */ template inline void dijkstra_shortest_paths (const DistributedGraph& g, typename graph_traits::vertex_descriptor s, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, Combine combine, DistInf inf, DistZero zero, DijkstraVisitor vis, const bgl_named_params& params BOOST_GRAPH_ENABLE_IF_MODELS_PARM(DistributedGraph,distributed_graph_tag)) { typedef typename graph_traits::vertices_size_type vertices_size_type; // Build a distributed property map for vertex colors, if we need it bool use_default_color_map = is_default_param(get_param(params, vertex_color)); vertices_size_type n = use_default_color_map? num_vertices(g) : 1; std::vector color(n, white_color); typedef iterator_property_map::iterator, IndexMap> DefColorMap; DefColorMap color_map(color.begin(), index_map); typedef typename get_param_type< vertex_color_t, bgl_named_params >::type color_map_type; graph::detail::parallel_dijkstra_impl ::run(g, s, predecessor, distance, get_param(params, lookahead_t()), weight, index_map, get_param(params, vertex_color), compare, combine, inf, zero, vis); } } // end namespace boost #endif // BOOST_GRAPH_PARALLEL_DIJKSTRA_HPP