Edit: /usr/include/boost/graph/floyd_warshall_shortest.hpp (8510B)
// 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
bool floyd_warshall_initialized_all_pairs_shortest_paths(
const VertexListGraph& g, DistanceMatrix& d,
const bgl_named_params& params)
AND
template
bool floyd_warshall_all_pairs_shortest_paths(
const VertexAndEdgeListGraph& g, DistanceMatrix& d,
const bgl_named_params& params)
*/
#ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP
#define BOOST_GRAPH_FLOYD_WARSHALL_HPP
#include
#include
#include
#include
#include
#include
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