//======================================================================= | |
// 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 |