Changeset 926:ec0b1b423b8b in lemon for lemon/suurballe.h
 Timestamp:
 10/16/09 01:06:16 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/suurballe.h
r925 r926 47 47 /// "minimum cost flow problem". This implementation is actually an 48 48 /// efficient specialized version of the \ref CapacityScaling 49 /// " Successive Shortest Path" algorithm directly for this problem.49 /// "successive shortest path" algorithm directly for this problem. 50 50 /// Therefore this class provides query functions for flow values and 51 51 /// node potentials (the dual solution) just like the minimum cost flow … … 58 58 /// \warning Length values should be \e nonnegative. 59 59 /// 60 /// \note For finding nodedisjoint pathsthis algorithm can be used60 /// \note For finding \e nodedisjoint paths, this algorithm can be used 61 61 /// along with the \ref SplitNodes adaptor. 62 62 #ifdef DOXYGEN … … 110 110 private: 111 111 112 // The digraph the algorithm runs on113 112 const Digraph &_graph; 114 115 // The main maps 113 const LengthMap &_length; 116 114 const FlowMap &_flow; 117 const LengthMap &_length; 118 PotentialMap &_potential; 119 120 // The distance map 121 PotentialMap _dist; 122 // The pred arc map 115 PotentialMap &_pi; 123 116 PredMap &_pred; 124 // The processed (i.e. permanently labeled) nodes125 std::vector<Node> _proc_nodes;126 127 117 Node _s; 128 118 Node _t; 119 120 PotentialMap _dist; 121 std::vector<Node> _proc_nodes; 129 122 130 123 public: 131 124 132 /// Constructor. 133 ResidualDijkstra( const Digraph &graph, 134 const FlowMap &flow, 135 const LengthMap &length, 136 PotentialMap &potential, 137 PredMap &pred, 138 Node s, Node t ) : 139 _graph(graph), _flow(flow), _length(length), _potential(potential), 140 _dist(graph), _pred(pred), _s(s), _t(t) {} 141 142 /// \brief Run the algorithm. It returns \c true if a path is found 143 /// from the source node to the target node. 144 bool run() { 125 // Constructor 126 ResidualDijkstra(Suurballe &srb) : 127 _graph(srb._graph), _length(srb._length), 128 _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred), 129 _s(srb._s), _t(srb._t), _dist(_graph) {} 130 131 // Run the algorithm and return true if a path is found 132 // from the source node to the target node. 133 bool run(int cnt) { 134 return cnt == 0 ? startFirst() : start(); 135 } 136 137 private: 138 139 // Execute the algorithm for the first time (the flow and potential 140 // functions have to be identically zero). 141 bool startFirst() { 145 142 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP); 146 143 Heap heap(heap_cross_ref); … … 152 149 while (!heap.empty() && heap.top() != _t) { 153 150 Node u = heap.top(), v; 154 Length d = heap.prio() + _potential[u], nd;151 Length d = heap.prio(), dn; 155 152 _dist[u] = heap.prio(); 153 _proc_nodes.push_back(u); 156 154 heap.pop(); 155 156 // Traverse outgoing arcs 157 for (OutArcIt e(_graph, u); e != INVALID; ++e) { 158 v = _graph.target(e); 159 switch(heap.state(v)) { 160 case Heap::PRE_HEAP: 161 heap.push(v, d + _length[e]); 162 _pred[v] = e; 163 break; 164 case Heap::IN_HEAP: 165 dn = d + _length[e]; 166 if (dn < heap[v]) { 167 heap.decrease(v, dn); 168 _pred[v] = e; 169 } 170 break; 171 case Heap::POST_HEAP: 172 break; 173 } 174 } 175 } 176 if (heap.empty()) return false; 177 178 // Update potentials of processed nodes 179 Length t_dist = heap.prio(); 180 for (int i = 0; i < int(_proc_nodes.size()); ++i) 181 _pi[_proc_nodes[i]] = _dist[_proc_nodes[i]]  t_dist; 182 return true; 183 } 184 185 // Execute the algorithm. 186 bool start() { 187 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP); 188 Heap heap(heap_cross_ref); 189 heap.push(_s, 0); 190 _pred[_s] = INVALID; 191 _proc_nodes.clear(); 192 193 // Process nodes 194 while (!heap.empty() && heap.top() != _t) { 195 Node u = heap.top(), v; 196 Length d = heap.prio() + _pi[u], dn; 197 _dist[u] = heap.prio(); 157 198 _proc_nodes.push_back(u); 199 heap.pop(); 158 200 159 201 // Traverse outgoing arcs … … 162 204 v = _graph.target(e); 163 205 switch(heap.state(v)) { 164 case Heap::PRE_HEAP: 165 heap.push(v, d + _length[e]  _potential[v]); 166 _pred[v] = e; 167 break; 168 case Heap::IN_HEAP: 169 nd = d + _length[e]  _potential[v]; 170 if (nd < heap[v]) { 171 heap.decrease(v, nd); 206 case Heap::PRE_HEAP: 207 heap.push(v, d + _length[e]  _pi[v]); 172 208 _pred[v] = e; 173 } 174 break; 175 case Heap::POST_HEAP: 176 break; 209 break; 210 case Heap::IN_HEAP: 211 dn = d + _length[e]  _pi[v]; 212 if (dn < heap[v]) { 213 heap.decrease(v, dn); 214 _pred[v] = e; 215 } 216 break; 217 case Heap::POST_HEAP: 218 break; 177 219 } 178 220 } … … 184 226 v = _graph.source(e); 185 227 switch(heap.state(v)) { 186 case Heap::PRE_HEAP: 187 heap.push(v, d  _length[e]  _potential[v]); 188 _pred[v] = e; 189 break; 190 case Heap::IN_HEAP: 191 nd = d  _length[e]  _potential[v]; 192 if (nd < heap[v]) { 193 heap.decrease(v, nd); 228 case Heap::PRE_HEAP: 229 heap.push(v, d  _length[e]  _pi[v]); 194 230 _pred[v] = e; 195 } 196 break; 197 case Heap::POST_HEAP: 198 break; 231 break; 232 case Heap::IN_HEAP: 233 dn = d  _length[e]  _pi[v]; 234 if (dn < heap[v]) { 235 heap.decrease(v, dn); 236 _pred[v] = e; 237 } 238 break; 239 case Heap::POST_HEAP: 240 break; 199 241 } 200 242 } … … 206 248 Length t_dist = heap.prio(); 207 249 for (int i = 0; i < int(_proc_nodes.size()); ++i) 208 _p otential[_proc_nodes[i]] += _dist[_proc_nodes[i]]  t_dist;250 _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]]  t_dist; 209 251 return true; 210 252 } … … 227 269 228 270 // The source node 229 Node _s ource;271 Node _s; 230 272 // The target node 231 Node _t arget;273 Node _t; 232 274 233 275 // Container to store the found paths 234 std::vector< SimplePath<Digraph> >paths;276 std::vector<Path> _paths; 235 277 int _path_num; 236 278 237 279 // The pred arc map 238 280 PredMap _pred; 239 // Implementation of the Dijkstra algorithm for finding augmenting240 // shortest paths in the residual network241 ResidualDijkstra *_dijkstra;242 281 243 282 public: … … 259 298 if (_local_flow) delete _flow; 260 299 if (_local_potential) delete _potential; 261 delete _dijkstra;262 300 } 263 301 … … 343 381 /// \param s The source node. 344 382 void init(const Node& s) { 345 _s ource= s;383 _s = s; 346 384 347 385 // Initialize maps … … 373 411 /// \pre \ref init() must be called before using this function. 374 412 int findFlow(const Node& t, int k = 2) { 375 _target = t; 376 _dijkstra = 377 new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred, 378 _source, _target ); 413 _t = t; 414 ResidualDijkstra dijkstra(*this); 379 415 380 416 // Find shortest paths … … 382 418 while (_path_num < k) { 383 419 // Run Dijkstra 384 if (! _dijkstra>run()) break;420 if (!dijkstra.run(_path_num)) break; 385 421 ++_path_num; 386 422 387 423 // Set the flow along the found shortest path 388 Node u = _t arget;424 Node u = _t; 389 425 Arc e; 390 426 while ((e = _pred[u]) != INVALID) { … … 403 439 /// \brief Compute the paths from the flow. 404 440 /// 405 /// This function computes the paths from the found minimum cost flow,406 /// which is the union of some arcdisjoint paths.441 /// This function computes arcdisjoint paths from the found minimum 442 /// cost flow, which is the union of them. 407 443 /// 408 444 /// \pre \ref init() and \ref findFlow() must be called before using … … 412 448 for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a]; 413 449 414 paths.clear();415 paths.resize(_path_num);450 _paths.clear(); 451 _paths.resize(_path_num); 416 452 for (int i = 0; i < _path_num; ++i) { 417 Node n = _s ource;418 while (n != _t arget) {453 Node n = _s; 454 while (n != _t) { 419 455 OutArcIt e(_graph, n); 420 456 for ( ; res_flow[e] == 0; ++e) ; 421 457 n = _graph.target(e); 422 paths[i].addBack(e);458 _paths[i].addBack(e); 423 459 res_flow[e] = 0; 424 460 } … … 519 555 /// this function. 520 556 const Path& path(int i) const { 521 return paths[i];557 return _paths[i]; 522 558 } 523 559
Note: See TracChangeset
for help on using the changeset viewer.