Changeset 385:d7ebbae96025 in lemon0.x
 Timestamp:
 04/23/04 21:04:05 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@515
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/include/dijkstra.h
r373 r385 1 1 // * C++ * 2 3 2 #ifndef HUGO_DIJKSTRA_H 4 3 #define HUGO_DIJKSTRA_H … … 7 6 ///\brief Dijkstra algorithm. 8 7 9 #include <fib_heap.h>10 8 #include <bin_heap.h> 11 9 #include <invalid.h> 12 10 13 11 namespace hugo { 14 12 15 13 ///%Dijkstra algorithm class. 16 14 … … 24 22 ///It is also possible to change the underlying priority heap. 25 23 /// 26 ///\param Graph The graph type the algorithm runs on. 27 ///\param LengthMap This readonly EdgeMap determines the lengths of 28 ///the edges. It is read once for each edge, so the map may involve 29 ///in relatively time consuming process to compute the edge length 30 ///if it is necessary. The default map type is \ref 31 ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" 32 ///\param Heap The heap type used by the %Dijkstra algorithm. The 33 ///default is using \ref BinHeap "binary heap". 24 ///\param Graph The graph type the algorithm runs on. 25 ///\param LengthMap This readonly 26 ///EdgeMap 27 ///determines the 28 ///lengths of the edges. It is read once for each edge, so the map 29 ///may involve in relatively time consuming process to compute the edge 30 ///length if it is necessary. The default map type is 31 ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" 32 ///\param Heap The heap type used by the %Dijkstra 33 ///algorithm. The default 34 ///is using \ref BinHeap "binary heap". 34 35 35 36 #ifdef DOXYGEN … … 68 69 void run(Node s); 69 70 70 ///The distance of a node from the source.71 ///The distance of a node from the root. 71 72 72 ///Returns the distance of a node from the source.73 ///Returns the distance of a node from the root. 73 74 ///\pre \ref run() must be called before using this function. 74 ///\warning If node \c v in unreachable from the sourcethe return value75 ///\warning If node \c v in unreachable from the root the return value 75 76 ///of this funcion is undefined. 76 77 ValueType dist(Node v) const { return distance[v]; } 77 78 78 ///Returns the edgesof the shortest path tree.79 ///Returns the previous edge of the shortest path tree. 79 80 80 ///For a node \c v it returns the last edge of the shortest path 81 ///from the source to \c v or INVALID if \c v is unreachable 82 ///from the source. 83 ///\pre \ref run() must be called before using this function. 81 ///For a node \c v it returns the previous edge of the shortest path tree, 82 ///i.e. it returns the last edge from a shortest path from the root to \c 83 ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The 84 ///shortest path tree used here is equal to the shortest path tree used in 85 ///\ref predNode(Node v). \pre \ref run() must be called before using 86 ///this function. 84 87 Edge pred(Node v) const { return predecessor[v]; } 85 88 86 ///Returns the nodes of the shortest paths.89 ///Returns the previous node of the shortest path tree. 87 90 88 ///For a node \c v it returns the last but one node of the shortest path 89 ///from the source to \c v or INVALID if \c v is unreachable 90 ///from the source. 91 ///\pre \ref run() must be called before using this function. 91 ///For a node \c v it returns the previous node of the shortest path tree, 92 ///i.e. it returns the last but one node from a shortest path from the 93 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if 94 ///\c v=s. The shortest path tree used here is equal to the shortest path 95 ///tree used in \ref pred(Node v). \pre \ref run() must be called before 96 ///using this function. 92 97 Node predNode(Node v) const { return pred_node[v]; } 93 98 94 99 ///Returns a reference to the NodeMap of distances. 95 100 96 /// \pre \ref run() must be called before using this function.97 /// 101 ///Returns a reference to the NodeMap of distances. \pre \ref run() must 102 ///be called before using this function. 98 103 const DistMap &distMap() const { return distance;} 99 104 100 105 ///Returns a reference to the shortest path tree map. 101 106 … … 104 109 ///\pre \ref run() must be called before using this function. 105 110 const PredMap &predMap() const { return predecessor;} 106 107 ///Returns a reference to the map of nodes of 111 112 ///Returns a reference to the map of nodes of shortest paths. 108 113 109 114 ///Returns a reference to the NodeMap of the last but one nodes of the 110 ///shortest path s.115 ///shortest path tree. 111 116 ///\pre \ref run() must be called before using this function. 112 117 const PredNodeMap &predNodeMap() const { return pred_node;} 113 118 114 ///Checks if a node is reachable from the source.119 ///Checks if a node is reachable from the root. 115 120 116 ///Returns \c true if \c v is reachable from the source.117 ///\warning the sourcenode is reported to be unreached!121 ///Returns \c true if \c v is reachable from the root. 122 ///\warning the root node is reported to be unreached! 118 123 ///\todo Is this what we want? 119 124 ///\pre \ref run() must be called before using this function. 125 /// 120 126 bool reached(Node v) { return G.valid(predecessor[v]); } 121 127 … … 127 133 // ********************************************************************** 128 134 129 ///Runs %Dijkstra algorithm from source node \c s.135 ///Runs %Dijkstra algorithm from node the root. 130 136 131 ///This method runs the %Dijkstra algorithm from a source node \c s 132 ///in order to compute the shortest path to each node. The algorithm 133 ///computes  The shortest path tree.  The distance of each node 134 ///from the source. 137 ///This method runs the %Dijkstra algorithm from a root node \c s 138 ///in order to 139 ///compute the 140 ///shortest path to each node. The algorithm computes 141 /// The shortest path tree. 142 /// The distance of each node from the root. 135 143 template <typename Graph, typename LengthMap, 136 144 template<class,class,class> class Heap > … … 146 154 147 155 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map); 156 148 157 heap.push(s,0); 149 158 150 while ( !heap.empty() ) { 151 152 Node v=heap.top(); 153 ValueType oldvalue=heap[v]; 154 heap.pop(); 155 distance.set(v, oldvalue); 159 while ( !heap.empty() ) { 156 160 157 { //FIXME this bracket is for e to be local 158 OutEdgeIt e; 159 for(G.first(e, v); G.valid(e); G.next(e)) { 161 Node v=heap.top(); 162 ValueType oldvalue=heap[v]; 163 heap.pop(); 164 distance.set(v, oldvalue); 165 166 { //FIXME this bracket is for e to be local 167 OutEdgeIt e; 168 for(G.first(e, v); 169 G.valid(e); G.next(e)) { 160 170 Node w=G.head(e); 161 171 … … 177 187 } 178 188 } 179 } //FIXME t his bracket180 }189 } //FIXME tis bracket 190 } 181 191 } 182 192
Note: See TracChangeset
for help on using the changeset viewer.