diff -r 6706c788ebb5 -r a3fb216a267d src/lemon/preflow.h --- a/src/lemon/preflow.h Wed Mar 16 17:31:04 2005 +0000 +++ b/src/lemon/preflow.h Thu Mar 17 10:43:57 2005 +0000 @@ -37,12 +37,12 @@ ///This class provides an implementation of the \e preflow \e ///algorithm producing a flow of maximum value in a directed - ///graph. The preflow algorithms are the fastest max flow algorithms + ///graph. The preflow algorithms are the fastest known max flow algorithms ///up to now. The \e source node, the \e target node, the \e ///capacity of the edges and the \e starting \e flow value of the ///edges should be passed to the algorithm through the ///constructor. It is possible to change these quantities using the - ///functions \ref setSource, \ref setTarget, \ref setCap and \ref + ///functions \ref source, \ref target, \ref setCap and \ref ///setFlow. /// ///After running \ref lemon::Preflow::phase1() "phase1()" @@ -55,12 +55,12 @@ /// ///\param Graph The directed graph type the algorithm runs on. ///\param Num The number type of the capacities and the flow values. - ///\param CapMap The capacity map type. + ///\param CapacityMap The capacity map type. ///\param FlowMap The flow map type. /// ///\author Jacint Szabo template , + typename CapacityMap=typename Graph::template EdgeMap, typename FlowMap=typename Graph::template EdgeMap > class Preflow { protected: @@ -73,12 +73,12 @@ typedef typename Graph::template NodeMap NNMap; typedef typename std::vector VecNode; - const Graph* g; - Node s; - Node t; - const CapMap* capacity; - FlowMap* flow; - int n; //the number of nodes of G + const Graph* _g; + Node _source; + Node _target; + const CapacityMap* _capacity; + FlowMap* _flow; + int _node_num; //the number of nodes of G typename Graph::template NodeMap level; typename Graph::template NodeMap excess; @@ -91,7 +91,8 @@ ///Indicates the property of the starting flow map. - ///Indicates the property of the starting flow map. The meanings are as follows: + ///Indicates the property of the starting flow map. + ///The meanings are as follows: ///- \c ZERO_FLOW: constant zero flow ///- \c GEN_FLOW: any flow, i.e. the sum of the in-flows equals to ///the sum of the out-flows in every node except the \e source and @@ -111,8 +112,10 @@ ///Indicates the state of the preflow algorithm. - ///Indicates the state of the preflow algorithm. The meanings are as follows: - ///- \c AFTER_NOTHING: before running the algorithm or at an unspecified state. + ///Indicates the state of the preflow algorithm. + ///The meanings are as follows: + ///- \c AFTER_NOTHING: before running the algorithm or + /// at an unspecified state. ///- \c AFTER_PREFLOW_PHASE_1: right after running \c phase1 ///- \c AFTER_PREFLOW_PHASE_2: after running \ref phase2() /// @@ -133,15 +136,15 @@ ///\param _G The directed graph the algorithm runs on. ///\param _s The source node. ///\param _t The target node. - ///\param _capacity The capacity of the edges. - ///\param _flow The flow of the edges. + ///\param _cap The capacity of the edges. + ///\param _f The flow of the edges. ///Except the graph, all of these parameters can be reset by - ///calling \ref setSource, \ref setTarget, \ref setCap and \ref + ///calling \ref source, \ref target, \ref setCap and \ref ///setFlow, resp. - Preflow(const Graph& _G, Node _s, Node _t, - const CapMap& _capacity, FlowMap& _flow) : - g(&_G), s(_s), t(_t), capacity(&_capacity), - flow(&_flow), n(countNodes(_G)), level(_G), excess(_G,0), + Preflow(const Graph& _gr, Node _s, Node _t, + const CapacityMap& _cap, FlowMap& _f) : + _g(&_gr), _source(_s), _target(_t), _capacity(&_cap), + _flow(&_f), _node_num(countNodes(_gr)), level(_gr), excess(_gr,0), flow_prop(NO_FLOW), status(AFTER_NOTHING) { } @@ -204,8 +207,8 @@ ///give minimum value cuts unless calling \ref phase2(). void phase1() { - int heur0=(int)(H0*n); //time while running 'bound decrease' - int heur1=(int)(H1*n); //time while running 'highest label' + int heur0=(int)(H0*_node_num); //time while running 'bound decrease' + int heur1=(int)(H1*_node_num); //time while running 'highest label' int heur=heur1; //starting time interval (#of relabels) int numrelabel=0; @@ -216,15 +219,15 @@ //Needed for 'bound decrease', true means no active //nodes are above bound b. - int k=n-2; //bound on the highest level under n containing a node + int k=_node_num-2; //bound on the highest level under n containing a node int b=k; //bound on the highest level under n of an active node - VecNode first(n, INVALID); - NNMap next(*g, INVALID); + VecNode first(_node_num, INVALID); + NNMap next(*_g, INVALID); - NNMap left(*g, INVALID); - NNMap right(*g, INVALID); - VecNode level_list(n,INVALID); + NNMap left(*_g, INVALID); + NNMap right(*_g, INVALID); + VecNode level_list(_node_num,INVALID); //List of the nodes in level i bfs_queue; - bfs_queue.push(s); + bfs_queue.push(_source); while ( !bfs_queue.empty() ) { @@ -303,10 +307,10 @@ bfs_queue.pop(); int l=level[v]+1; - for(InEdgeIt e(*g,v); e!=INVALID; ++e) { - if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node u=g->source(e); - if ( level[u] >= n ) { + for(InEdgeIt e(*_g,v); e!=INVALID; ++e) { + if ( (*_capacity)[e] <= (*_flow)[e] ) continue; + Node u=_g->source(e); + if ( level[u] >= _node_num ) { bfs_queue.push(u); level.set(u, l); if ( excess[u] > 0 ) { @@ -316,10 +320,10 @@ } } - for(OutEdgeIt e(*g,v); e!=INVALID; ++e) { - if ( 0 >= (*flow)[e] ) continue; - Node u=g->target(e); - if ( level[u] >= n ) { + for(OutEdgeIt e(*_g,v); e!=INVALID; ++e) { + if ( 0 >= (*_flow)[e] ) continue; + Node u=_g->target(e); + if ( level[u] >= _node_num ) { bfs_queue.push(u); level.set(u, l); if ( excess[u] > 0 ) { @@ -329,7 +333,7 @@ } } } - b=n-2; + b=_node_num-2; while ( true ) { @@ -359,7 +363,7 @@ /// of the target node \c t. This value equals to the value of /// the maximum flow already after running \ref phase1. Num flowValue() const { - return excess[t]; + return excess[_target]; } @@ -375,8 +379,8 @@ void minCut(_CutMap& M) const { switch ( status ) { case AFTER_PREFLOW_PHASE_1: - for(NodeIt v(*g); v!=INVALID; ++v) { - if (level[v] < n) { + for(NodeIt v(*_g); v!=INVALID; ++v) { + if (level[v] < _node_num) { M.set(v, false); } else { M.set(v, true); @@ -402,24 +406,24 @@ void minMinCut(_CutMap& M) const { std::queue queue; - M.set(s,true); + M.set(_source,true); queue.push(s); while (!queue.empty()) { Node w=queue.front(); queue.pop(); - for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->target(e); - if (!M[v] && (*flow)[e] < (*capacity)[e] ) { + for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { + Node v=_g->target(e); + if (!M[v] && (*_flow)[e] < (*_capacity)[e] ) { queue.push(v); M.set(v, true); } } - for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->source(e); - if (!M[v] && (*flow)[e] > 0 ) { + for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { + Node v=_g->source(e); + if (!M[v] && (*_flow)[e] > 0 ) { queue.push(v); M.set(v, true); } @@ -436,28 +440,28 @@ template void maxMinCut(_CutMap& M) const { - for(NodeIt v(*g) ; v!=INVALID; ++v) M.set(v, true); + for(NodeIt v(*_g) ; v!=INVALID; ++v) M.set(v, true); std::queue queue; - M.set(t,false); - queue.push(t); + M.set(_target,false); + queue.push(_target); while (!queue.empty()) { Node w=queue.front(); queue.pop(); - for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->source(e); - if (M[v] && (*flow)[e] < (*capacity)[e] ) { + for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { + Node v=_g->source(e); + if (M[v] && (*_flow)[e] < (*_capacity)[e] ) { queue.push(v); M.set(v, false); } } - for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { - Node v=g->target(e); - if (M[v] && (*flow)[e] > 0 ) { + for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { + Node v=_g->target(e); + if (M[v] && (*_flow)[e] > 0 ) { queue.push(v); M.set(v, false); } @@ -469,41 +473,71 @@ ///Sets the source node to \c _s. /// - void setSource(Node _s) { - s=_s; + void source(Node _s) { + _source=_s; if ( flow_prop != ZERO_FLOW ) flow_prop=NO_FLOW; status=AFTER_NOTHING; } + ///Returns the source node. + + ///Returns the source node. + /// + Node source() const { + return _source; + } + ///Sets the target node to \c _t. ///Sets the target node to \c _t. /// - void setTarget(Node _t) { - t=_t; + void target(Node _t) { + _target=_t; if ( flow_prop == GEN_FLOW ) flow_prop=PRE_FLOW; status=AFTER_NOTHING; } + ///Returns the target node. + + ///Returns the target node. + /// + Node target() const { + return _target; + } + /// Sets the edge map of the capacities to _cap. /// Sets the edge map of the capacities to _cap. /// - void setCap(const CapMap& _cap) { - capacity=&_cap; + void capacityMap(const CapacityMap& _cap) { + _capacity=&_cap; status=AFTER_NOTHING; } + /// Returns a reference to to capacity map. + + /// Returns a reference to to capacity map. + /// + const CapacityMap &capacityMap() const { + return *_capacity; + } /// Sets the edge map of the flows to _flow. /// Sets the edge map of the flows to _flow. /// - void setFlow(FlowMap& _flow) { - flow=&_flow; + void flowMap(FlowMap& _f) { + _flow=&_f; flow_prop=NO_FLOW; status=AFTER_NOTHING; } + + /// Returns a reference to to flow map. + /// Returns a reference to to flow map. + /// + const FlowMap &flowMap() const { + return *_flow; + } private: @@ -511,32 +545,32 @@ int lev=level[w]; Num exc=excess[w]; - int newlevel=n; //bound on the next level of w + int newlevel=_node_num; //bound on the next level of w - for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { - if ( (*flow)[e] >= (*capacity)[e] ) continue; - Node v=g->target(e); + for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { + if ( (*_flow)[e] >= (*_capacity)[e] ) continue; + Node v=_g->target(e); if( lev > level[v] ) { //Push is allowed now - if ( excess[v]<=0 && v!=t && v!=s ) { + if ( excess[v]<=0 && v!=_target && v!=_source ) { next.set(v,first[level[v]]); first[level[v]]=v; } - Num cap=(*capacity)[e]; - Num flo=(*flow)[e]; + Num cap=(*_capacity)[e]; + Num flo=(*_flow)[e]; Num remcap=cap-flo; if ( remcap >= exc ) { //A nonsaturating push. - flow->set(e, flo+exc); + _flow->set(e, flo+exc); excess.set(v, excess[v]+exc); exc=0; break; } else { //A saturating push. - flow->set(e, cap); + _flow->set(e, cap); excess.set(v, excess[v]+remcap); exc-=remcap; } @@ -544,23 +578,23 @@ } //for out edges wv if ( exc > 0 ) { - for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { + for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { - if( (*flow)[e] <= 0 ) continue; - Node v=g->source(e); + if( (*_flow)[e] <= 0 ) continue; + Node v=_g->source(e); if( lev > level[v] ) { //Push is allowed now - if ( excess[v]<=0 && v!=t && v!=s ) { + if ( excess[v]<=0 && v!=_target && v!=_source ) { next.set(v,first[level[v]]); first[level[v]]=v; } - Num flo=(*flow)[e]; + Num flo=(*_flow)[e]; if ( flo >= exc ) { //A nonsaturating push. - flow->set(e, flo-exc); + _flow->set(e, flo-exc); excess.set(v, excess[v]+exc); exc=0; break; @@ -568,7 +602,7 @@ excess.set(v, excess[v]+flo); exc-=flo; - flow->set(e,0); + _flow->set(e,0); } } else if ( newlevel > level[v] ) newlevel = level[v]; } //for in edges vw @@ -585,14 +619,14 @@ void preflowPreproc(VecNode& first, NNMap& next, VecNode& level_list, NNMap& left, NNMap& right) { - for(NodeIt v(*g); v!=INVALID; ++v) level.set(v,n); + for(NodeIt v(*_g); v!=INVALID; ++v) level.set(v,_node_num); std::queue bfs_queue; if ( flow_prop == GEN_FLOW || flow_prop == PRE_FLOW ) { //Reverse_bfs from t in the residual graph, //to find the starting level. - level.set(t,0); - bfs_queue.push(t); + level.set(_target,0); + bfs_queue.push(_target); while ( !bfs_queue.empty() ) { @@ -600,10 +634,10 @@ bfs_queue.pop(); int l=level[v]+1; - for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { - if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node w=g->source(e); - if ( level[w] == n && w != s ) { + for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) { + if ( (*_capacity)[e] <= (*_flow)[e] ) continue; + Node w=_g->source(e); + if ( level[w] == _node_num && w != _source ) { bfs_queue.push(w); Node z=level_list[l]; if ( z!=INVALID ) left.set(z,w); @@ -613,10 +647,10 @@ } } - for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) { - if ( 0 >= (*flow)[e] ) continue; - Node w=g->target(e); - if ( level[w] == n && w != s ) { + for(OutEdgeIt e(*_g,v) ; e!=INVALID; ++e) { + if ( 0 >= (*_flow)[e] ) continue; + Node w=_g->target(e); + if ( level[w] == _node_num && w != _source ) { bfs_queue.push(w); Node z=level_list[l]; if ( z!=INVALID ) left.set(z,w); @@ -631,13 +665,13 @@ switch (flow_prop) { case NO_FLOW: - for(EdgeIt e(*g); e!=INVALID; ++e) flow->set(e,0); + for(EdgeIt e(*_g); e!=INVALID; ++e) _flow->set(e,0); case ZERO_FLOW: - for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0); + for(NodeIt v(*_g); v!=INVALID; ++v) excess.set(v,0); //Reverse_bfs from t, to find the starting level. - level.set(t,0); - bfs_queue.push(t); + level.set(_target,0); + bfs_queue.push(_target); while ( !bfs_queue.empty() ) { @@ -645,9 +679,9 @@ bfs_queue.pop(); int l=level[v]+1; - for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { - Node w=g->source(e); - if ( level[w] == n && w != s ) { + for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) { + Node w=_g->source(e); + if ( level[w] == _node_num && w != _source ) { bfs_queue.push(w); Node z=level_list[l]; if ( z!=INVALID ) left.set(z,w); @@ -659,84 +693,84 @@ } //the starting flow - for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { - Num c=(*capacity)[e]; + for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { + Num c=(*_capacity)[e]; if ( c <= 0 ) continue; - Node w=g->target(e); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) { //putting into the stack + Node w=_g->target(e); + if ( level[w] < _node_num ) { + if ( excess[w] <= 0 && w!=_target ) { //putting into the stack next.set(w,first[level[w]]); first[level[w]]=w; } - flow->set(e, c); + _flow->set(e, c); excess.set(w, excess[w]+c); } } break; case GEN_FLOW: - for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0); + for(NodeIt v(*_g); v!=INVALID; ++v) excess.set(v,0); { Num exc=0; - for(InEdgeIt e(*g,t) ; e!=INVALID; ++e) exc+=(*flow)[e]; - for(OutEdgeIt e(*g,t) ; e!=INVALID; ++e) exc-=(*flow)[e]; - excess.set(t,exc); + for(InEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc+=(*_flow)[e]; + for(OutEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc-=(*_flow)[e]; + excess.set(_target,exc); } //the starting flow - for(OutEdgeIt e(*g,s); e!=INVALID; ++e) { - Num rem=(*capacity)[e]-(*flow)[e]; + for(OutEdgeIt e(*_g,_source); e!=INVALID; ++e) { + Num rem=(*_capacity)[e]-(*_flow)[e]; if ( rem <= 0 ) continue; - Node w=g->target(e); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) { //putting into the stack + Node w=_g->target(e); + if ( level[w] < _node_num ) { + if ( excess[w] <= 0 && w!=_target ) { //putting into the stack next.set(w,first[level[w]]); first[level[w]]=w; } - flow->set(e, (*capacity)[e]); + _flow->set(e, (*_capacity)[e]); excess.set(w, excess[w]+rem); } } - for(InEdgeIt e(*g,s); e!=INVALID; ++e) { - if ( (*flow)[e] <= 0 ) continue; - Node w=g->source(e); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) { + for(InEdgeIt e(*_g,_source); e!=INVALID; ++e) { + if ( (*_flow)[e] <= 0 ) continue; + Node w=_g->source(e); + if ( level[w] < _node_num ) { + if ( excess[w] <= 0 && w!=_target ) { next.set(w,first[level[w]]); first[level[w]]=w; } - excess.set(w, excess[w]+(*flow)[e]); - flow->set(e, 0); + excess.set(w, excess[w]+(*_flow)[e]); + _flow->set(e, 0); } } break; case PRE_FLOW: //the starting flow - for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { - Num rem=(*capacity)[e]-(*flow)[e]; + for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { + Num rem=(*_capacity)[e]-(*_flow)[e]; if ( rem <= 0 ) continue; - Node w=g->target(e); - if ( level[w] < n ) flow->set(e, (*capacity)[e]); + Node w=_g->target(e); + if ( level[w] < _node_num ) _flow->set(e, (*_capacity)[e]); } - for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) { - if ( (*flow)[e] <= 0 ) continue; - Node w=g->source(e); - if ( level[w] < n ) flow->set(e, 0); + for(InEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { + if ( (*_flow)[e] <= 0 ) continue; + Node w=_g->source(e); + if ( level[w] < _node_num ) _flow->set(e, 0); } //computing the excess - for(NodeIt w(*g); w!=INVALID; ++w) { + for(NodeIt w(*_g); w!=INVALID; ++w) { Num exc=0; - for(InEdgeIt e(*g,w); e!=INVALID; ++e) exc+=(*flow)[e]; - for(OutEdgeIt e(*g,w); e!=INVALID; ++e) exc-=(*flow)[e]; + for(InEdgeIt e(*_g,w); e!=INVALID; ++e) exc+=(*_flow)[e]; + for(OutEdgeIt e(*_g,w); e!=INVALID; ++e) exc-=(*_flow)[e]; excess.set(w,exc); //putting the active nodes into the stack int lev=level[w]; - if ( exc > 0 && lev < n && Node(w) != t ) { + if ( exc > 0 && lev < _node_num && Node(w) != _target ) { next.set(w,first[lev]); first[lev]=w; } @@ -780,21 +814,21 @@ for (int i=lev; i!=k ; ) { Node v=level_list[++i]; while ( v!=INVALID ) { - level.set(v,n); + level.set(v,_node_num); v=right[v]; } level_list[i]=INVALID; if ( !what_heur ) first[i]=INVALID; } - level.set(w,n); + level.set(w,_node_num); b=lev-1; k=b; //gapping ends } else { - if ( newlevel == n ) level.set(w,n); + if ( newlevel == _node_num ) level.set(w,_node_num); else { level.set(w,++newlevel); next.set(w,first[newlevel]);