1.1 --- a/src/include/dijkstra.h Thu Apr 22 14:11:28 2004 +0000
1.2 +++ b/src/include/dijkstra.h Thu Apr 22 14:50:24 2004 +0000
1.3 @@ -1,29 +1,5 @@
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 @@ -36,8 +12,6 @@
1.34
1.35 namespace hugo {
1.36
1.37 - //Alpar: Changed the order of the parameters
1.38 -
1.39 ///%Dijkstra algorithm class.
1.40
1.41 ///This class provides an efficient implementation of %Dijkstra algorithm.
1.42 @@ -49,17 +23,14 @@
1.43 ///
1.44 ///It is also possible to change the underlying priority heap.
1.45 ///
1.46 - ///\param Graph The graph type the algorithm runs on.
1.47 - ///\param LengthMap This read-only
1.48 - ///EdgeMap
1.49 - ///determines the
1.50 - ///lengths of the edges. It is read once for each edge, so the map
1.51 - ///may involve in relatively time consuming process to compute the edge
1.52 - ///length if it is necessary. The default map type is
1.53 - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
1.54 - ///\param Heap The heap type used by the %Dijkstra
1.55 - ///algorithm. The default
1.56 - ///is using \ref BinHeap "binary heap".
1.57 + ///\param Graph The graph type the algorithm runs on.
1.58 + ///\param LengthMap This read-only EdgeMap determines the lengths of
1.59 + ///the edges. It is read once for each edge, so the map may involve
1.60 + ///in relatively time consuming process to compute the edge length
1.61 + ///if it is necessary. The default map type is \ref
1.62 + ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
1.63 + ///\param Heap The heap type used by the %Dijkstra algorithm. The
1.64 + ///default is using \ref BinHeap "binary heap".
1.65
1.66 #ifdef DOXYGEN
1.67 template <typename Graph,
1.68 @@ -103,6 +74,7 @@
1.69 ///\warning If node \c v in unreachable from the source the return value
1.70 ///of this funcion is undefined.
1.71 ValueType dist(Node v) const { return distance[v]; }
1.72 +
1.73 ///Returns the edges of the shortest path tree.
1.74
1.75 ///For a node \c v it returns the last edge of the shortest path
1.76 @@ -110,6 +82,7 @@
1.77 ///from the source.
1.78 ///\pre \ref run() must be called before using this function.
1.79 Edge pred(Node v) const { return predecessor[v]; }
1.80 +
1.81 ///Returns the nodes of the shortest paths.
1.82
1.83 ///For a node \c v it returns the last but one node of the shortest path
1.84 @@ -123,12 +96,14 @@
1.85 ///\pre \ref run() must be called before using this function.
1.86 ///
1.87 const DistMap &distMap() const { return distance;}
1.88 +
1.89 ///Returns a reference to the shortest path tree map.
1.90
1.91 ///Returns a reference to the NodeMap of the edges of the
1.92 ///shortest path tree.
1.93 ///\pre \ref run() must be called before using this function.
1.94 const PredMap &predMap() const { return predecessor;}
1.95 +
1.96 ///Returns a reference to the map of nodes of shortest paths.
1.97
1.98 ///Returns a reference to the NodeMap of the last but one nodes of the
1.99 @@ -142,7 +117,6 @@
1.100 ///\warning the source node is reported to be unreached!
1.101 ///\todo Is this what we want?
1.102 ///\pre \ref run() must be called before using this function.
1.103 - ///
1.104 bool reached(Node v) { return G.valid(predecessor[v]); }
1.105
1.106 };
1.107 @@ -152,14 +126,12 @@
1.108 // IMPLEMENTATIONS
1.109 // **********************************************************************
1.110
1.111 - ///Runs %Dijkstra algorithm from node the source.
1.112 + ///Runs %Dijkstra algorithm from source node \c s.
1.113
1.114 ///This method runs the %Dijkstra algorithm from a source node \c s
1.115 - ///in order to
1.116 - ///compute the
1.117 - ///shortest path to each node. The algorithm computes
1.118 - ///- The shortest path tree.
1.119 - ///- The distance of each node from the source.
1.120 + ///in order to compute the shortest path to each node. The algorithm
1.121 + ///computes - The shortest path tree. - The distance of each node
1.122 + ///from the source.
1.123 template <typename Graph, typename LengthMap,
1.124 template<class,class,class> class Heap >
1.125 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
1.126 @@ -168,28 +140,23 @@
1.127 for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
1.128 predecessor.set(u,INVALID);
1.129 pred_node.set(u,INVALID);
1.130 - // If a node is unreacheable, then why should be the dist=0?
1.131 - // distance.set(u,0);
1.132 - // reach.set(u,false);
1.133 }
1.134
1.135 typename Graph::NodeMap<int> heap_map(G,-1);
1.136
1.137 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
1.138 -
1.139 heap.push(s,0);
1.140
1.141 - while ( !heap.empty() ) {
1.142 + while ( !heap.empty() ) {
1.143 +
1.144 + Node v=heap.top();
1.145 + ValueType oldvalue=heap[v];
1.146 + heap.pop();
1.147 + distance.set(v, oldvalue);
1.148
1.149 - Node v=heap.top();
1.150 - ValueType oldvalue=heap[v];
1.151 - heap.pop();
1.152 - distance.set(v, oldvalue);
1.153 -
1.154 - { //FIXME this bracket is for e to be local
1.155 - OutEdgeIt e;
1.156 - for(G.first(e, v);
1.157 - G.valid(e); G.next(e)) {
1.158 + { //FIXME this bracket is for e to be local
1.159 + OutEdgeIt e;
1.160 + for(G.first(e, v); G.valid(e); G.next(e)) {
1.161 Node w=G.head(e);
1.162
1.163 switch(heap.state(w)) {
1.164 @@ -209,8 +176,8 @@
1.165 break;
1.166 }
1.167 }
1.168 - } //FIXME tis bracket
1.169 - }
1.170 + } //FIXME this bracket
1.171 + }
1.172 }
1.173
1.174 } //END OF NAMESPACE HUGO