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