COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/dijkstra.h @ 570:eec0a62979c9

Last change on this file since 570:eec0a62979c9 was 570:eec0a62979c9, checked in by Alpar Juttner, 16 years ago

Compile checks added.

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