# source:lemon-0.x/src/work/alpar/dijkstra/dijkstra.h@224:5bc1c83257f8

Last change on this file since 224:5bc1c83257f8 was 224:5bc1c83257f8, checked in by Alpar Juttner, 20 years ago

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