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