Fix warning when compiling with -Wall.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_DINITZ_SLEATOR_TARJAN_H
20 #define LEMON_DINITZ_SLEATOR_TARJAN_H
24 /// \brief Implementation the dynamic tree data structure of Sleator
27 #include <lemon/graph_utils.h>
28 #include <lemon/tolerance.h>
29 #include <lemon/dynamic_tree.h>
38 /// \brief Default traits class of DinitzSleatorTarjan class.
40 /// Default traits class of DinitzSleatorTarjan class.
41 /// \param _Graph Graph type.
42 /// \param _CapacityMap Type of capacity map.
43 template <typename _Graph, typename _CapacityMap>
44 struct DinitzSleatorTarjanDefaultTraits {
46 /// \brief The graph type the algorithm runs on.
49 /// \brief The type of the map that stores the edge capacities.
51 /// The type of the map that stores the edge capacities.
52 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
53 typedef _CapacityMap CapacityMap;
55 /// \brief The type of the length of the edges.
56 typedef typename CapacityMap::Value Value;
58 /// \brief The map type that stores the flow values.
60 /// The map type that stores the flow values.
61 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
62 typedef typename Graph::template EdgeMap<Value> FlowMap;
64 /// \brief Instantiates a FlowMap.
66 /// This function instantiates a \ref FlowMap.
67 /// \param graph The graph, to which we would like to define the flow map.
68 static FlowMap* createFlowMap(const Graph& graph) {
69 return new FlowMap(graph);
72 /// \brief The tolerance used by the algorithm
74 /// The tolerance used by the algorithm to handle inexact computation.
75 typedef Tolerance<Value> Tolerance;
81 /// \brief Dinitz-Sleator-Tarjan algorithms class.
83 /// This class provides an implementation of the \e
84 /// Dinitz-Sleator-Tarjan \e algorithm producing a flow of maximum
85 /// value in a directed graph. The DinitzSleatorTarjan algorithm is
86 /// the fastest known max flow algorithms wich using blocking
87 /// flow. It is an improvement of the Dinitz algorithm by using the
88 /// \ref DynamicTree "dynamic tree" data structure of Sleator and
91 /// This blocking flow algorithms builds a layered graph according
92 /// to \ref Bfs "breadth-first search" distance from the target node
93 /// in the reversed residual graph. The layered graph contains each
94 /// residual edge which steps one level down. After that the
95 /// algorithm constructs a blocking flow on the layered graph and
96 /// augments the overall flow with it. The number of the levels in
97 /// the layered graph is strictly increasing in each augmenting
98 /// phase therefore the number of the augmentings is at most
99 /// \f$n-1\f$. The length of each phase is at most
100 /// \f$O(m\log(n))\f$, that the overall time complexity is
101 /// \f$O(nm\log(n))\f$.
103 /// \param _Graph The directed graph type the algorithm runs on.
104 /// \param _CapacityMap The capacity map type.
105 /// \param _Traits Traits class to set various data types used by
106 /// the algorithm. The default traits class is \ref
107 /// DinitzSleatorTarjanDefaultTraits. See \ref
108 /// DinitzSleatorTarjanDefaultTraits for the documentation of a
109 /// Dinitz-Sleator-Tarjan traits class.
111 /// \author Tamas Hamori and Balazs Dezso
113 template <typename _Graph, typename _CapacityMap, typename _Traits>
115 template <typename _Graph,
116 typename _CapacityMap = typename _Graph::template EdgeMap<int>,
118 DinitzSleatorTarjanDefaultTraits<_Graph, _CapacityMap> >
120 class DinitzSleatorTarjan {
123 typedef _Traits Traits;
124 typedef typename Traits::Graph Graph;
125 typedef typename Traits::CapacityMap CapacityMap;
126 typedef typename Traits::Value Value;
128 typedef typename Traits::FlowMap FlowMap;
129 typedef typename Traits::Tolerance Tolerance;
134 GRAPH_TYPEDEFS(typename Graph);
137 typedef typename Graph::template NodeMap<int> LevelMap;
138 typedef typename Graph::template NodeMap<int> IntNodeMap;
139 typedef typename Graph::template NodeMap<Edge> EdgeNodeMap;
140 typedef DynamicTree<Value, IntNodeMap, Tolerance, false> DynTree;
145 const CapacityMap* _capacity;
147 Node _source, _target;
153 EdgeNodeMap* _dt_edges;
155 IntNodeMap* _dt_index;
158 std::vector<Node> _queue;
160 Tolerance _tolerance;
168 typedef DinitzSleatorTarjan Create;
170 ///\name Named template parameters
174 template <typename _FlowMap>
175 struct DefFlowMapTraits : public Traits {
176 typedef _FlowMap FlowMap;
177 static FlowMap *createFlowMap(const Graph&) {
178 throw UninitializedParameter();
182 /// \brief \ref named-templ-param "Named parameter" for setting
185 /// \ref named-templ-param "Named parameter" for setting FlowMap
187 template <typename _FlowMap>
189 : public DinitzSleatorTarjan<Graph, CapacityMap,
190 DefFlowMapTraits<_FlowMap> > {
191 typedef DinitzSleatorTarjan<Graph, CapacityMap,
192 DefFlowMapTraits<_FlowMap> > Create;
195 template <typename _Elevator>
196 struct DefElevatorTraits : public Traits {
197 typedef _Elevator Elevator;
198 static Elevator *createElevator(const Graph&, int) {
199 throw UninitializedParameter();
205 /// \brief \ref Exception for the case when the source equals the target.
207 /// \ref Exception for the case when the source equals the target.
209 class InvalidArgument : public lemon::LogicError {
211 virtual const char* what() const throw() {
212 return "lemon::DinitzSleatorTarjan::InvalidArgument";
216 /// \brief The constructor of the class.
218 /// The constructor of the class.
219 /// \param graph The directed graph the algorithm runs on.
220 /// \param capacity The capacity of the edges.
221 /// \param source The source node.
222 /// \param target The target node.
223 DinitzSleatorTarjan(const Graph& graph, const CapacityMap& capacity,
224 Node source, Node target)
225 : _graph(graph), _capacity(&capacity),
226 _source(source), _target(target),
227 _flow(0), _local_flow(false),
228 _level(0), _dt_edges(0),
229 _dt_index(0), _dt(0), _queue(),
230 _tolerance(), _flow_value(), _max_value()
232 if (_source == _target) {
233 throw InvalidArgument();
237 /// \brief Destrcutor.
240 ~DinitzSleatorTarjan() {
244 /// \brief Sets the capacity map.
246 /// Sets the capacity map.
247 /// \return \c (*this)
248 DinitzSleatorTarjan& capacityMap(const CapacityMap& map) {
253 /// \brief Sets the flow map.
255 /// Sets the flow map.
256 /// \return \c (*this)
257 DinitzSleatorTarjan& flowMap(FlowMap& map) {
266 /// \brief Returns the flow map.
268 /// \return The flow map.
269 const FlowMap& flowMap() {
273 /// \brief Sets the source node.
275 /// Sets the source node.
276 /// \return \c (*this)
277 DinitzSleatorTarjan& source(const Node& node) {
282 /// \brief Sets the target node.
284 /// Sets the target node.
285 /// \return \c (*this)
286 DinitzSleatorTarjan& target(const Node& node) {
291 /// \brief Sets the tolerance used by algorithm.
293 /// Sets the tolerance used by algorithm.
294 DinitzSleatorTarjan& tolerance(const Tolerance& tolerance) const {
295 _tolerance = tolerance;
297 _dt.tolerance(_tolerance);
302 /// \brief Returns the tolerance used by algorithm.
304 /// Returns the tolerance used by algorithm.
305 const Tolerance& tolerance() const {
311 void createStructures() {
313 _flow = Traits::createFlowMap(_graph);
317 _level = new LevelMap(_graph);
319 if (!_dt_index && !_dt) {
320 _dt_index = new IntNodeMap(_graph);
321 _dt = new DynTree(*_dt_index, _tolerance);
324 _dt_edges = new EdgeNodeMap(_graph);
326 _queue.resize(countNodes(_graph));
327 _max_value = _dt->maxValue();
330 void destroyStructures() {
348 bool createLayeredGraph() {
350 for (NodeIt n(_graph); n != INVALID; ++n) {
357 _level->set(_target, level);
359 int first = 0, last = 1, limit = 0;
361 while (first != last && (*_level)[_source] == -2) {
362 if (first == limit) {
367 Node n = _queue[first++];
369 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
370 Node v = _graph.target(e);
371 if ((*_level)[v] != -2) continue;
372 Value rem = (*_flow)[e];
373 if (!_tolerance.positive(rem)) continue;
374 _level->set(v, level);
378 for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
379 Node v = _graph.source(e);
380 if ((*_level)[v] != -2) continue;
381 Value rem = (*_capacity)[e] - (*_flow)[e];
382 if (!_tolerance.positive(rem)) continue;
383 _level->set(v, level);
387 return (*_level)[_source] != -2;
391 for (NodeIt n(_graph); n != INVALID; ++n) {
392 _graph.firstOut((*_dt_edges)[n], n);
399 Node n = _dt->findCost(_source, rem);
401 _dt->addCost(_source, - rem);
404 _dt->addCost(n, _max_value);
406 Edge e = (*_dt_edges)[n];
407 if (_graph.source(e) == n) {
408 _flow->set(e, (*_capacity)[e]);
412 _graph.firstIn(e, n);
418 _dt_edges->set(n, e);
422 bool advance(Node n) {
423 Edge e = (*_dt_edges)[n];
424 if (e == INVALID) return false;
428 if (_graph.source(e) == n) {
429 u = _graph.target(e);
430 while ((*_level)[n] != (*_level)[u] + 1 ||
431 !_tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
433 if (e == INVALID) break;
434 u = _graph.target(e);
437 rem = (*_capacity)[e] - (*_flow)[e];
439 _graph.firstIn(e, n);
441 _dt_edges->set(n, INVALID);
444 u = _graph.source(e);
445 while ((*_level)[n] != (*_level)[u] + 1 ||
446 !_tolerance.positive((*_flow)[e])) {
449 _dt_edges->set(n, INVALID);
452 u = _graph.source(e);
457 u = _graph.source(e);
458 while ((*_level)[n] != (*_level)[u] + 1 ||
459 !_tolerance.positive((*_flow)[e])) {
462 _dt_edges->set(n, INVALID);
465 u = _graph.source(e);
470 _dt->addCost(n, - std::numeric_limits<Value>::max());
471 _dt->addCost(n, rem);
473 _dt_edges->set(n, e);
477 void retreat(Node n) {
480 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
481 Node u = _graph.target(e);
482 if ((*_dt_edges)[u] == e && _dt->findRoot(u) == n) {
484 _dt->findCost(u, rem);
487 _dt->addCost(u, - rem);
488 _dt->addCost(u, _max_value);
491 for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
492 Node u = _graph.source(e);
493 if ((*_dt_edges)[u] == e && _dt->findRoot(u) == n) {
495 _dt->findCost(u, rem);
496 _flow->set(e, (*_capacity)[e] - rem);
498 _dt->addCost(u, - rem);
499 _dt->addCost(u, _max_value);
504 void extractTrees() {
505 for (NodeIt n(_graph); n != INVALID; ++n) {
507 Node w = _dt->findRoot(n);
512 Node u = _dt->findCost(n, rem);
515 _dt->addCost(u, - rem);
516 _dt->addCost(u, _max_value);
518 Edge e = (*_dt_edges)[u];
519 _dt_edges->set(u, INVALID);
521 if (u == _graph.source(e)) {
522 _flow->set(e, (*_capacity)[e] - rem);
527 w = _dt->findRoot(n);
535 /// \name Execution control The simplest way to execute the
536 /// algorithm is to use the \c run() member functions.
538 /// If you need more control on initial solution or
539 /// execution then you have to call one \ref init() function and then
540 /// the start() or multiple times the \c augment() member function.
544 /// \brief Initializes the algorithm
546 /// It sets the flow to empty flow.
551 for (NodeIt n(_graph); n != INVALID; ++n) {
553 _dt->addCost(n, _max_value);
556 for (EdgeIt it(_graph); it != INVALID; ++it) {
562 /// \brief Initializes the algorithm
564 /// Initializes the flow to the \c flowMap. The \c flowMap should
565 /// contain a feasible flow, ie. in each node excluding the source
566 /// and the target the incoming flow should be equal to the
568 template <typename FlowMap>
569 void flowInit(const FlowMap& flowMap) {
573 for (NodeIt n(_graph); n != INVALID; ++n) {
575 _dt->addCost(n, _max_value);
578 for (EdgeIt e(_graph); e != INVALID; ++e) {
579 _flow->set(e, flowMap[e]);
582 for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
583 _flow_value += (*_flow)[jt];
585 for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
586 _flow_value -= (*_flow)[jt];
590 /// \brief Initializes the algorithm
592 /// Initializes the flow to the \c flowMap. The \c flowMap should
593 /// contain a feasible flow, ie. in each node excluding the source
594 /// and the target the incoming flow should be equal to the
596 /// \return %False when the given flowMap does not contain
598 template <typename FlowMap>
599 bool checkedFlowInit(const FlowMap& flowMap) {
603 for (NodeIt n(_graph); n != INVALID; ++n) {
605 _dt->addCost(n, _max_value);
608 for (EdgeIt e(_graph); e != INVALID; ++e) {
609 _flow->set(e, flowMap[e]);
611 for (NodeIt it(_graph); it != INVALID; ++it) {
612 if (it == _source || it == _target) continue;
614 for (OutEdgeIt jt(_graph, it); jt != INVALID; ++jt) {
615 outFlow += (*_flow)[jt];
618 for (InEdgeIt jt(_graph, it); jt != INVALID; ++jt) {
619 inFlow += (*_flow)[jt];
621 if (_tolerance.different(outFlow, inFlow)) {
625 for (EdgeIt it(_graph); it != INVALID; ++it) {
626 if (_tolerance.less((*_flow)[it], 0)) return false;
627 if (_tolerance.less((*_capacity)[it], (*_flow)[it])) return false;
630 for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
631 _flow_value += (*_flow)[jt];
633 for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
634 _flow_value -= (*_flow)[jt];
639 /// \brief Executes the algorithm
641 /// It runs augmenting phases by adding blocking flow until the
642 /// optimal solution is reached.
647 /// \brief Augments the flow with a blocking flow on a layered
650 /// This function builds a layered graph and then find a blocking
651 /// flow on this graph. The number of the levels in the layered
652 /// graph is strictly increasing in each augmenting phase
653 /// therefore the number of the augmentings is at most \f$ n-1
654 /// \f$. The length of each phase is at most \f$ O(m \log(n))
655 /// \f$, that the overall time complexity is \f$ O(nm \log(n)) \f$.
656 /// \return %False when there is not residual path between the
657 /// source and the target so the current flow is a feasible and
658 /// optimal solution.
662 if (createLayeredGraph()) {
667 n = _dt->findRoot(_source);
672 } else if (!advance(n)) {
679 n = _dt->findRoot(_source);
689 /// \brief runs the algorithm.
691 /// It is just a shorthand for:
704 /// \name Query Functions
705 /// The result of the Dinitz-Sleator-Tarjan algorithm can be
706 /// obtained using these functions.
708 /// Before the use of these functions,
709 /// either run() or start() must be called.
713 /// \brief Returns the value of the maximum flow.
715 /// Returns the value of the maximum flow by returning the excess
716 /// of the target node \c t. This value equals to the value of
717 /// the maximum flow already after the first phase.
718 Value flowValue() const {
723 /// \brief Returns the flow on the edge.
725 /// Sets the \c flowMap to the flow on the edges. This method can
726 /// be called after the second phase of algorithm.
727 Value flow(const Edge& edge) const {
728 return (*_flow)[edge];
731 /// \brief Returns true when the node is on the source side of minimum cut.
734 /// Returns true when the node is on the source side of minimum
735 /// cut. This method can be called both after running \ref
736 /// startFirstPhase() and \ref startSecondPhase().
737 bool minCut(const Node& node) const {
738 return (*_level)[node] == -2;
741 /// \brief Returns a minimum value cut.
743 /// Sets \c cut to the characteristic vector of a minimum value cut
744 /// It simply calls the minMinCut member.
745 /// \retval cut Write node bool map.
746 template <typename CutMap>
747 void minCutMap(CutMap& cutMap) const {
748 for (NodeIt n(_graph); n != INVALID; ++n) {
749 cutMap.set(n, (*_level)[n] == -2);
751 cutMap.set(_source, true);