22 /// \file |
22 /// \file |
23 /// \ingroup max_flow |
23 /// \ingroup max_flow |
24 /// \brief Implementation the dynamic tree data structure of Sleator |
24 /// \brief Implementation the dynamic tree data structure of Sleator |
25 /// and Tarjan. |
25 /// and Tarjan. |
26 |
26 |
27 #include <lemon/time_measure.h> |
|
28 #include <queue> |
|
29 #include <lemon/graph_utils.h> |
27 #include <lemon/graph_utils.h> |
30 #include <lemon/tolerance.h> |
28 #include <lemon/tolerance.h> |
31 #include <lemon/graph_adaptor.h> |
|
32 #include <lemon/bfs.h> |
|
33 #include <lemon/edge_set.h> |
|
34 #include <lemon/dynamic_tree.h> |
29 #include <lemon/dynamic_tree.h> |
35 |
30 |
36 #include <vector> |
31 #include <vector> |
37 #include <limits> |
32 #include <limits> |
38 #include <fstream> |
33 #include <fstream> |
227 Node source, Node target) |
224 Node source, Node target) |
228 : _graph(graph), _capacity(&capacity), |
225 : _graph(graph), _capacity(&capacity), |
229 _source(source), _target(target), |
226 _source(source), _target(target), |
230 _flow(0), _local_flow(false), |
227 _flow(0), _local_flow(false), |
231 _level(0), _dt_edges(0), |
228 _level(0), _dt_edges(0), |
232 _dt_index(0), _dt(0), |
229 _dt_index(0), _dt(0), _queue(), |
233 _tolerance(), _flow_value(), _max_value() |
230 _tolerance(), _flow_value(), _max_value() |
234 { |
231 { |
235 if (_source == _target) { |
232 if (_source == _target) { |
236 throw InvalidArgument(); |
233 throw InvalidArgument(); |
237 } |
234 } |
324 _dt = new DynTree(*_dt_index, _tolerance); |
321 _dt = new DynTree(*_dt_index, _tolerance); |
325 } |
322 } |
326 if (!_dt_edges) { |
323 if (!_dt_edges) { |
327 _dt_edges = new EdgeNodeMap(_graph); |
324 _dt_edges = new EdgeNodeMap(_graph); |
328 } |
325 } |
|
326 _queue.resize(countNodes(_graph)); |
329 _max_value = _dt->maxValue(); |
327 _max_value = _dt->maxValue(); |
330 } |
328 } |
331 |
329 |
332 void destroyStructures() { |
330 void destroyStructures() { |
333 if (_local_flow) { |
331 if (_local_flow) { |
353 _level->set(n, -2); |
351 _level->set(n, -2); |
354 } |
352 } |
355 |
353 |
356 int level = 0; |
354 int level = 0; |
357 |
355 |
358 std::vector<Node> queue; |
356 _queue[0] = _target; |
359 queue.push_back(_target); |
|
360 _level->set(_target, level); |
357 _level->set(_target, level); |
|
358 |
|
359 int first = 0, last = 1, limit = 0; |
361 |
360 |
362 while ((*_level)[_source] == -2 && !queue.empty()) { |
361 while (first != last && (*_level)[_source] == -2) { |
363 std::vector<Node> nqueue; |
362 if (first == limit) { |
364 ++level; |
363 limit = last; |
|
364 ++level; |
|
365 } |
365 |
366 |
366 for (int i = 0; i < int(queue.size()); ++i) { |
367 Node n = _queue[first++]; |
367 Node n = queue[i]; |
|
368 |
368 |
369 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) { |
369 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) { |
370 Node v = _graph.target(e); |
370 Node v = _graph.target(e); |
371 if ((*_level)[v] != -2) continue; |
371 if ((*_level)[v] != -2) continue; |
372 Value rem = (*_flow)[e]; |
372 Value rem = (*_flow)[e]; |
373 if (!_tolerance.positive(rem)) continue; |
373 if (!_tolerance.positive(rem)) continue; |
374 _level->set(v, level); |
374 _level->set(v, level); |
375 nqueue.push_back(v); |
375 _queue[last++] = v; |
376 } |
376 } |
377 |
377 |
378 for (InEdgeIt e(_graph, n); e != INVALID; ++e) { |
378 for (InEdgeIt e(_graph, n); e != INVALID; ++e) { |
379 Node v = _graph.source(e); |
379 Node v = _graph.source(e); |
380 if ((*_level)[v] != -2) continue; |
380 if ((*_level)[v] != -2) continue; |
381 Value rem = (*_capacity)[e] - (*_flow)[e]; |
381 Value rem = (*_capacity)[e] - (*_flow)[e]; |
382 if (!_tolerance.positive(rem)) continue; |
382 if (!_tolerance.positive(rem)) continue; |
383 _level->set(v, level); |
383 _level->set(v, level); |
384 nqueue.push_back(v); |
384 _queue[last++] = v; |
385 } |
385 } |
386 |
386 } |
387 } |
|
388 queue.swap(nqueue); |
|
389 } |
|
390 |
|
391 return (*_level)[_source] != -2; |
387 return (*_level)[_source] != -2; |
392 } |
388 } |
393 |
389 |
394 void initEdges() { |
390 void initEdges() { |
395 for (NodeIt n(_graph); n != INVALID; ++n) { |
391 for (NodeIt n(_graph); n != INVALID; ++n) { |