--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ossrv_pub/boost_apis/boost/graph/floyd_warshall_shortest.hpp Tue Feb 02 02:01:42 2010 +0200
@@ -0,0 +1,251 @@
+// Copyright 2002 Rensselaer Polytechnic Institute
+
+// 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)
+
+// Authors: Lauren Foutz
+// Scott Hill
+
+/*
+ This file implements the functions
+
+ template <class VertexListGraph, class DistanceMatrix,
+ class P, class T, class R>
+ bool floyd_warshall_initialized_all_pairs_shortest_paths(
+ const VertexListGraph& g, DistanceMatrix& d,
+ const bgl_named_params<P, T, R>& params)
+
+ AND
+
+ template <class VertexAndEdgeListGraph, class DistanceMatrix,
+ class P, class T, class R>
+ bool floyd_warshall_all_pairs_shortest_paths(
+ const VertexAndEdgeListGraph& g, DistanceMatrix& d,
+ const bgl_named_params<P, T, R>& params)
+*/
+
+
+#ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP
+#define BOOST_GRAPH_FLOYD_WARSHALL_HPP
+
+#include <boost/property_map.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/named_function_params.hpp>
+#include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/relax.hpp>
+
+namespace boost
+{
+ namespace detail {
+ template<typename T, typename BinaryPredicate>
+ T min_with_compare(const T& x, const T& y, const BinaryPredicate& compare)
+ {
+ if (compare(x, y)) return x;
+ else return y;
+ }
+
+ template<typename VertexListGraph, typename DistanceMatrix,
+ typename BinaryPredicate, typename BinaryFunction,
+ typename Infinity, typename Zero>
+ bool floyd_warshall_dispatch(const VertexListGraph& g,
+ DistanceMatrix& d, const BinaryPredicate &compare,
+ const BinaryFunction &combine, const Infinity& inf,
+ const Zero& zero)
+ {
+ typename graph_traits<VertexListGraph>::vertex_iterator
+ i, lasti, j, lastj, k, lastk;
+
+
+ for (tie(k, lastk) = vertices(g); k != lastk; k++)
+ for (tie(i, lasti) = vertices(g); i != lasti; i++)
+ for (tie(j, lastj) = vertices(g); j != lastj; j++)
+ {
+ d[*i][*j] =
+ detail::min_with_compare(d[*i][*j],
+ combine(d[*i][*k], d[*k][*j]),
+ compare);
+ }
+
+
+ for (tie(i, lasti) = vertices(g); i != lasti; i++)
+ if (compare(d[*i][*i], zero))
+ return false;
+ return true;
+ }
+ }
+
+ template <typename VertexListGraph, typename DistanceMatrix,
+ typename BinaryPredicate, typename BinaryFunction,
+ typename Infinity, typename Zero>
+ bool floyd_warshall_initialized_all_pairs_shortest_paths(
+ const VertexListGraph& g, DistanceMatrix& d,
+ const BinaryPredicate& compare,
+ const BinaryFunction& combine, const Infinity& inf,
+ const Zero& zero)
+ {
+ function_requires<VertexListGraphConcept<VertexListGraph> >();
+
+ return detail::floyd_warshall_dispatch(g, d, compare, combine,
+ inf, zero);
+ }
+
+
+
+ template <typename VertexAndEdgeListGraph, typename DistanceMatrix,
+ typename WeightMap, typename BinaryPredicate,
+ typename BinaryFunction, typename Infinity, typename Zero>
+ bool floyd_warshall_all_pairs_shortest_paths(
+ const VertexAndEdgeListGraph& g,
+ DistanceMatrix& d, const WeightMap& w,
+ const BinaryPredicate& compare, const BinaryFunction& combine,
+ const Infinity& inf, const Zero& zero)
+ {
+ function_requires<VertexListGraphConcept<VertexAndEdgeListGraph> >();
+ function_requires<EdgeListGraphConcept<VertexAndEdgeListGraph> >();
+ function_requires<IncidenceGraphConcept<VertexAndEdgeListGraph> >();
+
+ typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator
+ firstv, lastv, firstv2, lastv2;
+ typename graph_traits<VertexAndEdgeListGraph>::edge_iterator first, last;
+
+
+ for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
+ for(tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++)
+ d[*firstv][*firstv2] = inf;
+
+
+ for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
+ d[*firstv][*firstv] = zero;
+
+
+ for(tie(first, last) = edges(g); first != last; first++)
+ {
+ if (d[source(*first, g)][target(*first, g)] != inf) {
+ d[source(*first, g)][target(*first, g)] =
+ detail::min_with_compare(
+ get(w, *first),
+ d[source(*first, g)][target(*first, g)],
+ compare);
+ } else
+ d[source(*first, g)][target(*first, g)] = get(w, *first);
+ }
+
+ bool is_undirected = is_same<typename
+ graph_traits<VertexAndEdgeListGraph>::directed_category,
+ undirected_tag>::value;
+ if (is_undirected)
+ {
+ for(tie(first, last) = edges(g); first != last; first++)
+ {
+ if (d[target(*first, g)][source(*first, g)] != inf)
+ d[target(*first, g)][source(*first, g)] =
+ detail::min_with_compare(
+ get(w, *first),
+ d[target(*first, g)][source(*first, g)],
+ compare);
+ else
+ d[target(*first, g)][source(*first, g)] = get(w, *first);
+ }
+ }
+
+
+ return detail::floyd_warshall_dispatch(g, d, compare, combine,
+ inf, zero);
+ }
+
+
+ namespace detail {
+ template <class VertexListGraph, class DistanceMatrix,
+ class WeightMap, class P, class T, class R>
+ bool floyd_warshall_init_dispatch(const VertexListGraph& g,
+ DistanceMatrix& d, WeightMap w,
+ const bgl_named_params<P, T, R>& params)
+ {
+ typedef typename property_traits<WeightMap>::value_type WM;
+
+ return floyd_warshall_initialized_all_pairs_shortest_paths(g, d,
+ choose_param(get_param(params, distance_compare_t()),
+ std::less<WM>()),
+ choose_param(get_param(params, distance_combine_t()),
+ closed_plus<WM>()),
+ choose_param(get_param(params, distance_inf_t()),
+ std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
+ choose_param(get_param(params, distance_zero_t()),
+ WM()));
+ }
+
+
+
+ template <class VertexAndEdgeListGraph, class DistanceMatrix,
+ class WeightMap, class P, class T, class R>
+ bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g,
+ DistanceMatrix& d, WeightMap w,
+ const bgl_named_params<P, T, R>& params)
+ {
+ typedef typename property_traits<WeightMap>::value_type WM;
+
+ return floyd_warshall_all_pairs_shortest_paths(g, d, w,
+ choose_param(get_param(params, distance_compare_t()),
+ std::less<WM>()),
+ choose_param(get_param(params, distance_combine_t()),
+ closed_plus<WM>()),
+ choose_param(get_param(params, distance_inf_t()),
+ std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
+ choose_param(get_param(params, distance_zero_t()),
+ WM()));
+ }
+
+
+ } // namespace detail
+
+
+
+ template <class VertexListGraph, class DistanceMatrix, class P,
+ class T, class R>
+ bool floyd_warshall_initialized_all_pairs_shortest_paths(
+ const VertexListGraph& g, DistanceMatrix& d,
+ const bgl_named_params<P, T, R>& params)
+ {
+ return detail::floyd_warshall_init_dispatch(g, d,
+ choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
+ params);
+ }
+
+ template <class VertexListGraph, class DistanceMatrix>
+ bool floyd_warshall_initialized_all_pairs_shortest_paths(
+ const VertexListGraph& g, DistanceMatrix& d)
+ {
+ bgl_named_params<int,int> params(0);
+ return detail::floyd_warshall_init_dispatch(g, d,
+ get(edge_weight, g), params);
+ }
+
+
+
+
+ template <class VertexAndEdgeListGraph, class DistanceMatrix,
+ class P, class T, class R>
+ bool floyd_warshall_all_pairs_shortest_paths(
+ const VertexAndEdgeListGraph& g, DistanceMatrix& d,
+ const bgl_named_params<P, T, R>& params)
+ {
+ return detail::floyd_warshall_noninit_dispatch(g, d,
+ choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
+ params);
+ }
+
+ template <class VertexAndEdgeListGraph, class DistanceMatrix>
+ bool floyd_warshall_all_pairs_shortest_paths(
+ const VertexAndEdgeListGraph& g, DistanceMatrix& d)
+ {
+ bgl_named_params<int,int> params(0);
+ return detail::floyd_warshall_noninit_dispatch(g, d,
+ get(edge_weight, g), params);
+ }
+
+
+} // namespace boost
+
+#endif
+