test: epoc32/include/stdapis/boost/graph/floyd_warshall

     1 // Copyright 2002 Rensselaer Polytechnic Institute

     3 // Distributed under the Boost Software License, Version 1.0.

     4 // (See accompanying file LICENSE_1_0.txt or copy at

     5 // http://www.boost.org/LICENSE_1_0.txt)

     7 //  Authors: Lauren Foutz

     8 //           Scott Hill

    10 /*

    11   This file implements the functions

    13   template <class VertexListGraph, class DistanceMatrix,

    14     class P, class T, class R>

    15   bool floyd_warshall_initialized_all_pairs_shortest_paths(

    16     const VertexListGraph& g, DistanceMatrix& d,

    17     const bgl_named_params<P, T, R>& params)

    19   AND

    21   template <class VertexAndEdgeListGraph, class DistanceMatrix,

    22     class P, class T, class R>

    23   bool floyd_warshall_all_pairs_shortest_paths(

    24     const VertexAndEdgeListGraph& g, DistanceMatrix& d,

    25     const bgl_named_params<P, T, R>& params)

    26 */

    29 #ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP

    30 #define BOOST_GRAPH_FLOYD_WARSHALL_HPP

    32 #include <boost/property_map.hpp>

    33 #include <boost/graph/graph_traits.hpp>

    34 #include <boost/graph/named_function_params.hpp>

    35 #include <boost/graph/graph_concepts.hpp>

    36 #include <boost/graph/relax.hpp>

    38 namespace boost

    39 {

    40   namespace detail {

    41     template<typename T, typename BinaryPredicate>

    42     T min_with_compare(const T& x, const T& y, const BinaryPredicate& compare)

    43     {

    44       if (compare(x, y)) return x;

    45       else return y;

    46     }

    48     template<typename VertexListGraph, typename DistanceMatrix,

    49       typename BinaryPredicate, typename BinaryFunction,

    50       typename Infinity, typename Zero>

    51     bool floyd_warshall_dispatch(const VertexListGraph& g,

    52       DistanceMatrix& d, const BinaryPredicate &compare,

    53       const BinaryFunction &combine, const Infinity& inf,

    54       const Zero& zero)

    55     {

    56       typename graph_traits<VertexListGraph>::vertex_iterator

    57         i, lasti, j, lastj, k, lastk;

    60       for (tie(k, lastk) = vertices(g); k != lastk; k++)

    61         for (tie(i, lasti) = vertices(g); i != lasti; i++)

    62           for (tie(j, lastj) = vertices(g); j != lastj; j++)

    63           {

    64             d[*i][*j] =

    65               detail::min_with_compare(d[*i][*j],

    66                                        combine(d[*i][*k], d[*k][*j]),

    67                                        compare);

    68           }

    71       for (tie(i, lasti) = vertices(g); i != lasti; i++)

    72         if (compare(d[*i][*i], zero))

    73           return false;

    74       return true;

    75     }

    76   }

    78   template <typename VertexListGraph, typename DistanceMatrix,

    79     typename BinaryPredicate, typename BinaryFunction,

    80     typename Infinity, typename Zero>

    81   bool floyd_warshall_initialized_all_pairs_shortest_paths(

    82     const VertexListGraph& g, DistanceMatrix& d,

    83     const BinaryPredicate& compare,

    84     const BinaryFunction& combine, const Infinity& inf,

    85     const Zero& zero)

    86   {

    87     function_requires<VertexListGraphConcept<VertexListGraph> >();

    89     return detail::floyd_warshall_dispatch(g, d, compare, combine,

    90     inf, zero);

    91   }

    95   template <typename VertexAndEdgeListGraph, typename DistanceMatrix,

    96     typename WeightMap, typename BinaryPredicate,

    97     typename BinaryFunction, typename Infinity, typename Zero>

    98   bool floyd_warshall_all_pairs_shortest_paths(

    99     const VertexAndEdgeListGraph& g,

   100     DistanceMatrix& d, const WeightMap& w,

   101     const BinaryPredicate& compare, const BinaryFunction& combine,

   102     const Infinity& inf, const Zero& zero)

   103   {

   104     function_requires<VertexListGraphConcept<VertexAndEdgeListGraph> >();

   105     function_requires<EdgeListGraphConcept<VertexAndEdgeListGraph> >();

   106     function_requires<IncidenceGraphConcept<VertexAndEdgeListGraph> >();

   108     typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator

   109       firstv, lastv, firstv2, lastv2;

   110     typename graph_traits<VertexAndEdgeListGraph>::edge_iterator first, last;

   113     for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)

   114       for(tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++)

   115         d[*firstv][*firstv2] = inf;

   118     for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)

   119       d[*firstv][*firstv] = zero;

   122     for(tie(first, last) = edges(g); first != last; first++)

   123     {

   124       if (d[source(*first, g)][target(*first, g)] != inf) {

   125         d[source(*first, g)][target(*first, g)] =

   126           detail::min_with_compare(

   127             get(w, *first),

   128             d[source(*first, g)][target(*first, g)],

   129             compare);

   130       } else

   131         d[source(*first, g)][target(*first, g)] = get(w, *first);

   132     }

   134     bool is_undirected = is_same<typename

   135       graph_traits<VertexAndEdgeListGraph>::directed_category,

   136       undirected_tag>::value;

   137     if (is_undirected)

   138     {

   139       for(tie(first, last) = edges(g); first != last; first++)

   140       {

   141         if (d[target(*first, g)][source(*first, g)] != inf)

   142           d[target(*first, g)][source(*first, g)] =

   143             detail::min_with_compare(

   144               get(w, *first),

   145               d[target(*first, g)][source(*first, g)],

   146               compare);

   147         else

   148           d[target(*first, g)][source(*first, g)] = get(w, *first);

   149       }

   150     }

   153     return detail::floyd_warshall_dispatch(g, d, compare, combine,

   154       inf, zero);

   155   }

   158   namespace detail {

   159     template <class VertexListGraph, class DistanceMatrix,

   160       class WeightMap, class P, class T, class R>

   161     bool floyd_warshall_init_dispatch(const VertexListGraph& g,

   162       DistanceMatrix& d, WeightMap w,

   163       const bgl_named_params<P, T, R>& params)

   164     {

   165       typedef typename property_traits<WeightMap>::value_type WM;

   167       return floyd_warshall_initialized_all_pairs_shortest_paths(g, d,

   168         choose_param(get_param(params, distance_compare_t()),

   169           std::less<WM>()),

   170         choose_param(get_param(params, distance_combine_t()),

   171           closed_plus<WM>()),

   172         choose_param(get_param(params, distance_inf_t()),

   173           std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),

   174         choose_param(get_param(params, distance_zero_t()),

   175           WM()));

   176     }

   180     template <class VertexAndEdgeListGraph, class DistanceMatrix,

   181       class WeightMap, class P, class T, class R>

   182     bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g,

   183       DistanceMatrix& d, WeightMap w,

   184       const bgl_named_params<P, T, R>& params)

   185     {

   186       typedef typename property_traits<WeightMap>::value_type WM;

   188       return floyd_warshall_all_pairs_shortest_paths(g, d, w,

   189         choose_param(get_param(params, distance_compare_t()),

   190           std::less<WM>()),

   191         choose_param(get_param(params, distance_combine_t()),

   192           closed_plus<WM>()),

   193         choose_param(get_param(params, distance_inf_t()),

   194           std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),

   195         choose_param(get_param(params, distance_zero_t()),

   196           WM()));

   197     }

   200   }   // namespace detail

   204   template <class VertexListGraph, class DistanceMatrix, class P,

   205     class T, class R>

   206   bool floyd_warshall_initialized_all_pairs_shortest_paths(

   207     const VertexListGraph& g, DistanceMatrix& d,

   208     const bgl_named_params<P, T, R>& params)

   209   {

   210     return detail::floyd_warshall_init_dispatch(g, d,

   211       choose_const_pmap(get_param(params, edge_weight), g, edge_weight),

   212       params);

   213   }

   215   template <class VertexListGraph, class DistanceMatrix>

   216   bool floyd_warshall_initialized_all_pairs_shortest_paths(

   217     const VertexListGraph& g, DistanceMatrix& d)

   218   {

   219     bgl_named_params<int,int> params(0);

   220     return detail::floyd_warshall_init_dispatch(g, d,

   221       get(edge_weight, g), params);

   222   }

   227   template <class VertexAndEdgeListGraph, class DistanceMatrix,

   228     class P, class T, class R>

   229   bool floyd_warshall_all_pairs_shortest_paths(

   230     const VertexAndEdgeListGraph& g, DistanceMatrix& d,

   231     const bgl_named_params<P, T, R>& params)

   232   {

   233     return detail::floyd_warshall_noninit_dispatch(g, d,

   234       choose_const_pmap(get_param(params, edge_weight), g, edge_weight),

   235       params);

   236   }

   238   template <class VertexAndEdgeListGraph, class DistanceMatrix>

   239   bool floyd_warshall_all_pairs_shortest_paths(

   240     const VertexAndEdgeListGraph& g, DistanceMatrix& d)

   241   {

   242     bgl_named_params<int,int> params(0);

   243     return detail::floyd_warshall_noninit_dispatch(g, d,

   244       get(edge_weight, g), params);

   245   }

   248 } // namespace boost

   250 #endif

author	William Roberts <williamr@symbian.org>
	Wed, 31 Mar 2010 12:33:34 +0100
branch	Symbian3
changeset 4	837f303aceeb
permissions	-rw-r--r--