Changeset 372:e6a156fc186d in lemon0.x for src/work/jacint/dijkstra.h
 Timestamp:
 04/22/04 16:11:28 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@502
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/dijkstra.h
r220 r372 1 1 // * C++ * 2 2 3 /* 3 4 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> > … … 27 28 #define HUGO_DIJKSTRA_H 28 29 30 ///\file 31 ///\brief Dijkstra algorithm. 32 29 33 #include <fib_heap.h> 34 #include <bin_heap.h> 30 35 #include <invalid.h> 31 36 32 37 namespace hugo { 33 38 34 template <typename Graph, typename T, 35 typename Heap=FibHeap<typename Graph::Node, T, 36 typename Graph::NodeMap<int> >, 37 typename LengthMap=typename Graph::EdgeMap<T> > 39 //Alpar: Changed the order of the parameters 40 41 ///%Dijkstra algorithm class. 42 43 ///This class provides an efficient implementation of %Dijkstra algorithm. 44 ///The edge lengths are passed to the algorithm using a 45 ///\ref ReadMapSkeleton "readable map", 46 ///so it is easy to change it to any kind of length. 47 /// 48 ///The type of the length is determined by the \c ValueType of the length map. 49 /// 50 ///It is also possible to change the underlying priority heap. 51 /// 52 ///\param Graph The graph type the algorithm runs on. 53 ///\param LengthMap This readonly 54 ///EdgeMap 55 ///determines the 56 ///lengths of the edges. It is read once for each edge, so the map 57 ///may involve in relatively time consuming process to compute the edge 58 ///length if it is necessary. The default map type is 59 ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" 60 ///\param Heap The heap type used by the %Dijkstra 61 ///algorithm. The default 62 ///is using \ref BinHeap "binary heap". 63 64 #ifdef DOXYGEN 65 template <typename Graph, 66 typename LengthMap, 67 typename Heap> 68 #else 69 template <typename Graph, 70 typename LengthMap=typename Graph::EdgeMap<int>, 71 template <class,class,class> class Heap = BinHeap > 72 #endif 38 73 class Dijkstra{ 74 public: 39 75 typedef typename Graph::Node Node; 40 76 typedef typename Graph::NodeIt NodeIt; … … 42 78 typedef typename Graph::OutEdgeIt OutEdgeIt; 43 79 80 typedef typename LengthMap::ValueType ValueType; 81 typedef typename Graph::NodeMap<Edge> PredMap; 82 typedef typename Graph::NodeMap<Node> PredNodeMap; 83 typedef typename Graph::NodeMap<ValueType> DistMap; 84 85 private: 44 86 const Graph& G; 45 87 const LengthMap& length; 46 typename Graph::NodeMap<Edge> predecessor; 47 typename Graph::NodeMap<T> distance; 48 //FIXME: 49 typename Graph::NodeMap<bool> reach; 50 //typename Graph::NodeMap<int> reach; 88 PredMap predecessor; 89 PredNodeMap pred_node; 90 DistMap distance; 51 91 52 92 public : 53 93 54 /* 55 The distance of the nodes is 0. 56 */ 57 Dijkstra(Graph& _G, LengthMap& _length) : G(_G), 58 length(_length), predecessor(_G), distance(_G), reach(_G) { } 59 60 61 void run(Node s) { 62 63 NodeIt u; 64 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { 65 predecessor.set(u,INVALID); 66 distance.set(u,0); 67 reach.set(u,false); 68 } 69 70 //FIXME: 71 typename Graph::NodeMap<bool> scanned(G,false); 72 //typename Graph::NodeMap<int> scanned(G,false); 73 typename Graph::NodeMap<int> heap_map(G,1); 74 75 Heap heap(heap_map); 76 77 heap.push(s,0); 78 reach.set(s, true); 79 94 Dijkstra(Graph& _G, LengthMap& _length) : 95 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } 96 97 void run(Node s); 98 99 ///The distance of a node from the source. 100 101 ///Returns the distance of a node from the source. 102 ///\pre \ref run() must be called before using this function. 103 ///\warning If node \c v in unreachable from the source the return value 104 ///of this funcion is undefined. 105 ValueType dist(Node v) const { return distance[v]; } 106 ///Returns the edges of the shortest path tree. 107 108 ///For a node \c v it returns the last edge of the shortest path 109 ///from the source to \c v or INVALID if \c v is unreachable 110 ///from the source. 111 ///\pre \ref run() must be called before using this function. 112 Edge pred(Node v) const { return predecessor[v]; } 113 ///Returns the nodes of the shortest paths. 114 115 ///For a node \c v it returns the last but one node of the shortest path 116 ///from the source to \c v or INVALID if \c v is unreachable 117 ///from the source. 118 ///\pre \ref run() must be called before using this function. 119 Node predNode(Node v) const { return pred_node[v]; } 120 121 ///Returns a reference to the NodeMap of distances. 122 123 ///\pre \ref run() must be called before using this function. 124 /// 125 const DistMap &distMap() const { return distance;} 126 ///Returns a reference to the shortest path tree map. 127 128 ///Returns a reference to the NodeMap of the edges of the 129 ///shortest path tree. 130 ///\pre \ref run() must be called before using this function. 131 const PredMap &predMap() const { return predecessor;} 132 ///Returns a reference to the map of nodes of shortest paths. 133 134 ///Returns a reference to the NodeMap of the last but one nodes of the 135 ///shortest paths. 136 ///\pre \ref run() must be called before using this function. 137 const PredNodeMap &predNodeMap() const { return pred_node;} 138 139 ///Checks if a node is reachable from the source. 140 141 ///Returns \c true if \c v is reachable from the source. 142 ///\warning the source node is reported to be unreached! 143 ///\todo Is this what we want? 144 ///\pre \ref run() must be called before using this function. 145 /// 146 bool reached(Node v) { return G.valid(predecessor[v]); } 147 148 }; 149 150 151 // ********************************************************************** 152 // IMPLEMENTATIONS 153 // ********************************************************************** 154 155 ///Runs %Dijkstra algorithm from node the source. 156 157 ///This method runs the %Dijkstra algorithm from a source node \c s 158 ///in order to 159 ///compute the 160 ///shortest path to each node. The algorithm computes 161 /// The shortest path tree. 162 /// The distance of each node from the source. 163 template <typename Graph, typename LengthMap, 164 template<class,class,class> class Heap > 165 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { 166 167 NodeIt u; 168 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { 169 predecessor.set(u,INVALID); 170 pred_node.set(u,INVALID); 171 // If a node is unreacheable, then why should be the dist=0? 172 // distance.set(u,0); 173 // reach.set(u,false); 174 } 175 176 typename Graph::NodeMap<int> heap_map(G,1); 177 178 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map); 179 180 heap.push(s,0); 181 80 182 while ( !heap.empty() ) { 81 183 82 184 Node v=heap.top(); 83 T oldvalue=heap.get(v);185 ValueType oldvalue=heap[v]; 84 186 heap.pop(); 85 187 distance.set(v, oldvalue); 86 scanned.set(v,true); 87 88 OutEdgeIt e; 89 for( G.first(e,v); G.valid(e); G.next(e)) { 188 189 { //FIXME this bracket is for e to be local 190 OutEdgeIt e; 191 for(G.first(e, v); 192 G.valid(e); G.next(e)) { 90 193 Node w=G.head(e); 91 92 if ( !scanned[w] ) { 93 if ( !reach[w] ) { 94 reach.set(w,true); 95 heap.push(w,oldvalue+length[e]); 194 195 switch(heap.state(w)) { 196 case heap.PRE_HEAP: 197 heap.push(w,oldvalue+length[e]); 198 predecessor.set(w,e); 199 pred_node.set(w,v); 200 break; 201 case heap.IN_HEAP: 202 if ( oldvalue+length[e] < heap[w] ) { 203 heap.decrease(w, oldvalue+length[e]); 96 204 predecessor.set(w,e); 97 } else if ( oldvalue+length[e] < heap.get(w) ) { 98 predecessor.set(w,e); 99 heap.decrease(w, oldvalue+length[e]); 205 pred_node.set(w,v); 100 206 } 207 break; 208 case heap.POST_HEAP: 209 break; 101 210 } 102 211 } 212 } //FIXME tis bracket 103 213 } 104 } 105 106 T dist(Node v) { 107 return distance[v]; 108 } 109 110 Edge pred(Node v) { 111 return predecessor[v]; 112 } 113 114 bool reached(Node v) { 115 return reach[v]; 116 } 117 118 }; 119 120 } 214 } 215 216 } //END OF NAMESPACE HUGO 121 217 122 218 #endif
Note: See TracChangeset
for help on using the changeset viewer.