1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/dijkstra.h Thu May 06 13:21:24 2004 +0000
1.3 @@ -0,0 +1,208 @@
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 +