1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/prim_minimum_spanning_tree.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,91 @@
     1.4 +//=======================================================================
     1.5 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
     1.6 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     1.7 +//
     1.8 +// Distributed under the Boost Software License, Version 1.0. (See
     1.9 +// accompanying file LICENSE_1_0.txt or copy at
    1.10 +// http://www.boost.org/LICENSE_1_0.txt)
    1.11 +//=======================================================================
    1.12 +//
    1.13 +#ifndef BOOST_GRAPH_MST_PRIM_HPP
    1.14 +#define BOOST_GRAPH_MST_PRIM_HPP
    1.15 +
    1.16 +#include <functional>
    1.17 +#include <boost/graph/graph_traits.hpp>
    1.18 +#include <boost/graph/dijkstra_shortest_paths.hpp>
    1.19 +
    1.20 +namespace boost {
    1.21 +  
    1.22 +  namespace detail {
    1.23 +    // this should be somewhere else in boost...
    1.24 +    template <class U, class V> struct _project2nd {
    1.25 +      V operator()(U, V v) const { return v; }
    1.26 +    };
    1.27 +  }
    1.28 +
    1.29 +  namespace detail {
    1.30 +
    1.31 +    // This is Prim's algorithm to calculate the Minimum Spanning Tree
    1.32 +    // for an undirected graph with weighted edges.
    1.33 +
    1.34 +    template <class Graph, class P, class T, class R, class Weight>
    1.35 +    inline void
    1.36 +    prim_mst_impl(const Graph& G,
    1.37 +                  typename graph_traits<Graph>::vertex_descriptor s,
    1.38 +                  const bgl_named_params<P,T,R>& params,
    1.39 +                  Weight)
    1.40 +    {
    1.41 +      typedef typename property_traits<Weight>::value_type W;
    1.42 +      std::less<W> compare;
    1.43 +      detail::_project2nd<W,W> combine;
    1.44 +      dijkstra_shortest_paths(G, s, params.distance_compare(compare).
    1.45 +                              distance_combine(combine));
    1.46 +    }
    1.47 +  } // namespace detail
    1.48 +
    1.49 +  template <class VertexListGraph, class DijkstraVisitor, 
    1.50 +            class PredecessorMap, class DistanceMap,
    1.51 +            class WeightMap, class IndexMap>
    1.52 +  inline void
    1.53 +  prim_minimum_spanning_tree
    1.54 +    (const VertexListGraph& g,
    1.55 +     typename graph_traits<VertexListGraph>::vertex_descriptor s, 
    1.56 +     PredecessorMap predecessor, DistanceMap distance, WeightMap weight, 
    1.57 +     IndexMap index_map,
    1.58 +     DijkstraVisitor vis)
    1.59 +  {
    1.60 +    typedef typename property_traits<WeightMap>::value_type W;
    1.61 +    std::less<W> compare;
    1.62 +    detail::_project2nd<W,W> combine;
    1.63 +    dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,
    1.64 +                            compare, combine, (std::numeric_limits<W>::max)(), 0,
    1.65 +                            vis);
    1.66 +  }
    1.67 +
    1.68 +  template <class VertexListGraph, class PredecessorMap,
    1.69 +            class P, class T, class R>
    1.70 +  inline void prim_minimum_spanning_tree
    1.71 +    (const VertexListGraph& g,
    1.72 +     PredecessorMap p_map,
    1.73 +     const bgl_named_params<P,T,R>& params)
    1.74 +  {
    1.75 +    detail::prim_mst_impl
    1.76 +      (g, 
    1.77 +       choose_param(get_param(params, root_vertex_t()), *vertices(g).first), 
    1.78 +       params.predecessor_map(p_map),
    1.79 +       choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
    1.80 +  }
    1.81 +
    1.82 +  template <class VertexListGraph, class PredecessorMap>
    1.83 +  inline void prim_minimum_spanning_tree
    1.84 +    (const VertexListGraph& g, PredecessorMap p_map)
    1.85 +  {
    1.86 +    detail::prim_mst_impl
    1.87 +      (g, *vertices(g).first, predecessor_map(p_map).
    1.88 +       weight_map(get(edge_weight, g)),
    1.89 +       get(edge_weight, g));
    1.90 +  }
    1.91 +
    1.92 +} // namespace boost
    1.93 +
    1.94 +#endif // BOOST_GRAPH_MST_PRIM_HPP