Chris@16: //=======================================================================
Chris@16: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: #ifndef BOOST_GRAPH_MST_PRIM_HPP
Chris@16: #define BOOST_GRAPH_MST_PRIM_HPP
Chris@16: 
Chris@16: #include <functional>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/dijkstra_shortest_paths.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16:   
Chris@16:   namespace detail {
Chris@16:     // this should be somewhere else in boost...
Chris@16:     template <class U, class V> struct _project2nd {
Chris@16:       V operator()(U, V v) const { return v; }
Chris@16:     };
Chris@16:   }
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     // This is Prim's algorithm to calculate the Minimum Spanning Tree
Chris@16:     // for an undirected graph with weighted edges.
Chris@16: 
Chris@16:     template <class Graph, class P, class T, class R, class Weight>
Chris@16:     inline void
Chris@16:     prim_mst_impl(const Graph& G,
Chris@16:                   typename graph_traits<Graph>::vertex_descriptor s,
Chris@16:                   const bgl_named_params<P,T,R>& params,
Chris@16:                   Weight)
Chris@16:     {
Chris@16:       typedef typename property_traits<Weight>::value_type W;
Chris@16:       std::less<W> compare;
Chris@16:       detail::_project2nd<W,W> combine;
Chris@16:       dijkstra_shortest_paths(G, s, params.distance_compare(compare).
Chris@16:                               distance_combine(combine));
Chris@16:     }
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   template <class VertexListGraph, class DijkstraVisitor, 
Chris@16:             class PredecessorMap, class DistanceMap,
Chris@16:             class WeightMap, class IndexMap>
Chris@16:   inline void
Chris@16:   prim_minimum_spanning_tree
Chris@16:     (const VertexListGraph& g,
Chris@16:      typename graph_traits<VertexListGraph>::vertex_descriptor s, 
Chris@16:      PredecessorMap predecessor, DistanceMap distance, WeightMap weight, 
Chris@16:      IndexMap index_map,
Chris@16:      DijkstraVisitor vis)
Chris@16:   {
Chris@16:     typedef typename property_traits<WeightMap>::value_type W;
Chris@16:     std::less<W> compare;
Chris@16:     detail::_project2nd<W,W> combine;
Chris@16:     dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,
Chris@16:                             compare, combine, (std::numeric_limits<W>::max)(), 0,
Chris@16:                             vis);
Chris@16:   }
Chris@16: 
Chris@16:   template <class VertexListGraph, class PredecessorMap,
Chris@16:             class P, class T, class R>
Chris@16:   inline void prim_minimum_spanning_tree
Chris@16:     (const VertexListGraph& g,
Chris@16:      PredecessorMap p_map,
Chris@16:      const bgl_named_params<P,T,R>& params)
Chris@16:   {
Chris@16:     detail::prim_mst_impl
Chris@16:       (g, 
Chris@16:        choose_param(get_param(params, root_vertex_t()), *vertices(g).first), 
Chris@16:        params.predecessor_map(p_map),
Chris@16:        choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
Chris@16:   }
Chris@16: 
Chris@16:   template <class VertexListGraph, class PredecessorMap>
Chris@16:   inline void prim_minimum_spanning_tree
Chris@16:     (const VertexListGraph& g, PredecessorMap p_map)
Chris@16:   {
Chris@16:     detail::prim_mst_impl
Chris@16:       (g, *vertices(g).first, predecessor_map(p_map).
Chris@16:        weight_map(get(edge_weight, g)),
Chris@16:        get(edge_weight, g));
Chris@16:   }
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_MST_PRIM_HPP