ceph/src/boost/boost/graph/prim_minimum_spanning_tree.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9 //
  10 #ifndef BOOST_GRAPH_MST_PRIM_HPP
  11 #define BOOST_GRAPH_MST_PRIM_HPP
  12
  13 #include <functional>
  14 #include <boost/graph/graph_traits.hpp>
  15 #include <boost/graph/dijkstra_shortest_paths.hpp>
  16
  17 namespace boost
  18 {
  19
  20 namespace detail
  21 {
  22     // this should be somewhere else in boost...
  23     template < class U, class V > struct _project2nd
  24     {
  25         V operator()(U, V v) const { return v; }
  26     };
  27 }
  28
  29 namespace detail
  30 {
  31
  32     // This is Prim's algorithm to calculate the Minimum Spanning Tree
  33     // for an undirected graph with weighted edges.
  34
  35     template < class Graph, class P, class T, class R, class Weight >
  36     inline void prim_mst_impl(const Graph& G,
  37         typename graph_traits< Graph >::vertex_descriptor s,
  38         const bgl_named_params< P, T, R >& params, Weight)
  39     {
  40         typedef typename property_traits< Weight >::value_type W;
  41         std::less< W > compare;
  42         detail::_project2nd< W, W > combine;
  43         dijkstra_shortest_paths(
  44             G, s, params.distance_compare(compare).distance_combine(combine));
  45     }
  46 } // namespace detail
  47
  48 template < class VertexListGraph, class DijkstraVisitor, class PredecessorMap,
  49     class DistanceMap, class WeightMap, class IndexMap >
  50 inline void prim_minimum_spanning_tree(const VertexListGraph& g,
  51     typename graph_traits< VertexListGraph >::vertex_descriptor s,
  52     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
  53     IndexMap index_map, DijkstraVisitor vis)
  54 {
  55     typedef typename property_traits< WeightMap >::value_type W;
  56     std::less< W > compare;
  57     detail::_project2nd< W, W > combine;
  58     dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,
  59         compare, combine, (std::numeric_limits< W >::max)(), 0, vis);
  60 }
  61
  62 template < class VertexListGraph, class PredecessorMap, class P, class T,
  63     class R >
  64 inline void prim_minimum_spanning_tree(const VertexListGraph& g,
  65     PredecessorMap p_map, const bgl_named_params< P, T, R >& params)
  66 {
  67     detail::prim_mst_impl(g,
  68         choose_param(get_param(params, root_vertex_t()), *vertices(g).first),
  69         params.predecessor_map(p_map),
  70         choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
  71 }
  72
  73 template < class VertexListGraph, class PredecessorMap >
  74 inline void prim_minimum_spanning_tree(
  75     const VertexListGraph& g, PredecessorMap p_map)
  76 {
  77     detail::prim_mst_impl(g, *vertices(g).first,
  78         predecessor_map(p_map).weight_map(get(edge_weight, g)),
  79         get(edge_weight, g));
  80 }
  81
  82 } // namespace boost
  83
  84 #endif // BOOST_GRAPH_MST_PRIM_HPP