NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/preflow.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_PREFLOW_H
18 #define LEMON_PREFLOW_H
23 #include <lemon/error.h>
24 #include <lemon/invalid.h>
25 #include <lemon/maps.h>
26 #include <lemon/graph_utils.h>
30 /// \brief Implementation of the preflow algorithm.
35 ///\brief %Preflow algorithms class.
37 ///This class provides an implementation of the \e preflow \e
38 ///algorithm producing a flow of maximum value in a directed
39 ///graph. The preflow algorithms are the fastest known max flow algorithms
40 ///up to now. The \e source node, the \e target node, the \e
41 ///capacity of the edges and the \e starting \e flow value of the
42 ///edges should be passed to the algorithm through the
43 ///constructor. It is possible to change these quantities using the
44 ///functions \ref source, \ref target, \ref capacityMap and \ref
47 ///After running \ref lemon::Preflow::phase1() "phase1()"
48 ///or \ref lemon::Preflow::run() "run()", the maximal flow
49 ///value can be obtained by calling \ref flowValue(). The minimum
50 ///value cut can be written into a <tt>bool</tt> node map by
51 ///calling \ref minCut(). (\ref minMinCut() and \ref maxMinCut() writes
52 ///the inclusionwise minimum and maximum of the minimum value cuts,
55 ///\param Graph The directed graph type the algorithm runs on.
56 ///\param Num The number type of the capacities and the flow values.
57 ///\param CapacityMap The capacity map type.
58 ///\param FlowMap The flow map type.
60 ///\author Jacint Szabo
61 ///\todo Second template parameter is superfluous
62 template <typename Graph, typename Num,
63 typename CapacityMap=typename Graph::template EdgeMap<Num>,
64 typename FlowMap=typename Graph::template EdgeMap<Num> >
67 typedef typename Graph::Node Node;
68 typedef typename Graph::NodeIt NodeIt;
69 typedef typename Graph::EdgeIt EdgeIt;
70 typedef typename Graph::OutEdgeIt OutEdgeIt;
71 typedef typename Graph::InEdgeIt InEdgeIt;
73 typedef typename Graph::template NodeMap<Node> NNMap;
74 typedef typename std::vector<Node> VecNode;
79 const CapacityMap* _capacity;
81 int _node_num; //the number of nodes of G
83 typename Graph::template NodeMap<int> level;
84 typename Graph::template NodeMap<Num> excess;
86 // constants used for heuristics
87 static const int H0=20;
88 static const int H1=1;
92 ///\ref Exception for the case when s=t.
94 ///\ref Exception for the case when the source equals the target.
95 class InvalidArgument : public lemon::LogicError {
97 virtual const char* exceptionName() const {
98 return "lemon::Preflow::InvalidArgument";
103 ///Indicates the property of the starting flow map.
105 ///Indicates the property of the starting flow map.
106 ///The meanings are as follows:
107 ///- \c ZERO_FLOW: constant zero flow
108 ///- \c GEN_FLOW: any flow, i.e. the sum of the in-flows equals to
109 ///the sum of the out-flows in every node except the \e source and
111 ///- \c PRE_FLOW: any preflow, i.e. the sum of the in-flows is at
112 ///least the sum of the out-flows in every node except the \e source.
113 ///- \c NO_FLOW: indicates an unspecified edge map. \c flow will be
114 ///set to the constant zero flow in the beginning of
115 ///the algorithm in this case.
124 ///Indicates the state of the preflow algorithm.
126 ///Indicates the state of the preflow algorithm.
127 ///The meanings are as follows:
128 ///- \c AFTER_NOTHING: before running the algorithm or
129 /// at an unspecified state.
130 ///- \c AFTER_PREFLOW_PHASE_1: right after running \c phase1
131 ///- \c AFTER_PREFLOW_PHASE_2: after running \ref phase2()
135 AFTER_PREFLOW_PHASE_1,
136 AFTER_PREFLOW_PHASE_2
141 StatusEnum status; // Do not needle this flag only if necessary.
144 ///The constructor of the class.
146 ///The constructor of the class.
147 ///\param _gr The directed graph the algorithm runs on.
148 ///\param _s The source node.
149 ///\param _t The target node.
150 ///\param _cap The capacity of the edges.
151 ///\param _f The flow of the edges.
152 ///Except the graph, all of these parameters can be reset by
153 ///calling \ref source, \ref target, \ref capacityMap and \ref
155 Preflow(const Graph& _gr, Node _s, Node _t,
156 const CapacityMap& _cap, FlowMap& _f) :
157 _g(&_gr), _source(_s), _target(_t), _capacity(&_cap),
158 _flow(&_f), _node_num(countNodes(_gr)), level(_gr), excess(_gr,0),
159 flow_prop(NO_FLOW), status(AFTER_NOTHING) {
160 if ( _source==_target )
161 throw InvalidArgument();
166 ///Runs the preflow algorithm.
168 ///Runs the preflow algorithm.
175 ///Runs the preflow algorithm.
177 ///Runs the preflow algorithm.
178 ///\pre The starting flow map must be
179 /// - a constant zero flow if \c fp is \c ZERO_FLOW,
180 /// - an arbitrary flow if \c fp is \c GEN_FLOW,
181 /// - an arbitrary preflow if \c fp is \c PRE_FLOW,
182 /// - any map if \c fp is NO_FLOW.
183 ///If the starting flow map is a flow or a preflow then
184 ///the algorithm terminates faster.
185 void run(FlowEnum fp) {
190 ///Runs the first phase of the preflow algorithm.
192 ///The preflow algorithm consists of two phases, this method runs
193 ///the first phase. After the first phase the maximum flow value
194 ///and a minimum value cut can already be computed, although a
195 ///maximum flow is not yet obtained. So after calling this method
196 ///\ref flowValue returns the value of a maximum flow and \ref
197 ///minCut returns a minimum cut.
198 ///\warning \ref minMinCut and \ref maxMinCut do not give minimum
199 ///value cuts unless calling \ref phase2.
200 ///\pre The starting flow must be
201 ///- a constant zero flow if \c fp is \c ZERO_FLOW,
202 ///- an arbitary flow if \c fp is \c GEN_FLOW,
203 ///- an arbitary preflow if \c fp is \c PRE_FLOW,
204 ///- any map if \c fp is NO_FLOW.
205 void phase1(FlowEnum fp)
212 ///Runs the first phase of the preflow algorithm.
214 ///The preflow algorithm consists of two phases, this method runs
215 ///the first phase. After the first phase the maximum flow value
216 ///and a minimum value cut can already be computed, although a
217 ///maximum flow is not yet obtained. So after calling this method
218 ///\ref flowValue returns the value of a maximum flow and \ref
219 ///minCut returns a minimum cut.
220 ///\warning \ref minMinCut() and \ref maxMinCut() do not
221 ///give minimum value cuts unless calling \ref phase2().
224 int heur0=(int)(H0*_node_num); //time while running 'bound decrease'
225 int heur1=(int)(H1*_node_num); //time while running 'highest label'
226 int heur=heur1; //starting time interval (#of relabels)
230 //It is 0 in case 'bound decrease' and 1 in case 'highest label'
233 //Needed for 'bound decrease', true means no active
234 //nodes are above bound b.
236 int k=_node_num-2; //bound on the highest level under n containing a node
237 int b=k; //bound on the highest level under n of an active node
239 VecNode first(_node_num, INVALID);
240 NNMap next(*_g, INVALID);
242 NNMap left(*_g, INVALID);
243 NNMap right(*_g, INVALID);
244 VecNode level_list(_node_num,INVALID);
245 //List of the nodes in level i<n, set to n.
247 preflowPreproc(first, next, level_list, left, right);
249 //Push/relabel on the highest level active nodes.
252 if ( !what_heur && !end && k > 0 ) {
258 if ( first[b]==INVALID ) --b;
263 int newlevel=push(w, next, first);
264 if ( excess[w] > 0 ) relabel(w, newlevel, first, next, level_list,
265 left, right, b, k, what_heur);
268 if ( numrelabel >= heur ) {
283 status=AFTER_PREFLOW_PHASE_1;
288 // list 'level_list' on the nodes on level i implemented by hand
289 // stack 'active' on the active nodes on level i
290 // runs heuristic 'highest label' for H1*n relabels
291 // runs heuristic 'bound decrease' for H0*n relabels,
292 // starts with 'highest label'
293 // Parameters H0 and H1 are initialized to 20 and 1.
296 ///Runs the second phase of the preflow algorithm.
298 ///The preflow algorithm consists of two phases, this method runs
299 ///the second phase. After calling \ref phase1() and then
301 /// \ref flowMap() return a maximum flow, \ref flowValue
302 ///returns the value of a maximum flow, \ref minCut returns a
303 ///minimum cut, while the methods \ref minMinCut and \ref
304 ///maxMinCut return the inclusionwise minimum and maximum cuts of
305 ///minimum value, resp. \pre \ref phase1 must be called before.
309 int k=_node_num-2; //bound on the highest level under n containing a node
310 int b=k; //bound on the highest level under n of an active node
313 VecNode first(_node_num, INVALID);
314 NNMap next(*_g, INVALID);
315 level.set(_source,0);
316 std::queue<Node> bfs_queue;
317 bfs_queue.push(_source);
319 while ( !bfs_queue.empty() ) {
321 Node v=bfs_queue.front();
325 for(InEdgeIt e(*_g,v); e!=INVALID; ++e) {
326 if ( (*_capacity)[e] <= (*_flow)[e] ) continue;
327 Node u=_g->source(e);
328 if ( level[u] >= _node_num ) {
331 if ( excess[u] > 0 ) {
332 next.set(u,first[l]);
338 for(OutEdgeIt e(*_g,v); e!=INVALID; ++e) {
339 if ( 0 >= (*_flow)[e] ) continue;
340 Node u=_g->target(e);
341 if ( level[u] >= _node_num ) {
344 if ( excess[u] > 0 ) {
345 next.set(u,first[l]);
356 if ( first[b]==INVALID ) --b;
360 int newlevel=push(w,next, first);
363 if ( excess[w] > 0 ) {
364 level.set(w,++newlevel);
365 next.set(w,first[newlevel]);
372 status=AFTER_PREFLOW_PHASE_2;
375 /// Returns the value of the maximum flow.
377 /// Returns the value of the maximum flow by returning the excess
378 /// of the target node \c t. This value equals to the value of
379 /// the maximum flow already after running \ref phase1.
380 Num flowValue() const {
381 return excess[_target];
385 ///Returns a minimum value cut.
387 ///Sets \c M to the characteristic vector of a minimum value
388 ///cut. This method can be called both after running \ref
389 ///phase1 and \ref phase2. It is much faster after
390 ///\ref phase1. \pre M should be a bool-valued node-map. \pre
391 ///If \ref minCut() is called after \ref phase2() then M should
392 ///be initialized to false.
393 template<typename _CutMap>
394 void minCut(_CutMap& M) const {
396 case AFTER_PREFLOW_PHASE_1:
397 for(NodeIt v(*_g); v!=INVALID; ++v) {
398 if (level[v] < _node_num) {
405 case AFTER_PREFLOW_PHASE_2:
413 ///Returns the inclusionwise minimum of the minimum value cuts.
415 ///Sets \c M to the characteristic vector of the minimum value cut
416 ///which is inclusionwise minimum. It is computed by processing a
417 ///bfs from the source node \c s in the residual graph. \pre M
418 ///should be a node map of bools initialized to false. \pre \ref
419 ///phase2 should already be run.
420 template<typename _CutMap>
421 void minMinCut(_CutMap& M) const {
423 std::queue<Node> queue;
427 while (!queue.empty()) {
428 Node w=queue.front();
431 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
432 Node v=_g->target(e);
433 if (!M[v] && (*_flow)[e] < (*_capacity)[e] ) {
439 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
440 Node v=_g->source(e);
441 if (!M[v] && (*_flow)[e] > 0 ) {
449 ///Returns the inclusionwise maximum of the minimum value cuts.
451 ///Sets \c M to the characteristic vector of the minimum value cut
452 ///which is inclusionwise maximum. It is computed by processing a
453 ///backward bfs from the target node \c t in the residual graph.
454 ///\pre \ref phase2() or run() should already be run.
455 template<typename _CutMap>
456 void maxMinCut(_CutMap& M) const {
458 for(NodeIt v(*_g) ; v!=INVALID; ++v) M.set(v, true);
460 std::queue<Node> queue;
462 M.set(_target,false);
465 while (!queue.empty()) {
466 Node w=queue.front();
469 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
470 Node v=_g->source(e);
471 if (M[v] && (*_flow)[e] < (*_capacity)[e] ) {
477 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
478 Node v=_g->target(e);
479 if (M[v] && (*_flow)[e] > 0 ) {
487 ///Sets the source node to \c _s.
489 ///Sets the source node to \c _s.
491 void source(Node _s) {
493 if ( flow_prop != ZERO_FLOW ) flow_prop=NO_FLOW;
494 status=AFTER_NOTHING;
497 ///Returns the source node.
499 ///Returns the source node.
501 Node source() const {
505 ///Sets the target node to \c _t.
507 ///Sets the target node to \c _t.
509 void target(Node _t) {
511 if ( flow_prop == GEN_FLOW ) flow_prop=PRE_FLOW;
512 status=AFTER_NOTHING;
515 ///Returns the target node.
517 ///Returns the target node.
519 Node target() const {
523 /// Sets the edge map of the capacities to _cap.
525 /// Sets the edge map of the capacities to _cap.
527 void capacityMap(const CapacityMap& _cap) {
529 status=AFTER_NOTHING;
531 /// Returns a reference to capacity map.
533 /// Returns a reference to capacity map.
535 const CapacityMap &capacityMap() const {
539 /// Sets the edge map of the flows to _flow.
541 /// Sets the edge map of the flows to _flow.
543 void flowMap(FlowMap& _f) {
546 status=AFTER_NOTHING;
549 /// Returns a reference to flow map.
551 /// Returns a reference to flow map.
553 const FlowMap &flowMap() const {
559 int push(Node w, NNMap& next, VecNode& first) {
563 int newlevel=_node_num; //bound on the next level of w
565 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
566 if ( (*_flow)[e] >= (*_capacity)[e] ) continue;
567 Node v=_g->target(e);
569 if( lev > level[v] ) { //Push is allowed now
571 if ( excess[v]<=0 && v!=_target && v!=_source ) {
572 next.set(v,first[level[v]]);
576 Num cap=(*_capacity)[e];
580 if ( remcap >= exc ) { //A nonsaturating push.
582 _flow->set(e, flo+exc);
583 excess.set(v, excess[v]+exc);
587 } else { //A saturating push.
589 excess.set(v, excess[v]+remcap);
592 } else if ( newlevel > level[v] ) newlevel = level[v];
596 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
598 if( (*_flow)[e] <= 0 ) continue;
599 Node v=_g->source(e);
601 if( lev > level[v] ) { //Push is allowed now
603 if ( excess[v]<=0 && v!=_target && v!=_source ) {
604 next.set(v,first[level[v]]);
610 if ( flo >= exc ) { //A nonsaturating push.
612 _flow->set(e, flo-exc);
613 excess.set(v, excess[v]+exc);
616 } else { //A saturating push.
618 excess.set(v, excess[v]+flo);
622 } else if ( newlevel > level[v] ) newlevel = level[v];
625 } // if w still has excess after the out edge for cycle
634 void preflowPreproc(VecNode& first, NNMap& next,
635 VecNode& level_list, NNMap& left, NNMap& right)
637 for(NodeIt v(*_g); v!=INVALID; ++v) level.set(v,_node_num);
638 std::queue<Node> bfs_queue;
640 if ( flow_prop == GEN_FLOW || flow_prop == PRE_FLOW ) {
641 //Reverse_bfs from t in the residual graph,
642 //to find the starting level.
643 level.set(_target,0);
644 bfs_queue.push(_target);
646 while ( !bfs_queue.empty() ) {
648 Node v=bfs_queue.front();
652 for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
653 if ( (*_capacity)[e] <= (*_flow)[e] ) continue;
654 Node w=_g->source(e);
655 if ( level[w] == _node_num && w != _source ) {
657 Node z=level_list[l];
658 if ( z!=INVALID ) left.set(z,w);
665 for(OutEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
666 if ( 0 >= (*_flow)[e] ) continue;
667 Node w=_g->target(e);
668 if ( level[w] == _node_num && w != _source ) {
670 Node z=level_list[l];
671 if ( z!=INVALID ) left.set(z,w);
683 for(EdgeIt e(*_g); e!=INVALID; ++e) _flow->set(e,0);
685 for(NodeIt v(*_g); v!=INVALID; ++v) excess.set(v,0);
687 //Reverse_bfs from t, to find the starting level.
688 level.set(_target,0);
689 bfs_queue.push(_target);
691 while ( !bfs_queue.empty() ) {
693 Node v=bfs_queue.front();
697 for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
698 Node w=_g->source(e);
699 if ( level[w] == _node_num && w != _source ) {
701 Node z=level_list[l];
702 if ( z!=INVALID ) left.set(z,w);
711 for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
712 Num c=(*_capacity)[e];
713 if ( c <= 0 ) continue;
714 Node w=_g->target(e);
715 if ( level[w] < _node_num ) {
716 if ( excess[w] <= 0 && w!=_target ) { //putting into the stack
717 next.set(w,first[level[w]]);
721 excess.set(w, excess[w]+c);
727 for(NodeIt v(*_g); v!=INVALID; ++v) excess.set(v,0);
730 for(InEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc+=(*_flow)[e];
731 for(OutEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc-=(*_flow)[e];
732 excess.set(_target,exc);
736 for(OutEdgeIt e(*_g,_source); e!=INVALID; ++e) {
737 Num rem=(*_capacity)[e]-(*_flow)[e];
738 if ( rem <= 0 ) continue;
739 Node w=_g->target(e);
740 if ( level[w] < _node_num ) {
741 if ( excess[w] <= 0 && w!=_target ) { //putting into the stack
742 next.set(w,first[level[w]]);
745 _flow->set(e, (*_capacity)[e]);
746 excess.set(w, excess[w]+rem);
750 for(InEdgeIt e(*_g,_source); e!=INVALID; ++e) {
751 if ( (*_flow)[e] <= 0 ) continue;
752 Node w=_g->source(e);
753 if ( level[w] < _node_num ) {
754 if ( excess[w] <= 0 && w!=_target ) {
755 next.set(w,first[level[w]]);
758 excess.set(w, excess[w]+(*_flow)[e]);
766 for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
767 Num rem=(*_capacity)[e]-(*_flow)[e];
768 if ( rem <= 0 ) continue;
769 Node w=_g->target(e);
770 if ( level[w] < _node_num ) _flow->set(e, (*_capacity)[e]);
773 for(InEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
774 if ( (*_flow)[e] <= 0 ) continue;
775 Node w=_g->source(e);
776 if ( level[w] < _node_num ) _flow->set(e, 0);
779 //computing the excess
780 for(NodeIt w(*_g); w!=INVALID; ++w) {
782 for(InEdgeIt e(*_g,w); e!=INVALID; ++e) exc+=(*_flow)[e];
783 for(OutEdgeIt e(*_g,w); e!=INVALID; ++e) exc-=(*_flow)[e];
786 //putting the active nodes into the stack
788 if ( exc > 0 && lev < _node_num && Node(w) != _target ) {
789 next.set(w,first[lev]);
798 void relabel(Node w, int newlevel, VecNode& first, NNMap& next,
799 VecNode& level_list, NNMap& left,
800 NNMap& right, int& b, int& k, bool what_heur )
805 Node right_n=right[w];
809 if ( right_n!=INVALID ) {
810 if ( left_n!=INVALID ) {
811 right.set(left_n, right_n);
812 left.set(right_n, left_n);
814 level_list[lev]=right_n;
815 left.set(right_n, INVALID);
818 if ( left_n!=INVALID ) {
819 right.set(left_n, INVALID);
821 level_list[lev]=INVALID;
826 if ( level_list[lev]==INVALID ) {
829 for (int i=lev; i!=k ; ) {
830 Node v=level_list[++i];
831 while ( v!=INVALID ) {
832 level.set(v,_node_num);
835 level_list[i]=INVALID;
836 if ( !what_heur ) first[i]=INVALID;
839 level.set(w,_node_num);
846 if ( newlevel == _node_num ) level.set(w,_node_num);
848 level.set(w,++newlevel);
849 next.set(w,first[newlevel]);
851 if ( what_heur ) b=newlevel;
852 if ( k < newlevel ) ++k; //now k=newlevel
853 Node z=level_list[newlevel];
854 if ( z!=INVALID ) left.set(z,w);
857 level_list[newlevel]=w;
865 ///\brief Function type interface for Preflow algorithm.
867 ///Function type interface for Preflow algorithm.
869 template<class GR, class CM, class FM>
870 Preflow<GR,typename CM::Value,CM,FM> preflow(const GR &g,
871 typename GR::Node source,
872 typename GR::Node target,
877 return Preflow<GR,typename CM::Value,CM,FM>(g,source,target,cap,flow);
882 #endif //LEMON_PREFLOW_H