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
17namespace boost {
18
19 namespace detail {
20 // this should be somewhere else in boost...
21 template <class U, class V> struct _project2nd {
22 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
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
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>
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>
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

source code of boost/boost/graph/prim_minimum_spanning_tree.hpp