257 lines
8.4 KiB
C++
257 lines
8.4 KiB
C++
// 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/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>
|
|
#include <boost/concept/assert.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 (boost::tie(k, lastk) = vertices(g); k != lastk; k++)
|
|
for (boost::tie(i, lasti) = vertices(g); i != lasti; i++)
|
|
if(d[*i][*k] != inf)
|
|
for (boost::tie(j, lastj) = vertices(g); j != lastj; j++)
|
|
if(d[*k][*j] != inf)
|
|
d[*i][*j] =
|
|
detail::min_with_compare(d[*i][*j],
|
|
combine(d[*i][*k], d[*k][*j]),
|
|
compare);
|
|
|
|
|
|
for (boost::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)
|
|
{
|
|
BOOST_CONCEPT_ASSERT(( 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)
|
|
{
|
|
BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<VertexAndEdgeListGraph> ));
|
|
BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<VertexAndEdgeListGraph> ));
|
|
BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<VertexAndEdgeListGraph> ));
|
|
|
|
typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator
|
|
firstv, lastv, firstv2, lastv2;
|
|
typename graph_traits<VertexAndEdgeListGraph>::edge_iterator first, last;
|
|
|
|
|
|
for(boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
|
|
for(boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++)
|
|
d[*firstv][*firstv2] = inf;
|
|
|
|
|
|
for(boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
|
|
d[*firstv][*firstv] = zero;
|
|
|
|
|
|
for(boost::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(boost::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;
|
|
WM inf =
|
|
choose_param(get_param(params, distance_inf_t()),
|
|
std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION());
|
|
|
|
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>(inf)),
|
|
inf,
|
|
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;
|
|
|
|
WM inf =
|
|
choose_param(get_param(params, distance_inf_t()),
|
|
std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION());
|
|
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>(inf)),
|
|
inf,
|
|
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
|
|
|