source: NonGTP/Boost/boost/graph/prim_minimum_spanning_tree.hpp @ 857

Revision 857, 3.1 KB checked in by igarcia, 19 years ago (diff)
Line 
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
Note: See TracBrowser for help on using the repository browser.