source: NonGTP/Boost/boost/graph/floyd_warshall_shortest.hpp @ 857

Revision 857, 8.2 KB checked in by igarcia, 19 years ago (diff)
Line 
1// Copyright 2002 Rensselaer Polytechnic Institute
2
3// Use, modification and distribution is subject to the Boost Software
4// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7//  Authors: Lauren Foutz
8//           Scott Hill
9
10/*
11  This file implements the functions
12
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)
18
19  AND
20
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*/
27
28
29#ifndef BOOST_GRAPH_FLOYD_WARSHALL_HPP
30#define BOOST_GRAPH_FLOYD_WARSHALL_HPP
31
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>
37#include <algorithm> // for std::min and std::max
38
39namespace boost
40{
41  namespace detail {
42    template<typename VertexListGraph, typename DistanceMatrix,
43      typename BinaryPredicate, typename BinaryFunction,
44      typename Infinity, typename Zero>
45    bool floyd_warshall_dispatch(const VertexListGraph& g,
46      DistanceMatrix& d, const BinaryPredicate &compare,
47      const BinaryFunction &combine, const Infinity& inf,
48      const Zero& zero)
49    {
50      BOOST_USING_STD_MIN();
51
52      typename graph_traits<VertexListGraph>::vertex_iterator
53        i, lasti, j, lastj, k, lastk;
54   
55     
56      for (tie(k, lastk) = vertices(g); k != lastk; k++)
57        for (tie(i, lasti) = vertices(g); i != lasti; i++)
58          for (tie(j, lastj) = vertices(g); j != lastj; j++)
59          {
60            d[*i][*j] = min BOOST_PREVENT_MACRO_SUBSTITUTION
61                         (d[*i][*j], combine(d[*i][*k], d[*k][*j]));
62          }
63     
64   
65      for (tie(i, lasti) = vertices(g); i != lasti; i++)
66        if (compare(d[*i][*i], zero))
67          return false;
68      return true;
69    }
70  }
71
72  template <typename VertexListGraph, typename DistanceMatrix,
73    typename BinaryPredicate, typename BinaryFunction,
74    typename Infinity, typename Zero>
75  bool floyd_warshall_initialized_all_pairs_shortest_paths(
76    const VertexListGraph& g, DistanceMatrix& d,
77    const BinaryPredicate& compare,
78    const BinaryFunction& combine, const Infinity& inf,
79    const Zero& zero)
80  {
81    function_requires<VertexListGraphConcept<VertexListGraph> >();
82 
83    return detail::floyd_warshall_dispatch(g, d, compare, combine,
84    inf, zero);
85  }
86 
87
88 
89  template <typename VertexAndEdgeListGraph, typename DistanceMatrix,
90    typename WeightMap, typename BinaryPredicate,
91    typename BinaryFunction, typename Infinity, typename Zero>
92  bool floyd_warshall_all_pairs_shortest_paths(
93    const VertexAndEdgeListGraph& g,
94    DistanceMatrix& d, const WeightMap& w,
95    const BinaryPredicate& compare, const BinaryFunction& combine,
96    const Infinity& inf, const Zero& zero)
97  {
98    BOOST_USING_STD_MIN();
99
100    function_requires<VertexListGraphConcept<VertexAndEdgeListGraph> >();
101    function_requires<EdgeListGraphConcept<VertexAndEdgeListGraph> >();
102    function_requires<IncidenceGraphConcept<VertexAndEdgeListGraph> >();
103 
104    typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator
105      firstv, lastv, firstv2, lastv2;
106    typename graph_traits<VertexAndEdgeListGraph>::edge_iterator first, last;
107 
108   
109    for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
110      for(tie(firstv2, lastv2) = vertices(g); firstv2 != lastv2; firstv2++)
111        d[*firstv][*firstv2] = inf;
112   
113   
114    for(tie(firstv, lastv) = vertices(g); firstv != lastv; firstv++)
115      d[*firstv][*firstv] = 0;
116   
117   
118    for(tie(first, last) = edges(g); first != last; first++)
119    {
120      if (d[source(*first, g)][target(*first, g)] != inf)
121        d[source(*first, g)][target(*first, g)] =
122          min BOOST_PREVENT_MACRO_SUBSTITUTION(get(w, *first),
123            d[source(*first, g)][target(*first, g)]);
124      else
125        d[source(*first, g)][target(*first, g)] = get(w, *first);
126    }
127   
128    bool is_undirected = is_same<typename
129      graph_traits<VertexAndEdgeListGraph>::directed_category,
130      undirected_tag>::value;
131    if (is_undirected)
132    {
133      for(tie(first, last) = edges(g); first != last; first++)
134      {
135        if (d[target(*first, g)][source(*first, g)] != inf)
136          d[target(*first, g)][source(*first, g)] =
137            min BOOST_PREVENT_MACRO_SUBSTITUTION(get(w, *first),
138            d[target(*first, g)][source(*first, g)]);
139        else
140          d[target(*first, g)][source(*first, g)] = get(w, *first);
141      }
142    }
143   
144 
145    return detail::floyd_warshall_dispatch(g, d, compare, combine,
146      inf, zero);
147  }
148 
149
150  namespace detail {       
151    template <class VertexListGraph, class DistanceMatrix,
152      class WeightMap, class P, class T, class R>
153    bool floyd_warshall_init_dispatch(const VertexListGraph& g,
154      DistanceMatrix& d, WeightMap w,
155      const bgl_named_params<P, T, R>& params)
156    {
157      typedef typename property_traits<WeightMap>::value_type WM;
158   
159      return floyd_warshall_initialized_all_pairs_shortest_paths(g, d,
160        choose_param(get_param(params, distance_compare_t()),
161          std::less<WM>()),
162        choose_param(get_param(params, distance_combine_t()),
163          closed_plus<WM>()),
164        choose_param(get_param(params, distance_inf_t()),
165          std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
166        choose_param(get_param(params, distance_zero_t()),
167          WM()));
168    }
169   
170
171   
172    template <class VertexAndEdgeListGraph, class DistanceMatrix,
173      class WeightMap, class P, class T, class R>
174    bool floyd_warshall_noninit_dispatch(const VertexAndEdgeListGraph& g,
175      DistanceMatrix& d, WeightMap w,
176      const bgl_named_params<P, T, R>& params)
177    {
178      typedef typename property_traits<WeightMap>::value_type WM;
179   
180      return floyd_warshall_all_pairs_shortest_paths(g, d, w,
181        choose_param(get_param(params, distance_compare_t()),
182          std::less<WM>()),
183        choose_param(get_param(params, distance_combine_t()),
184          closed_plus<WM>()),
185        choose_param(get_param(params, distance_inf_t()),
186          std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
187        choose_param(get_param(params, distance_zero_t()),
188          WM()));
189    }
190   
191
192  }   // namespace detail
193
194 
195 
196  template <class VertexListGraph, class DistanceMatrix, class P,
197    class T, class R>
198  bool floyd_warshall_initialized_all_pairs_shortest_paths(
199    const VertexListGraph& g, DistanceMatrix& d,
200    const bgl_named_params<P, T, R>& params)
201  {
202    return detail::floyd_warshall_init_dispatch(g, d,
203      choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
204      params);
205  }
206 
207  template <class VertexListGraph, class DistanceMatrix>
208  bool floyd_warshall_initialized_all_pairs_shortest_paths(
209    const VertexListGraph& g, DistanceMatrix& d)
210  {
211    bgl_named_params<int,int> params(0);
212    return detail::floyd_warshall_init_dispatch(g, d,
213      get(edge_weight, g), params);
214  }
215 
216
217 
218 
219  template <class VertexAndEdgeListGraph, class DistanceMatrix,
220    class P, class T, class R>
221  bool floyd_warshall_all_pairs_shortest_paths(
222    const VertexAndEdgeListGraph& g, DistanceMatrix& d,
223    const bgl_named_params<P, T, R>& params)
224  {
225    return detail::floyd_warshall_noninit_dispatch(g, d,
226      choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
227      params);
228  }
229 
230  template <class VertexAndEdgeListGraph, class DistanceMatrix>
231  bool floyd_warshall_all_pairs_shortest_paths(
232    const VertexAndEdgeListGraph& g, DistanceMatrix& d)
233  {
234    bgl_named_params<int,int> params(0);
235    return detail::floyd_warshall_noninit_dispatch(g, d,
236      get(edge_weight, g), params);
237  }
238 
239
240} // namespace boost
241
242#endif
243
Note: See TracBrowser for help on using the repository browser.