1.1 --- a/src/include/dijkstra.h Thu May 06 09:26:23 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,208 +0,0 @@
1.4 -// -*- C++ -*-
1.5 -#ifndef HUGO_DIJKSTRA_H
1.6 -#define HUGO_DIJKSTRA_H
1.7 -
1.8 -///\ingroup galgs
1.9 -///\file
1.10 -///\brief Dijkstra algorithm.
1.11 -
1.12 -#include <bin_heap.h>
1.13 -#include <invalid.h>
1.14 -
1.15 -namespace hugo {
1.16 -
1.17 -/// \addtogroup galgs
1.18 -/// @{
1.19 -
1.20 - ///%Dijkstra algorithm class.
1.21 -
1.22 - ///This class provides an efficient implementation of %Dijkstra algorithm.
1.23 - ///The edge lengths are passed to the algorithm using a
1.24 - ///\ref ReadMapSkeleton "readable map",
1.25 - ///so it is easy to change it to any kind of length.
1.26 - ///
1.27 - ///The type of the length is determined by the \c ValueType of the length map.
1.28 - ///
1.29 - ///It is also possible to change the underlying priority heap.
1.30 - ///
1.31 - ///\param Graph The graph type the algorithm runs on.
1.32 - ///\param LengthMap This read-only
1.33 - ///EdgeMap
1.34 - ///determines the
1.35 - ///lengths of the edges. It is read once for each edge, so the map
1.36 - ///may involve in relatively time consuming process to compute the edge
1.37 - ///length if it is necessary. The default map type is
1.38 - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
1.39 - ///\param Heap The heap type used by the %Dijkstra
1.40 - ///algorithm. The default
1.41 - ///is using \ref BinHeap "binary heap".
1.42 - ///
1.43 - ///\author Jacint Szabo
1.44 -#ifdef DOXYGEN
1.45 - template <typename Graph,
1.46 - typename LengthMap,
1.47 - typename Heap>
1.48 -#else
1.49 - template <typename Graph,
1.50 - typename LengthMap=typename Graph::template EdgeMap<int>,
1.51 - template <class,class,class,class> class Heap = BinHeap >
1.52 -#endif
1.53 - class Dijkstra{
1.54 - public:
1.55 - typedef typename Graph::Node Node;
1.56 - typedef typename Graph::NodeIt NodeIt;
1.57 - typedef typename Graph::Edge Edge;
1.58 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.59 -
1.60 - typedef typename LengthMap::ValueType ValueType;
1.61 - typedef typename Graph::template NodeMap<Edge> PredMap;
1.62 - typedef typename Graph::template NodeMap<Node> PredNodeMap;
1.63 - typedef typename Graph::template NodeMap<ValueType> DistMap;
1.64 -
1.65 - private:
1.66 - const Graph& G;
1.67 - const LengthMap& length;
1.68 - PredMap predecessor;
1.69 - PredNodeMap pred_node;
1.70 - DistMap distance;
1.71 -
1.72 - public :
1.73 -
1.74 - Dijkstra(const Graph& _G, const LengthMap& _length) :
1.75 - G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
1.76 -
1.77 - void run(Node s);
1.78 -
1.79 - ///The distance of a node from the root.
1.80 -
1.81 - ///Returns the distance of a node from the root.
1.82 - ///\pre \ref run() must be called before using this function.
1.83 - ///\warning If node \c v in unreachable from the root the return value
1.84 - ///of this funcion is undefined.
1.85 - ValueType dist(Node v) const { return distance[v]; }
1.86 -
1.87 - ///Returns the previous edge of the shortest path tree.
1.88 -
1.89 - ///For a node \c v it returns the previous edge of the shortest path tree,
1.90 - ///i.e. it returns the last edge from a shortest path from the root to \c
1.91 - ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
1.92 - ///shortest path tree used here is equal to the shortest path tree used in
1.93 - ///\ref predNode(Node v). \pre \ref run() must be called before using
1.94 - ///this function.
1.95 - Edge pred(Node v) const { return predecessor[v]; }
1.96 -
1.97 - ///Returns the previous node of the shortest path tree.
1.98 -
1.99 - ///For a node \c v it returns the previous node of the shortest path tree,
1.100 - ///i.e. it returns the last but one node from a shortest path from the
1.101 - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
1.102 - ///\c v=s. The shortest path tree used here is equal to the shortest path
1.103 - ///tree used in \ref pred(Node v). \pre \ref run() must be called before
1.104 - ///using this function.
1.105 - Node predNode(Node v) const { return pred_node[v]; }
1.106 -
1.107 - ///Returns a reference to the NodeMap of distances.
1.108 -
1.109 - ///Returns a reference to the NodeMap of distances. \pre \ref run() must
1.110 - ///be called before using this function.
1.111 - const DistMap &distMap() const { return distance;}
1.112 -
1.113 - ///Returns a reference to the shortest path tree map.
1.114 -
1.115 - ///Returns a reference to the NodeMap of the edges of the
1.116 - ///shortest path tree.
1.117 - ///\pre \ref run() must be called before using this function.
1.118 - const PredMap &predMap() const { return predecessor;}
1.119 -
1.120 - ///Returns a reference to the map of nodes of shortest paths.
1.121 -
1.122 - ///Returns a reference to the NodeMap of the last but one nodes of the
1.123 - ///shortest path tree.
1.124 - ///\pre \ref run() must be called before using this function.
1.125 - const PredNodeMap &predNodeMap() const { return pred_node;}
1.126 -
1.127 - ///Checks if a node is reachable from the root.
1.128 -
1.129 - ///Returns \c true if \c v is reachable from the root.
1.130 - ///\warning the root node is reported to be unreached!
1.131 - ///\todo Is this what we want?
1.132 - ///\pre \ref run() must be called before using this function.
1.133 - ///
1.134 - bool reached(Node v) { return G.valid(predecessor[v]); }
1.135 -
1.136 - };
1.137 -
1.138 -
1.139 - // **********************************************************************
1.140 - // IMPLEMENTATIONS
1.141 - // **********************************************************************
1.142 -
1.143 - ///Runs %Dijkstra algorithm from node the root.
1.144 -
1.145 - ///This method runs the %Dijkstra algorithm from a root node \c s
1.146 - ///in order to
1.147 - ///compute the
1.148 - ///shortest path to each node. The algorithm computes
1.149 - ///- The shortest path tree.
1.150 - ///- The distance of each node from the root.
1.151 - template <typename Graph, typename LengthMap,
1.152 - template<class,class,class,class> class Heap >
1.153 - void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
1.154 -
1.155 - NodeIt u;
1.156 - for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
1.157 - predecessor.set(u,INVALID);
1.158 - pred_node.set(u,INVALID);
1.159 - }
1.160 -
1.161 - typename Graph::template NodeMap<int> heap_map(G,-1);
1.162 -
1.163 - typedef Heap<Node, ValueType, typename Graph::template NodeMap<int>,
1.164 - std::less<ValueType> >
1.165 - HeapType;
1.166 -
1.167 - HeapType heap(heap_map);
1.168 -
1.169 - heap.push(s,0);
1.170 -
1.171 - while ( !heap.empty() ) {
1.172 -
1.173 - Node v=heap.top();
1.174 - ValueType oldvalue=heap[v];
1.175 - heap.pop();
1.176 - distance.set(v, oldvalue);
1.177 -
1.178 - { //FIXME this bracket is for e to be local
1.179 - OutEdgeIt e;
1.180 - for(G.first(e, v);
1.181 - G.valid(e); G.next(e)) {
1.182 - Node w=G.bNode(e);
1.183 -
1.184 - switch(heap.state(w)) {
1.185 - case HeapType::PRE_HEAP:
1.186 - heap.push(w,oldvalue+length[e]);
1.187 - predecessor.set(w,e);
1.188 - pred_node.set(w,v);
1.189 - break;
1.190 - case HeapType::IN_HEAP:
1.191 - if ( oldvalue+length[e] < heap[w] ) {
1.192 - heap.decrease(w, oldvalue+length[e]);
1.193 - predecessor.set(w,e);
1.194 - pred_node.set(w,v);
1.195 - }
1.196 - break;
1.197 - case HeapType::POST_HEAP:
1.198 - break;
1.199 - }
1.200 - }
1.201 - } //FIXME tis bracket
1.202 - }
1.203 - }
1.204 -
1.205 -/// @}
1.206 -
1.207 -} //END OF NAMESPACE HUGO
1.208 -
1.209 -#endif
1.210 -
1.211 -