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