//=======================================================================

 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

 //

 // Distributed under the Boost Software License, Version 1.0. (See

 // accompanying file LICENSE_1_0.txt or copy at

 // http://www.boost.org/LICENSE_1_0.txt)

 //=======================================================================

 //

 #ifndef BOOST_GRAPH_MST_PRIM_HPP

 #define BOOST_GRAPH_MST_PRIM_HPP

 #include <functional>

 #include <boost/graph/graph_traits.hpp>

 #include <boost/graph/dijkstra_shortest_paths.hpp>

 namespace boost {

   namespace detail {

     // this should be somewhere else in boost...

     template <class U, class V> struct _project2nd {

       V operator()(U, V v) const { return v; }

     };

   }

   namespace detail {

     // This is Prim's algorithm to calculate the Minimum Spanning Tree

     // for an undirected graph with weighted edges.

     template <class Graph, class P, class T, class R, class Weight>

     inline void

     prim_mst_impl(const Graph& G,

                   typename graph_traits<Graph>::vertex_descriptor s,

                   const bgl_named_params<P,T,R>& params,

                   Weight)

     {

       typedef typename property_traits<Weight>::value_type W;

       std::less<W> compare;

       detail::_project2nd<W,W> combine;

       dijkstra_shortest_paths(G, s, params.distance_compare(compare).

                               distance_combine(combine));

     }

   } // namespace detail

   template <class VertexListGraph, class DijkstraVisitor, 

             class PredecessorMap, class DistanceMap,

             class WeightMap, class IndexMap>

   inline void

   prim_minimum_spanning_tree

     (const VertexListGraph& g,

      typename graph_traits<VertexListGraph>::vertex_descriptor s, 

      PredecessorMap predecessor, DistanceMap distance, WeightMap weight, 

      IndexMap index_map,

      DijkstraVisitor vis)

   {

     typedef typename property_traits<WeightMap>::value_type W;

     std::less<W> compare;

     detail::_project2nd<W,W> combine;

     dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,

                             compare, combine, (std::numeric_limits<W>::max)(), 0,

                             vis);

   }

   template <class VertexListGraph, class PredecessorMap,

             class P, class T, class R>

   inline void prim_minimum_spanning_tree

     (const VertexListGraph& g,

      PredecessorMap p_map,

      const bgl_named_params<P,T,R>& params)

   {

     detail::prim_mst_impl

       (g, 

        choose_param(get_param(params, root_vertex_t()), *vertices(g).first), 

        params.predecessor_map(p_map),

        choose_const_pmap(get_param(params, edge_weight), g, edge_weight));

   }

   template <class VertexListGraph, class PredecessorMap>

   inline void prim_minimum_spanning_tree

     (const VertexListGraph& g, PredecessorMap p_map)

   {

     detail::prim_mst_impl

       (g, *vertices(g).first, predecessor_map(p_map).

        weight_map(get(edge_weight, g)),

        get(edge_weight, g));

   }

 } // namespace boost

 #endif // BOOST_GRAPH_MST_PRIM_HPP