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 {
operator ()boost::detail::_project2nd25 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 >
prim_mst_impl(const Graph & G,typename graph_traits<Graph>::vertex_descriptor s,const bgl_named_params<P,T,R> & params,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 >
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 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 >
prim_minimum_spanning_tree(const VertexListGraph & g,PredecessorMap p_map,const bgl_named_params<P,T,R> & params)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 >
prim_minimum_spanning_tree(const VertexListGraph & g,PredecessorMap p_map)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
85