Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / 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   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