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

Revision 857, 8.8 KB checked in by igarcia, 18 years ago (diff)
Line 
1//
2//=======================================================================
3// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5//
6// Distributed under the Boost Software License, Version 1.0. (See
7// accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9//=======================================================================
10//
11
12/*
13  This file implements the function
14
15  template <class EdgeListGraph, class Size, class P, class T, class R>
16  bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N,
17     const bgl_named_params<P, T, R>& params)
18 
19 */
20
21
22#ifndef BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP
23#define BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP
24
25#include <boost/config.hpp>
26#include <boost/graph/graph_traits.hpp>
27#include <boost/graph/graph_concepts.hpp>
28#include <boost/graph/properties.hpp>
29#include <boost/graph/relax.hpp>
30#include <boost/graph/visitors.hpp>
31#include <boost/graph/named_function_params.hpp>
32
33namespace boost {
34
35  template <class Visitor, class Graph>
36  struct BellmanFordVisitorConcept {
37    void constraints() {
38      function_requires< CopyConstructibleConcept<Visitor> >();
39      vis.examine_edge(e, g);
40      vis.edge_relaxed(e, g);
41      vis.edge_not_relaxed(e, g);
42      vis.edge_minimized(e, g);
43      vis.edge_not_minimized(e, g);
44    }
45    Visitor vis;
46    Graph g;
47    typename graph_traits<Graph>::edge_descriptor e;
48  };
49
50  template <class Visitors = null_visitor>
51  class bellman_visitor {
52  public:
53    bellman_visitor() { }
54    bellman_visitor(Visitors vis) : m_vis(vis) { }
55
56    template <class Edge, class Graph>
57    void examine_edge(Edge u, Graph& g) {
58      invoke_visitors(m_vis, u, g, on_examine_edge());
59    }
60    template <class Edge, class Graph>
61    void edge_relaxed(Edge u, Graph& g) {
62      invoke_visitors(m_vis, u, g, on_edge_relaxed());     
63    }
64    template <class Edge, class Graph>
65    void edge_not_relaxed(Edge u, Graph& g) {
66      invoke_visitors(m_vis, u, g, on_edge_not_relaxed());
67    }
68    template <class Edge, class Graph>
69    void edge_minimized(Edge u, Graph& g) {
70      invoke_visitors(m_vis, u, g, on_edge_minimized());
71    }
72    template <class Edge, class Graph>
73    void edge_not_minimized(Edge u, Graph& g) {
74      invoke_visitors(m_vis, u, g, on_edge_not_minimized());
75    }
76  protected:
77    Visitors m_vis;
78  };
79  template <class Visitors>
80  bellman_visitor<Visitors>
81  make_bellman_visitor(Visitors vis) {
82    return bellman_visitor<Visitors>(vis);
83  }
84  typedef bellman_visitor<> default_bellman_visitor;
85
86  template <class EdgeListGraph, class Size, class WeightMap,
87            class PredecessorMap, class DistanceMap,
88            class BinaryFunction, class BinaryPredicate,
89            class BellmanFordVisitor>
90  bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N,
91                         WeightMap weight,
92                         PredecessorMap pred,
93                         DistanceMap distance,
94                         BinaryFunction combine,
95                         BinaryPredicate compare,
96                         BellmanFordVisitor v)
97  {
98    function_requires<EdgeListGraphConcept<EdgeListGraph> >();
99    typedef graph_traits<EdgeListGraph> GTraits;
100    typedef typename GTraits::edge_descriptor Edge;
101    typedef typename GTraits::vertex_descriptor Vertex;
102    function_requires<ReadWritePropertyMapConcept<DistanceMap, Vertex> >();
103    function_requires<ReadablePropertyMapConcept<WeightMap, Edge> >();
104    typedef typename property_traits<DistanceMap>::value_type D_value;
105    typedef typename property_traits<WeightMap>::value_type W_value;
106
107    typename GTraits::edge_iterator i, end;
108
109    for (Size k = 0; k < N; ++k) {
110      bool at_least_one_edge_relaxed = false;
111      for (tie(i, end) = edges(g); i != end; ++i) {
112        v.examine_edge(*i, g);
113        if (relax(*i, g, weight, pred, distance, combine, compare)) {
114          at_least_one_edge_relaxed = true;
115          v.edge_relaxed(*i, g);
116        } else
117          v.edge_not_relaxed(*i, g);
118      }
119      if (!at_least_one_edge_relaxed)
120        break;
121    }
122
123    for (tie(i, end) = edges(g); i != end; ++i)
124      if (compare(combine(get(distance, source(*i, g)), get(weight, *i)),
125                  get(distance, target(*i,g))))
126      {
127        v.edge_not_minimized(*i, g);
128        return false;
129      } else
130        v.edge_minimized(*i, g);
131
132    return true;
133  }
134
135  namespace detail {
136
137    template<typename VertexAndEdgeListGraph, typename Size,
138             typename WeightMap, typename PredecessorMap, typename DistanceMap,
139             typename P, typename T, typename R>
140    bool
141    bellman_dispatch2
142      (VertexAndEdgeListGraph& g,
143       typename graph_traits<VertexAndEdgeListGraph>::vertex_descriptor s,
144       Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance,
145       const bgl_named_params<P, T, R>& params)
146    {
147      typedef typename property_traits<DistanceMap>::value_type D;
148      bellman_visitor<> null_vis;
149      typedef typename property_traits<WeightMap>::value_type weight_type;
150      typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator v, v_end;
151      for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
152        put(distance, *v, (std::numeric_limits<weight_type>::max)());
153        put(pred, *v, *v);
154      }
155      put(distance, s, weight_type(0));
156      return bellman_ford_shortest_paths
157               (g, N, weight, pred, distance,
158                choose_param(get_param(params, distance_combine_t()),
159                             closed_plus<D>()),
160                choose_param(get_param(params, distance_compare_t()),
161                             std::less<D>()),
162                choose_param(get_param(params, graph_visitor),
163                             null_vis)
164                );
165    }
166
167    template<typename VertexAndEdgeListGraph, typename Size,
168             typename WeightMap, typename PredecessorMap, typename DistanceMap,
169             typename P, typename T, typename R>
170    bool
171    bellman_dispatch2
172      (VertexAndEdgeListGraph& g,
173       detail::error_property_not_found,
174       Size N, WeightMap weight, PredecessorMap pred, DistanceMap distance,
175       const bgl_named_params<P, T, R>& params)
176    {
177      typedef typename property_traits<DistanceMap>::value_type D;
178      bellman_visitor<> null_vis;
179      return bellman_ford_shortest_paths
180               (g, N, weight, pred, distance,
181                choose_param(get_param(params, distance_combine_t()),
182                             closed_plus<D>()),
183                choose_param(get_param(params, distance_compare_t()),
184                             std::less<D>()),
185                choose_param(get_param(params, graph_visitor),
186                             null_vis)
187                );
188    }
189
190    template <class EdgeListGraph, class Size, class WeightMap,
191              class DistanceMap, class P, class T, class R>
192    bool bellman_dispatch(EdgeListGraph& g, Size N,
193                          WeightMap weight, DistanceMap distance,
194                          const bgl_named_params<P, T, R>& params)
195    {
196      dummy_property_map dummy_pred;
197      return
198        detail::bellman_dispatch2
199          (g,
200           get_param(params, root_vertex_t()),
201           N, weight,
202           choose_param(get_param(params, vertex_predecessor), dummy_pred),
203           distance,
204           params);
205    }
206  } // namespace detail
207
208  template <class EdgeListGraph, class Size, class P, class T, class R>
209  bool bellman_ford_shortest_paths
210    (EdgeListGraph& g, Size N,
211     const bgl_named_params<P, T, R>& params)
212  {                               
213    return detail::bellman_dispatch
214      (g, N,
215       choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
216       choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
217       params);
218  }
219
220  template <class EdgeListGraph, class Size>
221  bool bellman_ford_shortest_paths(EdgeListGraph& g, Size N)
222  {                               
223    bgl_named_params<int,int> params(0);
224    return bellman_ford_shortest_paths(g, N, params);
225  }
226
227  template <class VertexAndEdgeListGraph, class P, class T, class R>
228  bool bellman_ford_shortest_paths
229    (VertexAndEdgeListGraph& g,
230     const bgl_named_params<P, T, R>& params)
231  {               
232    function_requires<VertexListGraphConcept<VertexAndEdgeListGraph> >();
233    return detail::bellman_dispatch
234      (g, num_vertices(g),
235       choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
236       choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
237       params);
238  }
239} // namespace boost
240
241#endif // BOOST_GRAPH_BELLMAN_FORD_SHORTEST_PATHS_HPP
Note: See TracBrowser for help on using the repository browser.