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 namespace detail { 20 // this should be somewhere else in boost... 21 template <class U, class V> struct _project2nd { operator ()boost::detail::_project2nd22 V operator()(U, V v) const { return v; } 23 }; 24 } 25 26 namespace detail { 27 28 // This is Prim's algorithm to calculate the Minimum Spanning Tree 29 // for an undirected graph with weighted edges. 30 31 template <class Graph, class P, class T, class R, class Weight> 32 inline void prim_mst_impl(const Graph & G,typename graph_traits<Graph>::vertex_descriptor s,const bgl_named_params<P,T,R> & params,Weight)33 prim_mst_impl(const Graph& G, 34 typename graph_traits<Graph>::vertex_descriptor s, 35 const bgl_named_params<P,T,R>& params, 36 Weight) 37 { 38 typedef typename property_traits<Weight>::value_type W; 39 std::less<W> compare; 40 detail::_project2nd<W,W> combine; 41 dijkstra_shortest_paths(G, s, params.distance_compare(compare). 42 distance_combine(combine)); 43 } 44 } // namespace detail 45 46 template <class VertexListGraph, class DijkstraVisitor, 47 class PredecessorMap, class DistanceMap, 48 class WeightMap, class IndexMap> 49 inline void prim_minimum_spanning_tree(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,PredecessorMap predecessor,DistanceMap distance,WeightMap weight,IndexMap index_map,DijkstraVisitor vis)50 prim_minimum_spanning_tree 51 (const VertexListGraph& g, 52 typename graph_traits<VertexListGraph>::vertex_descriptor s, 53 PredecessorMap predecessor, DistanceMap distance, WeightMap weight, 54 IndexMap index_map, 55 DijkstraVisitor vis) 56 { 57 typedef typename property_traits<WeightMap>::value_type W; 58 std::less<W> compare; 59 detail::_project2nd<W,W> combine; 60 dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map, 61 compare, combine, (std::numeric_limits<W>::max)(), 0, 62 vis); 63 } 64 65 template <class VertexListGraph, class PredecessorMap, 66 class P, class T, class R> prim_minimum_spanning_tree(const VertexListGraph & g,PredecessorMap p_map,const bgl_named_params<P,T,R> & params)67 inline void prim_minimum_spanning_tree 68 (const VertexListGraph& g, 69 PredecessorMap p_map, 70 const bgl_named_params<P,T,R>& params) 71 { 72 detail::prim_mst_impl 73 (g, 74 choose_param(get_param(params, root_vertex_t()), *vertices(g).first), 75 params.predecessor_map(p_map), 76 choose_const_pmap(get_param(params, edge_weight), g, edge_weight)); 77 } 78 79 template <class VertexListGraph, class PredecessorMap> prim_minimum_spanning_tree(const VertexListGraph & g,PredecessorMap p_map)80 inline void prim_minimum_spanning_tree 81 (const VertexListGraph& g, PredecessorMap p_map) 82 { 83 detail::prim_mst_impl 84 (g, *vertices(g).first, predecessor_map(p_map). 85 weight_map(get(edge_weight, g)), 86 get(edge_weight, g)); 87 } 88 89 } // namespace boost 90 91 #endif // BOOST_GRAPH_MST_PRIM_HPP 92