1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/floyd_warshall_shortest.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,251 @@
1.4 +// Copyright 2002 Rensselaer Polytechnic Institute
1.5 +
1.6 +// Distributed under the Boost Software License, Version 1.0.
1.7 +// (See accompanying file LICENSE_1_0.txt or copy at
1.8 +// http://www.boost.org/LICENSE_1_0.txt)
1.9 +
1.10 +// Authors: Lauren Foutz
1.11 +// Scott Hill
1.12 +
1.13 +/*
1.14 + This file implements the functions
1.15 +
1.16 + template <class VertexListGraph, class DistanceMatrix,
1.17 + class P, class T, class R>
1.18 + bool floyd_warshall_initialized_all_pairs_shortest_paths(
1.19 + const VertexListGraph& g, DistanceMatrix& d,
1.20 + const bgl_named_params<P, T, R>& params)
1.21 +
1.22 + AND
1.23 +
1.24 + template <class VertexAndEdgeListGraph, class DistanceMatrix,
1.25 + class P, class T, class R>
1.26 + bool floyd_warshall_all_pairs_shortest_paths(
1.27 + const VertexAndEdgeListGraph& g, DistanceMatrix& d,
1.28 + const bgl_named_params<P, T, R>& params)
1.29 +*/
1.30 +
1.31 +
1.32 +#ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP
1.33 +#define BOOST_GRAPH_FLOYD_WARSHALL_HPP
1.34 +
1.35 +#include <boost/property_map.hpp>
1.36 +#include <boost/graph/graph_traits.hpp>
1.37 +#include <boost/graph/named_function_params.hpp>
1.38 +#include <boost/graph/graph_concepts.hpp>
1.39 +#include <boost/graph/relax.hpp>
1.40 +
1.41 +namespace boost
1.42 +{
1.43 + namespace detail {
1.44 + template<typename T, typename BinaryPredicate>
1.45 + T min_with_compare(const T& x, const T& y, const BinaryPredicate& compare)
1.46 + {
1.47 + if (compare(x, y)) return x;
1.48 + else return y;
1.49 + }
1.50 +
1.51 + template<typename VertexListGraph, typename DistanceMatrix,
1.52 + typename BinaryPredicate, typename BinaryFunction,
1.53 + typename Infinity, typename Zero>
1.54 + bool floyd_warshall_dispatch(const VertexListGraph& g,
1.55 + DistanceMatrix& d, const BinaryPredicate &compare,
1.56 + const BinaryFunction &combine, const Infinity& inf,
1.57 + const Zero& zero)
1.58 + {
1.59 + typename graph_traits<VertexListGraph>::vertex_iterator
1.60 + i, lasti, j, lastj, k, lastk;
1.61 +
1.62 +
1.63 + for (tie(k, lastk) = vertices(g); k != lastk; k++)
1.64 + for (tie(i, lasti) = vertices(g); i != lasti; i++)
1.65 + for (tie(j, lastj) = vertices(g); j != lastj; j++)
1.66 + {
1.67 + d[*i][*j] =
1.68 + detail::min_with_compare(d[*i][*j],
1.69 + combine(d[*i][*k], d[*k][*j]),
1.70 + compare);
1.71 + }
1.72 +
1.73 +
1.74 + for (tie(i, lasti) = vertices(g); i != lasti; i++)
1.75 + if (compare(d[*i][*i], zero))
1.76 + return false;
1.77 + return true;
1.78 + }
1.79 + }
1.80 +
1.81 + template <typename VertexListGraph, typename DistanceMatrix,
1.82 + typename BinaryPredicate, typename BinaryFunction,
1.83 + typename Infinity, typename Zero>
1.84 + bool floyd_warshall_initialized_all_pairs_shortest_paths(
1.85 + const VertexListGraph& g, DistanceMatrix& d,
1.86 + const BinaryPredicate& compare,
1.87 + const BinaryFunction& combine, const Infinity& inf,
1.88 + const Zero& zero)
1.89 + {
1.90 + function_requires<VertexListGraphConcept<VertexListGraph> >();
1.91 +
1.92 + return detail::floyd_warshall_dispatch(g, d, compare, combine,
1.93 + inf, zero);
1.94 + }
1.95 +
1.96 +
1.97 +
1.98 + template <typename VertexAndEdgeListGraph, typename DistanceMatrix,
1.99 + typename WeightMap, typename BinaryPredicate,
1.100 + typename BinaryFunction, typename Infinity, typename Zero>
1.101 + bool floyd_warshall_all_pairs_shortest_paths(
1.102 + const VertexAndEdgeListGraph& g,
1.103 + DistanceMatrix& d, const WeightMap& w,
1.104 + const BinaryPredicate& compare, const BinaryFunction& combine,
1.105 + const Infinity& inf, const Zero& zero)
1.106 + {
1.107 + function_requires<VertexListGraphConcept<VertexAndEdgeListGraph> >();
1.108 + function_requires<EdgeListGraphConcept<VertexAndEdgeListGraph> >();
1.109 + function_requires<IncidenceGraphConcept<VertexAndEdgeListGraph> >();
1.110 +
1.111 + typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator
1.112 + firstv, lastv, firstv2, lastv2;
1.113 + typename graph_traits<VertexAndEdgeListGraph>::edge_iterator first, last;
1.114 +
1.115 +
1.116 + for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
1.117 + for(tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++)
1.118 + d[*firstv][*firstv2] = inf;
1.119 +
1.120 +
1.121 + for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
1.122 + d[*firstv][*firstv] = zero;
1.123 +
1.124 +
1.125 + for(tie(first, last) = edges(g); first != last; first++)
1.126 + {
1.127 + if (d[source(*first, g)][target(*first, g)] != inf) {
1.128 + d[source(*first, g)][target(*first, g)] =
1.129 + detail::min_with_compare(
1.130 + get(w, *first),
1.131 + d[source(*first, g)][target(*first, g)],
1.132 + compare);
1.133 + } else
1.134 + d[source(*first, g)][target(*first, g)] = get(w, *first);
1.135 + }
1.136 +
1.137 + bool is_undirected = is_same<typename
1.138 + graph_traits<VertexAndEdgeListGraph>::directed_category,
1.139 + undirected_tag>::value;
1.140 + if (is_undirected)
1.141 + {
1.142 + for(tie(first, last) = edges(g); first != last; first++)
1.143 + {
1.144 + if (d[target(*first, g)][source(*first, g)] != inf)
1.145 + d[target(*first, g)][source(*first, g)] =
1.146 + detail::min_with_compare(
1.147 + get(w, *first),
1.148 + d[target(*first, g)][source(*first, g)],
1.149 + compare);
1.150 + else
1.151 + d[target(*first, g)][source(*first, g)] = get(w, *first);
1.152 + }
1.153 + }
1.154 +
1.155 +
1.156 + return detail::floyd_warshall_dispatch(g, d, compare, combine,
1.157 + inf, zero);
1.158 + }
1.159 +
1.160 +
1.161 + namespace detail {
1.162 + template <class VertexListGraph, class DistanceMatrix,
1.163 + class WeightMap, class P, class T, class R>
1.164 + bool floyd_warshall_init_dispatch(const VertexListGraph& g,
1.165 + DistanceMatrix& d, WeightMap w,
1.166 + const bgl_named_params<P, T, R>& params)
1.167 + {
1.168 + typedef typename property_traits<WeightMap>::value_type WM;
1.169 +
1.170 + return floyd_warshall_initialized_all_pairs_shortest_paths(g, d,
1.171 + choose_param(get_param(params, distance_compare_t()),
1.172 + std::less<WM>()),
1.173 + choose_param(get_param(params, distance_combine_t()),
1.174 + closed_plus<WM>()),
1.175 + choose_param(get_param(params, distance_inf_t()),
1.176 + std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
1.177 + choose_param(get_param(params, distance_zero_t()),
1.178 + WM()));
1.179 + }
1.180 +
1.181 +
1.182 +
1.183 + template <class VertexAndEdgeListGraph, class DistanceMatrix,
1.184 + class WeightMap, class P, class T, class R>
1.185 + bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g,
1.186 + DistanceMatrix& d, WeightMap w,
1.187 + const bgl_named_params<P, T, R>& params)
1.188 + {
1.189 + typedef typename property_traits<WeightMap>::value_type WM;
1.190 +
1.191 + return floyd_warshall_all_pairs_shortest_paths(g, d, w,
1.192 + choose_param(get_param(params, distance_compare_t()),
1.193 + std::less<WM>()),
1.194 + choose_param(get_param(params, distance_combine_t()),
1.195 + closed_plus<WM>()),
1.196 + choose_param(get_param(params, distance_inf_t()),
1.197 + std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
1.198 + choose_param(get_param(params, distance_zero_t()),
1.199 + WM()));
1.200 + }
1.201 +
1.202 +
1.203 + } // namespace detail
1.204 +
1.205 +
1.206 +
1.207 + template <class VertexListGraph, class DistanceMatrix, class P,
1.208 + class T, class R>
1.209 + bool floyd_warshall_initialized_all_pairs_shortest_paths(
1.210 + const VertexListGraph& g, DistanceMatrix& d,
1.211 + const bgl_named_params<P, T, R>& params)
1.212 + {
1.213 + return detail::floyd_warshall_init_dispatch(g, d,
1.214 + choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
1.215 + params);
1.216 + }
1.217 +
1.218 + template <class VertexListGraph, class DistanceMatrix>
1.219 + bool floyd_warshall_initialized_all_pairs_shortest_paths(
1.220 + const VertexListGraph& g, DistanceMatrix& d)
1.221 + {
1.222 + bgl_named_params<int,int> params(0);
1.223 + return detail::floyd_warshall_init_dispatch(g, d,
1.224 + get(edge_weight, g), params);
1.225 + }
1.226 +
1.227 +
1.228 +
1.229 +
1.230 + template <class VertexAndEdgeListGraph, class DistanceMatrix,
1.231 + class P, class T, class R>
1.232 + bool floyd_warshall_all_pairs_shortest_paths(
1.233 + const VertexAndEdgeListGraph& g, DistanceMatrix& d,
1.234 + const bgl_named_params<P, T, R>& params)
1.235 + {
1.236 + return detail::floyd_warshall_noninit_dispatch(g, d,
1.237 + choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
1.238 + params);
1.239 + }
1.240 +
1.241 + template <class VertexAndEdgeListGraph, class DistanceMatrix>
1.242 + bool floyd_warshall_all_pairs_shortest_paths(
1.243 + const VertexAndEdgeListGraph& g, DistanceMatrix& d)
1.244 + {
1.245 + bgl_named_params<int,int> params(0);
1.246 + return detail::floyd_warshall_noninit_dispatch(g, d,
1.247 + get(edge_weight, g), params);
1.248 + }
1.249 +
1.250 +
1.251 +} // namespace boost
1.252 +
1.253 +#endif
1.254 +