diff -r 4406c93c862b -r 8aca0af3f30b src/work/jacint/dijkstra.h --- a/src/work/jacint/dijkstra.h Fri Apr 23 19:41:01 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,220 +0,0 @@ -// -*- C++ -*- - -/* - *template > - * - *Constructor: - * - *Dijkstra(Graph G, LengthMap length) - * - * - *Methods: - * - *void run(Node s) - * - *T dist(Node v) : After run(s) was run, it returns the distance from s to v. - * Returns T() if v is not reachable from s. - * - *Edge pred(Node v) : After run(s) was run, it returns the last - * edge of a shortest s-v path. It is INVALID for s and for - * the nodes not reachable from s. - * - *bool reached(Node v) : After run(s) was run, it is true iff v is - * reachable from s - * - */ - -#ifndef HUGO_DIJKSTRA_H -#define HUGO_DIJKSTRA_H - -///\file -///\brief Dijkstra algorithm. - -#include -#include -#include - -namespace hugo { - - //Alpar: Changed the order of the parameters - - ///%Dijkstra algorithm class. - - ///This class provides an efficient implementation of %Dijkstra algorithm. - ///The edge lengths are passed to the algorithm using a - ///\ref ReadMapSkeleton "readable map", - ///so it is easy to change it to any kind of length. - /// - ///The type of the length is determined by the \c ValueType of the length map. - /// - ///It is also possible to change the underlying priority heap. - /// - ///\param Graph The graph type the algorithm runs on. - ///\param LengthMap This read-only - ///EdgeMap - ///determines the - ///lengths of the edges. It is read once for each edge, so the map - ///may involve in relatively time consuming process to compute the edge - ///length if it is necessary. The default map type is - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap" - ///\param Heap The heap type used by the %Dijkstra - ///algorithm. The default - ///is using \ref BinHeap "binary heap". - -#ifdef DOXYGEN - template -#else - template , - template class Heap = BinHeap > -#endif - class Dijkstra{ - public: - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::OutEdgeIt OutEdgeIt; - - typedef typename LengthMap::ValueType ValueType; - typedef typename Graph::NodeMap PredMap; - typedef typename Graph::NodeMap PredNodeMap; - typedef typename Graph::NodeMap DistMap; - - private: - const Graph& G; - const LengthMap& length; - PredMap predecessor; - PredNodeMap pred_node; - DistMap distance; - - public : - - Dijkstra(Graph& _G, LengthMap& _length) : - G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } - - void run(Node s); - - ///The distance of a node from the source. - - ///Returns the distance of a node from the source. - ///\pre \ref run() must be called before using this function. - ///\warning If node \c v in unreachable from the source the return value - ///of this funcion is undefined. - ValueType dist(Node v) const { return distance[v]; } - ///Returns the edges of the shortest path tree. - - ///For a node \c v it returns the last edge of the shortest path - ///from the source to \c v or INVALID if \c v is unreachable - ///from the source. - ///\pre \ref run() must be called before using this function. - Edge pred(Node v) const { return predecessor[v]; } - ///Returns the nodes of the shortest paths. - - ///For a node \c v it returns the last but one node of the shortest path - ///from the source to \c v or INVALID if \c v is unreachable - ///from the source. - ///\pre \ref run() must be called before using this function. - Node predNode(Node v) const { return pred_node[v]; } - - ///Returns a reference to the NodeMap of distances. - - ///\pre \ref run() must be called before using this function. - /// - const DistMap &distMap() const { return distance;} - ///Returns a reference to the shortest path tree map. - - ///Returns a reference to the NodeMap of the edges of the - ///shortest path tree. - ///\pre \ref run() must be called before using this function. - const PredMap &predMap() const { return predecessor;} - ///Returns a reference to the map of nodes of shortest paths. - - ///Returns a reference to the NodeMap of the last but one nodes of the - ///shortest paths. - ///\pre \ref run() must be called before using this function. - const PredNodeMap &predNodeMap() const { return pred_node;} - - ///Checks if a node is reachable from the source. - - ///Returns \c true if \c v is reachable from the source. - ///\warning the source node is reported to be unreached! - ///\todo Is this what we want? - ///\pre \ref run() must be called before using this function. - /// - bool reached(Node v) { return G.valid(predecessor[v]); } - - }; - - - // ********************************************************************** - // IMPLEMENTATIONS - // ********************************************************************** - - ///Runs %Dijkstra algorithm from node the source. - - ///This method runs the %Dijkstra algorithm from a source node \c s - ///in order to - ///compute the - ///shortest path to each node. The algorithm computes - ///- The shortest path tree. - ///- The distance of each node from the source. - template class Heap > - void Dijkstra::run(Node s) { - - NodeIt u; - for ( G.first(u) ; G.valid(u) ; G.next(u) ) { - predecessor.set(u,INVALID); - pred_node.set(u,INVALID); - // If a node is unreacheable, then why should be the dist=0? - // distance.set(u,0); - // reach.set(u,false); - } - - typename Graph::NodeMap heap_map(G,-1); - - Heap > heap(heap_map); - - heap.push(s,0); - - while ( !heap.empty() ) { - - Node v=heap.top(); - ValueType oldvalue=heap[v]; - heap.pop(); - distance.set(v, oldvalue); - - { //FIXME this bracket is for e to be local - OutEdgeIt e; - for(G.first(e, v); - G.valid(e); G.next(e)) { - Node w=G.head(e); - - switch(heap.state(w)) { - case heap.PRE_HEAP: - heap.push(w,oldvalue+length[e]); - predecessor.set(w,e); - pred_node.set(w,v); - break; - case heap.IN_HEAP: - if ( oldvalue+length[e] < heap[w] ) { - heap.decrease(w, oldvalue+length[e]); - predecessor.set(w,e); - pred_node.set(w,v); - } - break; - case heap.POST_HEAP: - break; - } - } - } //FIXME tis bracket - } - } - -} //END OF NAMESPACE HUGO - -#endif - -