boost/graph/floyd_warshall_shortest.hpp

0001 // Copyright 2002 Rensselaer Polytechnic Institute
0002
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Lauren Foutz
0008 //           Scott Hill
0009
0010 /*
0011   This file implements the functions
0012
0013   template <class VertexListGraph, class DistanceMatrix,
0014     class P, class T, class R>
0015   bool floyd_warshall_initialized_all_pairs_shortest_paths(
0016     const VertexListGraph& g, DistanceMatrix& d,
0017     const bgl_named_params<P, T, R>& params)
0018
0019   AND
0020
0021   template <class VertexAndEdgeListGraph, class DistanceMatrix,
0022     class P, class T, class R>
0023   bool floyd_warshall_all_pairs_shortest_paths(
0024     const VertexAndEdgeListGraph& g, DistanceMatrix& d,
0025     const bgl_named_params<P, T, R>& params)
0026 */
0027
0028 #ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP
0029 #define BOOST_GRAPH_FLOYD_WARSHALL_HPP
0030
0031 #include <boost/property_map/property_map.hpp>
0032 #include <boost/graph/graph_traits.hpp>
0033 #include <boost/graph/named_function_params.hpp>
0034 #include <boost/graph/graph_concepts.hpp>
0035 #include <boost/graph/relax.hpp>
0036 #include <boost/concept/assert.hpp>
0037
0038 namespace boost
0039 {
0040 namespace detail
0041 {
0042     template < typename T, typename BinaryPredicate >
0043     T min_with_compare(const T& x, const T& y, const BinaryPredicate& compare)
0044     {
0045         if (compare(x, y))
0046             return x;
0047         else
0048             return y;
0049     }
0050
0051     template < typename VertexListGraph, typename DistanceMatrix,
0052         typename BinaryPredicate, typename BinaryFunction, typename Infinity,
0053         typename Zero >
0054     bool floyd_warshall_dispatch(const VertexListGraph& g, DistanceMatrix& d,
0055         const BinaryPredicate& compare, const BinaryFunction& combine,
0056         const Infinity& inf, const Zero& zero)
0057     {
0058         typename graph_traits< VertexListGraph >::vertex_iterator i, lasti, j,
0059             lastj, k, lastk;
0060
0061         for (boost::tie(k, lastk) = vertices(g); k != lastk; k++)
0062             for (boost::tie(i, lasti) = vertices(g); i != lasti; i++)
0063                 if (d[*i][*k] != inf)
0064                     for (boost::tie(j, lastj) = vertices(g); j != lastj; j++)
0065                         if (d[*k][*j] != inf)
0066                             d[*i][*j] = detail::min_with_compare(d[*i][*j],
0067                                 combine(d[*i][*k], d[*k][*j]), compare);
0068
0069         for (boost::tie(i, lasti) = vertices(g); i != lasti; i++)
0070             if (compare(d[*i][*i], zero))
0071                 return false;
0072         return true;
0073     }
0074 }
0075
0076 template < typename VertexListGraph, typename DistanceMatrix,
0077     typename BinaryPredicate, typename BinaryFunction, typename Infinity,
0078     typename Zero >
0079 bool floyd_warshall_initialized_all_pairs_shortest_paths(
0080     const VertexListGraph& g, DistanceMatrix& d, const BinaryPredicate& compare,
0081     const BinaryFunction& combine, const Infinity& inf, const Zero& zero)
0082 {
0083     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexListGraph >));
0084
0085     return detail::floyd_warshall_dispatch(g, d, compare, combine, inf, zero);
0086 }
0087
0088 template < typename VertexAndEdgeListGraph, typename DistanceMatrix,
0089     typename WeightMap, typename BinaryPredicate, typename BinaryFunction,
0090     typename Infinity, typename Zero >
0091 bool floyd_warshall_all_pairs_shortest_paths(const VertexAndEdgeListGraph& g,
0092     DistanceMatrix& d, const WeightMap& w, const BinaryPredicate& compare,
0093     const BinaryFunction& combine, const Infinity& inf, const Zero& zero)
0094 {
0095     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexAndEdgeListGraph >));
0096     BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< VertexAndEdgeListGraph >));
0097     BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< VertexAndEdgeListGraph >));
0098
0099     typename graph_traits< VertexAndEdgeListGraph >::vertex_iterator firstv,
0100         lastv, firstv2, lastv2;
0101     typename graph_traits< VertexAndEdgeListGraph >::edge_iterator first, last;
0102
0103     for (boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
0104         for (boost::tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2;
0105              firstv2++)
0106             d[*firstv][*firstv2] = inf;
0107
0108     for (boost::tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
0109         d[*firstv][*firstv] = zero;
0110
0111     for (boost::tie(first, last) = edges(g); first != last; first++)
0112     {
0113         if (d[source(*first, g)][target(*first, g)] != inf)
0114         {
0115             d[source(*first, g)][target(*first, g)]
0116                 = detail::min_with_compare(get(w, *first),
0117                     d[source(*first, g)][target(*first, g)], compare);
0118         }
0119         else
0120             d[source(*first, g)][target(*first, g)] = get(w, *first);
0121     }
0122
0123     bool is_undirected = is_same<
0124         typename graph_traits< VertexAndEdgeListGraph >::directed_category,
0125         undirected_tag >::value;
0126     if (is_undirected)
0127     {
0128         for (boost::tie(first, last) = edges(g); first != last; first++)
0129         {
0130             if (d[target(*first, g)][source(*first, g)] != inf)
0131                 d[target(*first, g)][source(*first, g)]
0132                     = detail::min_with_compare(get(w, *first),
0133                         d[target(*first, g)][source(*first, g)], compare);
0134             else
0135                 d[target(*first, g)][source(*first, g)] = get(w, *first);
0136         }
0137     }
0138
0139     return detail::floyd_warshall_dispatch(g, d, compare, combine, inf, zero);
0140 }
0141
0142 namespace detail
0143 {
0144     template < class VertexListGraph, class DistanceMatrix, class WeightMap,
0145         class P, class T, class R >
0146     bool floyd_warshall_init_dispatch(const VertexListGraph& g,
0147         DistanceMatrix& d, WeightMap /*w*/,
0148         const bgl_named_params< P, T, R >& params)
0149     {
0150         typedef typename property_traits< WeightMap >::value_type WM;
0151         WM inf = choose_param(get_param(params, distance_inf_t()),
0152             std::numeric_limits< WM >::max BOOST_PREVENT_MACRO_SUBSTITUTION());
0153
0154         return floyd_warshall_initialized_all_pairs_shortest_paths(g, d,
0155             choose_param(
0156                 get_param(params, distance_compare_t()), std::less< WM >()),
0157             choose_param(get_param(params, distance_combine_t()),
0158                 closed_plus< WM >(inf)),
0159             inf, choose_param(get_param(params, distance_zero_t()), WM()));
0160     }
0161
0162     template < class VertexAndEdgeListGraph, class DistanceMatrix,
0163         class WeightMap, class P, class T, class R >
0164     bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g,
0165         DistanceMatrix& d, WeightMap w,
0166         const bgl_named_params< P, T, R >& params)
0167     {
0168         typedef typename property_traits< WeightMap >::value_type WM;
0169
0170         WM inf = choose_param(get_param(params, distance_inf_t()),
0171             std::numeric_limits< WM >::max BOOST_PREVENT_MACRO_SUBSTITUTION());
0172         return floyd_warshall_all_pairs_shortest_paths(g, d, w,
0173             choose_param(
0174                 get_param(params, distance_compare_t()), std::less< WM >()),
0175             choose_param(get_param(params, distance_combine_t()),
0176                 closed_plus< WM >(inf)),
0177             inf, choose_param(get_param(params, distance_zero_t()), WM()));
0178     }
0179
0180 } // namespace detail
0181
0182 template < class VertexListGraph, class DistanceMatrix, class P, class T,
0183     class R >
0184 bool floyd_warshall_initialized_all_pairs_shortest_paths(
0185     const VertexListGraph& g, DistanceMatrix& d,
0186     const bgl_named_params< P, T, R >& params)
0187 {
0188     return detail::floyd_warshall_init_dispatch(g, d,
0189         choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
0190         params);
0191 }
0192
0193 template < class VertexListGraph, class DistanceMatrix >
0194 bool floyd_warshall_initialized_all_pairs_shortest_paths(
0195     const VertexListGraph& g, DistanceMatrix& d)
0196 {
0197     bgl_named_params< int, int > params(0);
0198     return detail::floyd_warshall_init_dispatch(
0199         g, d, get(edge_weight, g), params);
0200 }
0201
0202 template < class VertexAndEdgeListGraph, class DistanceMatrix, class P, class T,
0203     class R >
0204 bool floyd_warshall_all_pairs_shortest_paths(const VertexAndEdgeListGraph& g,
0205     DistanceMatrix& d, const bgl_named_params< P, T, R >& params)
0206 {
0207     return detail::floyd_warshall_noninit_dispatch(g, d,
0208         choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
0209         params);
0210 }
0211
0212 template < class VertexAndEdgeListGraph, class DistanceMatrix >
0213 bool floyd_warshall_all_pairs_shortest_paths(
0214     const VertexAndEdgeListGraph& g, DistanceMatrix& d)
0215 {
0216     bgl_named_params< int, int > params(0);
0217     return detail::floyd_warshall_noninit_dispatch(
0218         g, d, get(edge_weight, g), params);
0219 }
0220
0221 } // namespace boost
0222
0223 #endif