# source:lemon-0.x/src/include/dijkstra.h@297:8b6ba518fc21

Last change on this file since 297:8b6ba518fc21 was 296:09d6d48815a5, checked in by Alpar Juttner, 18 years ago

File size: 6.4 KB
Line
1// -*- C++ -*-
2
3/*
4 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
5 *
6 *Constructor:
7 *
8 *Dijkstra(Graph G, LengthMap length)
9 *
10 *
11 *Methods:
12 *
13 *void run(Node s)
14 *
15 *T dist(Node v) : After run(s) was run, it returns the distance from s to v.
16 *   Returns T() if v is not reachable from s.
17 *
18 *Edge pred(Node v) : After run(s) was run, it returns the last
19 *   edge of a shortest s-v path. It is INVALID for s and for
20 *   the nodes not reachable from s.
21 *
22 *bool reached(Node v) : After run(s) was run, it is true iff v is
23 *   reachable from s
24 *
25 */
26
27#ifndef HUGO_DIJKSTRA_H
28#define HUGO_DIJKSTRA_H
29
30///\file
31///\brief Dijkstra algorithm.
32
33#include <fib_heap.h>
34#include <bin_heap.h>
35#include <invalid.h>
36
37namespace hugo {
38
39  //Alpar: Changed the order of the parameters
40
41  ///%Dijkstra algorithm class.
42
43  ///This class provides an efficient implementation of %Dijkstra algorithm.
44  ///The edge lengths are passed to the algorithm using a
46  ///so it is easy to change it to any kind of length.
47  ///
48  ///The type of the length is determined by the \c ValueType of the length map.
49  ///
50  ///It is also possible to change the underlying priority heap.
51  ///
52  ///\param Graph The graph type the algorithm runs on.
54  ///EdgeMap
55  ///determines the
56  ///lengths of the edges. It is read once for each edge, so the map
57  ///may involve in relatively time consuming process to compute the edge
58  ///length if it is necessary. The default map type is
59  ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
60  ///\param Heap The heap type used by the %Dijkstra
61  ///algorithm. The default
62  ///is using \ref BinHeap "binary heap".
63
64#ifdef DOXYGEN
65  template <typename Graph,
66            typename LengthMap,
67            typename Heap>
68#else
69  template <typename Graph,
70            typename LengthMap=typename Graph::EdgeMap<int>,
71            template <class,class,class> class Heap = BinHeap >
72#endif
73  class Dijkstra{
74  public:
75    typedef typename Graph::Node Node;
76    typedef typename Graph::NodeIt NodeIt;
77    typedef typename Graph::Edge Edge;
78    typedef typename Graph::OutEdgeIt OutEdgeIt;
79
80    typedef typename LengthMap::ValueType ValueType;
81    typedef typename Graph::NodeMap<Edge> PredMap;
82    typedef typename Graph::NodeMap<Node> PredNodeMap;
83    typedef typename Graph::NodeMap<ValueType> DistMap;
84
85  private:
86    const Graph& G;
87    const LengthMap& length;
88    PredMap predecessor;
89    PredNodeMap pred_node;
90    DistMap distance;
91
92  public :
93
94    Dijkstra(Graph& _G, LengthMap& _length) :
95      G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
96
97    void run(Node s);
98
99    ///The distance of a node from the source.
100
101    ///Returns the distance of a node from the source.
102    ///\pre \ref run() must be called before using this function.
103    ///\warning If node \c v in unreachable from the source the return value
104    ///of this funcion is undefined.
105    ValueType dist(Node v) const { return distance[v]; }
106    ///Returns the edges of the shortest path tree.
107
108    ///For a node \c v it returns the last edge of the shortest path
109    ///from the source to \c v or INVALID if \c v is unreachable
110    ///from the source.
111    ///\pre \ref run() must be called before using this function.
112    Edge pred(Node v) const { return predecessor[v]; }
113    ///Returns the nodes of the shortest paths.
114
115    ///For a node \c v it returns the last but one node of the shortest path
116    ///from the source to \c v or INVALID if \c v is unreachable
117    ///from the source.
118    ///\pre \ref run() must be called before using this function.
119    Node predNode(Node v) const { return pred_node[v]; }
120
121    ///Returns a reference to the NodeMap of distances.
122
123    ///\pre \ref run() must be called before using this function.
124    ///
125    const DistMap &distMap() const { return distance;}
126    ///Returns a reference to the shortest path tree map.
127
128    ///Returns a reference to the NodeMap of the edges of the
129    ///shortest path tree.
130    ///\pre \ref run() must be called before using this function.
131    const PredMap &predMap() const { return predecessor;}
132    ///Returns a reference to the map of nodes of  shortest paths.
133
134    ///Returns a reference to the NodeMap of the last but one nodes of the
135    ///shortest paths.
136    ///\pre \ref run() must be called before using this function.
137    const PredNodeMap &predNodeMap() const { return pred_node;}
138
139    ///Checks if a node is reachable from the source.
140
141    ///Returns \c true if \c v is reachable from the source.
142    ///\warning the source node is reported to be unreached!
143    ///\todo Is this what we want?
144    ///\pre \ref run() must be called before using this function.
145    ///
146    bool reached(Node v) { return G.valid(predecessor[v]); }
147
148  };
149
150
151  // **********************************************************************
152  //  IMPLEMENTATIONS
153  // **********************************************************************
154
155  ///Runs %Dijkstra algorithm from node the source.
156
157  ///This method runs the %Dijkstra algorithm from a source node \c s
158  ///in order to
159  ///compute the
160  ///shortest path to each node. The algorithm computes
161  ///- The shortest path tree.
162  ///- The distance of each node from the source.
163  template <typename Graph, typename LengthMap,
164            template<class,class,class> class Heap >
165  void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
166
167    NodeIt u;
168    for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
169      predecessor.set(u,INVALID);
170      pred_node.set(u,INVALID);
171      // If a node is unreacheable, then why should be the dist=0?
172      // distance.set(u,0);
173      //      reach.set(u,false);
174    }
175
176    typename Graph::NodeMap<int> heap_map(G,-1);
177
178    Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
179
180    heap.push(s,0);
181
182      while ( !heap.empty() ) {
183
184        Node v=heap.top();
185        ValueType oldvalue=heap[v];
186        heap.pop();
187        distance.set(v, oldvalue);
188
189        for(OutEdgeIt e = G.template first<OutEdgeIt>(v);
190            G.valid(e); G.next(e)) {
192
193          switch(heap.state(w)) {
194          case heap.PRE_HEAP:
195            heap.push(w,oldvalue+length[e]);
196            predecessor.set(w,e);
197            pred_node.set(w,v);
198            break;
199          case heap.IN_HEAP:
200            if ( oldvalue+length[e] < heap[w] ) {
201              heap.decrease(w, oldvalue+length[e]);
202              predecessor.set(w,e);
203              pred_node.set(w,v);
204            }
205            break;
206          case heap.POST_HEAP:
207            break;
208          }
209        }
210      }
211  }
212
213} //END OF NAMESPACE HUGO
214
215#endif
216
217
Note: See TracBrowser for help on using the repository browser.