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 { |
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 | |