# HG changeset patch # User alpar # Date 1090505963 0 # Node ID 835ebe1b3250572ab331c463171bbe1533a08cad # Parent 9fa4045571cdd6180c85f1c9746ff9581b082062 max_flow.h (wich doesn't use STL - max_flow.h (which doesn't use STL stack) moved to /src/hugo - for_each_macros.h was removed from max_flow.h - (blocking) flow augmenting stuffs was removed. diff -r 9fa4045571cd -r 835ebe1b3250 src/hugo/max_flow.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/max_flow.h Thu Jul 22 14:19:23 2004 +0000 @@ -0,0 +1,892 @@ +// -*- C++ -*- +#ifndef HUGO_MAX_FLOW_NO_STACK_H +#define HUGO_MAX_FLOW_NO_STACK_H + +#include +#include +//#include + +#include +#include +#include + +/// \file +/// \brief The same as max_flow.h, but without using stl stack for the active nodes. Only for test. +/// \ingroup galgs + +namespace hugo { + + /// \addtogroup galgs + /// @{ + ///Maximum flow algorithms class. + + ///This class provides various algorithms for finding a flow of + ///maximum value in a directed graph. 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 resetSource, \ref resetTarget, \ref resetCap and + ///\ref resetFlow. Before any subsequent runs of any algorithm of + ///the class \ref resetFlow should be called. + + ///After running an algorithm of the class, the actual flow value + ///can be obtained by calling \ref flowValue(). The minimum + ///value cut can be written into a \c node map of \c bools by + ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes + ///the inclusionwise minimum and maximum of the minimum value + ///cuts, resp.) + ///\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 FlowMap The flow map type. + ///\author Marton Makai, Jacint Szabo + template , + typename FlowMap=typename Graph::template EdgeMap > + class MaxFlow { + protected: + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::OutEdgeIt OutEdgeIt; + typedef typename Graph::InEdgeIt InEdgeIt; + + // typedef typename std::vector > VecStack; + typedef typename std::vector VecFirst; + 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 + typedef ResGraphWrapper ResGW; + //typedef ExpResGraphWrapper ResGW; + typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; + typedef typename ResGW::Edge ResGWEdge; + //typedef typename ResGW::template NodeMap ReachedMap; + typedef typename Graph::template NodeMap ReachedMap; + + + //level works as a bool map in augmenting path algorithms and is + //used by bfs for storing reached information. In preflow, it + //shows the levels of nodes. + ReachedMap level; + + //excess is needed only in preflow + typename Graph::template NodeMap excess; + + // constants used for heuristics + static const int H0=20; + static const int H1=1; + + public: + + ///Indicates the property of the starting flow. + + ///Indicates the property of the starting flow. 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 + ///the \e target. + ///- \c PRE_FLOW: any preflow, i.e. the sum of the in-flows is at + ///least the sum of the out-flows in every node except the \e source. + ///- \c NO_FLOW: indicates an unspecified edge map. \ref flow will be + ///set to the constant zero flow in the beginning of the algorithm in this case. + enum FlowEnum{ + ZERO_FLOW, + GEN_FLOW, + PRE_FLOW, + NO_FLOW + }; + + enum StatusEnum { + AFTER_NOTHING, + AFTER_AUGMENTING, + AFTER_FAST_AUGMENTING, + AFTER_PRE_FLOW_PHASE_1, + AFTER_PRE_FLOW_PHASE_2 + }; + + /// Don not needle this flag only if necessary. + StatusEnum status; + +// int number_of_augmentations; + + +// template +// class TrickyReachedMap { +// protected: +// IntMap* map; +// int* number_of_augmentations; +// public: +// TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) : +// map(&_map), number_of_augmentations(&_number_of_augmentations) { } +// void set(const Node& n, bool b) { +// if (b) +// map->set(n, *number_of_augmentations); +// else +// map->set(n, *number_of_augmentations-1); +// } +// bool operator[](const Node& n) const { +// return (*map)[n]==*number_of_augmentations; +// } +// }; + + ///Constructor + + ///\todo Document, please. + /// + MaxFlow(const Graph& _G, Node _s, Node _t, + const CapMap& _capacity, FlowMap& _flow) : + g(&_G), s(_s), t(_t), capacity(&_capacity), + flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0), + status(AFTER_NOTHING) { } + + ///Runs a maximum flow algorithm. + + ///Runs a preflow algorithm, which is the fastest maximum flow + ///algorithm up-to-date. The default for \c fe is ZERO_FLOW. + ///\pre The starting flow must be + /// - a constant zero flow if \c fe is \c ZERO_FLOW, + /// - an arbitary flow if \c fe is \c GEN_FLOW, + /// - an arbitary preflow if \c fe is \c PRE_FLOW, + /// - any map if \c fe is NO_FLOW. + void run(FlowEnum fe=ZERO_FLOW) { + preflow(fe); + } + + + ///Runs a preflow algorithm. + + ///Runs a preflow algorithm. The preflow algorithms provide the + ///fastest way to compute a maximum flow in a directed graph. + ///\pre The starting flow must be + /// - a constant zero flow if \c fe is \c ZERO_FLOW, + /// - an arbitary flow if \c fe is \c GEN_FLOW, + /// - an arbitary preflow if \c fe is \c PRE_FLOW, + /// - any map if \c fe is NO_FLOW. + /// + ///\todo NO_FLOW should be the default flow. + void preflow(FlowEnum fe) { + preflowPhase1(fe); + preflowPhase2(); + } + // Heuristics: + // 2 phase + // gap + // list 'level_list' on the nodes on level i implemented by hand + // stack 'active' on the active nodes on level i + // runs heuristic 'highest label' for H1*n relabels + // runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label' + // Parameters H0 and H1 are initialized to 20 and 1. + + ///Runs the first phase of the preflow algorithm. + + ///The preflow algorithm consists of two phases, this method runs the + ///first phase. After the first phase the maximum flow value and a + ///minimum value cut can already be computed, though a maximum flow + ///is net yet obtained. So after calling this method \ref flowValue + ///and \ref actMinCut gives proper results. + ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not + ///give minimum value cuts unless calling \ref preflowPhase2. + ///\pre The starting flow must be + /// - a constant zero flow if \c fe is \c ZERO_FLOW, + /// - an arbitary flow if \c fe is \c GEN_FLOW, + /// - an arbitary preflow if \c fe is \c PRE_FLOW, + /// - any map if \c fe is NO_FLOW. + void preflowPhase1(FlowEnum fe) + { + + int heur0=(int)(H0*n); //time while running 'bound decrease' + int heur1=(int)(H1*n); //time while running 'highest label' + int heur=heur1; //starting time interval (#of relabels) + int numrelabel=0; + + bool what_heur=1; + //It is 0 in case 'bound decrease' and 1 in case 'highest label' + + bool end=false; + //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 b=k; //bound on the highest level under n of an active node + + VecFirst first(n, INVALID); + NNMap next(*g, INVALID); //maybe INVALID is not needed + // VecStack active(n); + + NNMap left(*g, INVALID); + NNMap right(*g, INVALID); + VecNode level_list(n,INVALID); + //List of the nodes in level ifirst(v); g->valid(v); g->next(v)) level.set(v,n); + //setting each node to level n + + if ( fe == NO_FLOW ) { + EdgeIt e; + for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0); + } + + switch (fe) { //computing the excess + case PRE_FLOW: + { + NodeIt v; + for(g->first(v); g->valid(v); g->next(v)) { + Num exc=0; + + InEdgeIt e; + for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e]; + OutEdgeIt f; + for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f]; + + excess.set(v,exc); + + //putting the active nodes into the stack + int lev=level[v]; + if ( exc > 0 && lev < n && v != t ) + { + next.set(v,first[lev]); + first[lev]=v; + } + // active[lev].push(v); + } + break; + } + case GEN_FLOW: + { + NodeIt v; + for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0); + + Num exc=0; + InEdgeIt e; + for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e]; + OutEdgeIt f; + for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f]; + excess.set(t,exc); + break; + } + case ZERO_FLOW: + case NO_FLOW: + { + NodeIt v; + for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0); + break; + } + } + + preflowPreproc(fe, next, first,/*active*/ level_list, left, right); + //End of preprocessing + + + //Push/relabel on the highest level active nodes. + while ( true ) { + if ( b == 0 ) { + if ( !what_heur && !end && k > 0 ) { + b=k; + end=true; + } else break; + } + + if ( !g->valid(first[b])/*active[b].empty()*/ ) --b; + else { + end=false; + Node w=first[b]; + first[b]=next[w]; + /* Node w=active[b].top(); + active[b].pop();*/ + int newlevel=push(w,/*active*/next, first); + if ( excess[w] > 0 ) relabel(w, newlevel, /*active*/next, first, level_list, + left, right, b, k, what_heur); + + ++numrelabel; + if ( numrelabel >= heur ) { + numrelabel=0; + if ( what_heur ) { + what_heur=0; + heur=heur0; + end=false; + } else { + what_heur=1; + heur=heur1; + b=k; + } + } + } + } + + status=AFTER_PRE_FLOW_PHASE_1; + } + + + ///Runs the second phase of the preflow algorithm. + + ///The preflow algorithm consists of two phases, this method runs + ///the second phase. After calling \ref preflowPhase1 and then + ///\ref preflowPhase2 the methods \ref flowValue, \ref minCut, + ///\ref minMinCut and \ref maxMinCut give proper results. + ///\pre \ref preflowPhase1 must be called before. + void preflowPhase2() + { + + int k=n-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 + + + VecFirst first(n, INVALID); + NNMap next(*g, INVALID); //maybe INVALID is not needed + // VecStack active(n); + level.set(s,0); + std::queue bfs_queue; + bfs_queue.push(s); + + while (!bfs_queue.empty()) { + + Node v=bfs_queue.front(); + bfs_queue.pop(); + int l=level[v]+1; + + InEdgeIt e; + for(g->first(e,v); g->valid(e); g->next(e)) { + if ( (*capacity)[e] <= (*flow)[e] ) continue; + Node u=g->tail(e); + if ( level[u] >= n ) { + bfs_queue.push(u); + level.set(u, l); + if ( excess[u] > 0 ) { + next.set(u,first[l]); + first[l]=u; + //active[l].push(u); + } + } + } + + OutEdgeIt f; + for(g->first(f,v); g->valid(f); g->next(f)) { + if ( 0 >= (*flow)[f] ) continue; + Node u=g->head(f); + if ( level[u] >= n ) { + bfs_queue.push(u); + level.set(u, l); + if ( excess[u] > 0 ) { + next.set(u,first[l]); + first[l]=u; + //active[l].push(u); + } + } + } + } + b=n-2; + + while ( true ) { + + if ( b == 0 ) break; + + if ( !g->valid(first[b])/*active[b].empty()*/ ) --b; + else { + + Node w=first[b]; + first[b]=next[w]; + /* Node w=active[b].top(); + active[b].pop();*/ + int newlevel=push(w,next, first/*active*/); + + //relabel + if ( excess[w] > 0 ) { + level.set(w,++newlevel); + next.set(w,first[newlevel]); + first[newlevel]=w; + //active[newlevel].push(w); + b=newlevel; + } + } // if stack[b] is nonempty + } // while(true) + + status=AFTER_PRE_FLOW_PHASE_2; + } + + + /// Returns the maximum value of a flow. + + /// Returns the maximum value of a flow, by counting the + /// over-flow of the target node \ref t. + /// It can be called already after running \ref preflowPhase1. + Num flowValue() const { + Num a=0; + for(InEdgeIt e(*g,t);g->valid(e);G.next(e)) a+=(*flow)[e]; + for(OutEdgeIt e(*g,t);g->valid(e);G.next(e)) a-=(*flow)[e]; + + //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan + } + + ///Returns a minimum value cut after calling \ref preflowPhase1. + + ///After the first phase of the preflow algorithm the maximum flow + ///value and a minimum value cut can already be computed. This + ///method can be called after running \ref preflowPhase1 for + ///obtaining a minimum value cut. + /// \warning Gives proper result only right after calling \ref + /// preflowPhase1. + /// \todo We have to make some status variable which shows the + /// actual state + /// of the class. This enables us to determine which methods are valid + /// for MinCut computation + template + void actMinCut(_CutMap& M) const { + NodeIt v; + switch (status) { + case AFTER_PRE_FLOW_PHASE_1: + for(g->first(v); g->valid(v); g->next(v)) { + if (level[v] < n) { + M.set(v, false); + } else { + M.set(v, true); + } + } + break; + case AFTER_PRE_FLOW_PHASE_2: + case AFTER_NOTHING: + minMinCut(M); + break; + case AFTER_AUGMENTING: + for(g->first(v); g->valid(v); g->next(v)) { + if (level[v]) { + M.set(v, true); + } else { + M.set(v, false); + } + } + break; + case AFTER_FAST_AUGMENTING: + for(g->first(v); g->valid(v); g->next(v)) { + if (level[v]==number_of_augmentations) { + M.set(v, true); + } else { + M.set(v, false); + } + } + break; + } + } + + ///Returns the inclusionwise minimum of the minimum value cuts. + + ///Sets \c M to the characteristic vector of the minimum value cut + ///which is inclusionwise minimum. It is computed by processing + ///a bfs from the source node \c s in the residual graph. + ///\pre M should be a node map of bools initialized to false. + ///\pre \c flow must be a maximum flow. + template + void minMinCut(_CutMap& M) const { + std::queue queue; + + M.set(s,true); + queue.push(s); + + while (!queue.empty()) { + Node w=queue.front(); + queue.pop(); + + OutEdgeIt e; + for(g->first(e,w) ; g->valid(e); g->next(e)) { + Node v=g->head(e); + if (!M[v] && (*flow)[e] < (*capacity)[e] ) { + queue.push(v); + M.set(v, true); + } + } + + InEdgeIt f; + for(g->first(f,w) ; g->valid(f); g->next(f)) { + Node v=g->tail(f); + if (!M[v] && (*flow)[f] > 0 ) { + queue.push(v); + M.set(v, true); + } + } + } + } + + ///Returns the inclusionwise maximum of the minimum value cuts. + + ///Sets \c M to the characteristic vector of the minimum value cut + ///which is inclusionwise maximum. It is computed by processing a + ///backward bfs from the target node \c t in the residual graph. + ///\pre M should be a node map of bools initialized to false. + ///\pre \c flow must be a maximum flow. + template + void maxMinCut(_CutMap& M) const { + + NodeIt v; + for(g->first(v) ; g->valid(v); g->next(v)) { + M.set(v, true); + } + + std::queue queue; + + M.set(t,false); + queue.push(t); + + while (!queue.empty()) { + Node w=queue.front(); + queue.pop(); + + InEdgeIt e; + for(g->first(e,w) ; g->valid(e); g->next(e)) { + Node v=g->tail(e); + if (M[v] && (*flow)[e] < (*capacity)[e] ) { + queue.push(v); + M.set(v, false); + } + } + + OutEdgeIt f; + for(g->first(f,w) ; g->valid(f); g->next(f)) { + Node v=g->head(f); + if (M[v] && (*flow)[f] > 0 ) { + queue.push(v); + M.set(v, false); + } + } + } + } + + ///Returns a minimum value cut. + + ///Sets \c M to the characteristic vector of a minimum value cut. + ///\pre M should be a node map of bools initialized to false. + ///\pre \c flow must be a maximum flow. + template + void minCut(CutMap& M) const { minMinCut(M); } + + ///Resets the source node to \c _s. + + ///Resets the source node to \c _s. + /// + void resetSource(Node _s) { s=_s; status=AFTER_NOTHING; } + + ///Resets the target node to \c _t. + + ///Resets the target node to \c _t. + /// + void resetTarget(Node _t) { t=_t; status=AFTER_NOTHING; } + + /// Resets the edge map of the capacities to _cap. + + /// Resets the edge map of the capacities to _cap. + /// + void resetCap(const CapMap& _cap) + { capacity=&_cap; status=AFTER_NOTHING; } + + /// Resets the edge map of the flows to _flow. + + /// Resets the edge map of the flows to _flow. + /// + void resetFlow(FlowMap& _flow) { flow=&_flow; status=AFTER_NOTHING; } + + + private: + + int push(Node w, NNMap& next, VecFirst& first) { + + int lev=level[w]; + Num exc=excess[w]; + int newlevel=n; //bound on the next level of w + + OutEdgeIt e; + for(g->first(e,w); g->valid(e); g->next(e)) { + + if ( (*flow)[e] >= (*capacity)[e] ) continue; + Node v=g->head(e); + + if( lev > level[v] ) { //Push is allowed now + + if ( excess[v]<=0 && v!=t && v!=s ) { + next.set(v,first[level[v]]); + first[level[v]]=v; + // int lev_v=level[v]; + //active[lev_v].push(v); + } + + Num cap=(*capacity)[e]; + Num flo=(*flow)[e]; + Num remcap=cap-flo; + + if ( remcap >= exc ) { //A nonsaturating push. + + flow->set(e, flo+exc); + excess.set(v, excess[v]+exc); + exc=0; + break; + + } else { //A saturating push. + flow->set(e, cap); + excess.set(v, excess[v]+remcap); + exc-=remcap; + } + } else if ( newlevel > level[v] ) newlevel = level[v]; + } //for out edges wv + + if ( exc > 0 ) { + InEdgeIt e; + for(g->first(e,w); g->valid(e); g->next(e)) { + + if( (*flow)[e] <= 0 ) continue; + Node v=g->tail(e); + + if( lev > level[v] ) { //Push is allowed now + + if ( excess[v]<=0 && v!=t && v!=s ) { + next.set(v,first[level[v]]); + first[level[v]]=v; + //int lev_v=level[v]; + //active[lev_v].push(v); + } + + Num flo=(*flow)[e]; + + if ( flo >= exc ) { //A nonsaturating push. + + flow->set(e, flo-exc); + excess.set(v, excess[v]+exc); + exc=0; + break; + } else { //A saturating push. + + excess.set(v, excess[v]+flo); + exc-=flo; + flow->set(e,0); + } + } else if ( newlevel > level[v] ) newlevel = level[v]; + } //for in edges vw + + } // if w still has excess after the out edge for cycle + + excess.set(w, exc); + + return newlevel; + } + + + void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first, + VecNode& level_list, NNMap& left, NNMap& right) + { + std::queue bfs_queue; + + switch (fe) { + case NO_FLOW: //flow is already set to const zero in this case + case ZERO_FLOW: + { + //Reverse_bfs from t, to find the starting level. + level.set(t,0); + bfs_queue.push(t); + + while (!bfs_queue.empty()) { + + Node v=bfs_queue.front(); + bfs_queue.pop(); + int l=level[v]+1; + + InEdgeIt e; + for(g->first(e,v); g->valid(e); g->next(e)) { + Node w=g->tail(e); + if ( level[w] == n && w != s ) { + bfs_queue.push(w); + Node z=level_list[l]; + if ( g->valid(z) ) left.set(z,w); + right.set(w,z); + level_list[l]=w; + level.set(w, l); + } + } + } + + //the starting flow + OutEdgeIt e; + for(g->first(e,s); g->valid(e); g->next(e)) + { + Num c=(*capacity)[e]; + if ( c <= 0 ) continue; + Node w=g->head(e); + if ( level[w] < n ) { + if ( excess[w] <= 0 && w!=t ) + { + next.set(w,first[level[w]]); + first[level[w]]=w; + //active[level[w]].push(w); + } + flow->set(e, c); + excess.set(w, excess[w]+c); + } + } + break; + } + + case GEN_FLOW: + case PRE_FLOW: + { + //Reverse_bfs from t in the residual graph, + //to find the starting level. + level.set(t,0); + bfs_queue.push(t); + + while (!bfs_queue.empty()) { + + Node v=bfs_queue.front(); + bfs_queue.pop(); + int l=level[v]+1; + + InEdgeIt e; + for(g->first(e,v); g->valid(e); g->next(e)) { + if ( (*capacity)[e] <= (*flow)[e] ) continue; + Node w=g->tail(e); + if ( level[w] == n && w != s ) { + bfs_queue.push(w); + Node z=level_list[l]; + if ( g->valid(z) ) left.set(z,w); + right.set(w,z); + level_list[l]=w; + level.set(w, l); + } + } + + OutEdgeIt f; + for(g->first(f,v); g->valid(f); g->next(f)) { + if ( 0 >= (*flow)[f] ) continue; + Node w=g->head(f); + if ( level[w] == n && w != s ) { + bfs_queue.push(w); + Node z=level_list[l]; + if ( g->valid(z) ) left.set(z,w); + right.set(w,z); + level_list[l]=w; + level.set(w, l); + } + } + } + + + //the starting flow + OutEdgeIt e; + for(g->first(e,s); g->valid(e); g->next(e)) + { + Num rem=(*capacity)[e]-(*flow)[e]; + if ( rem <= 0 ) continue; + Node w=g->head(e); + if ( level[w] < n ) { + if ( excess[w] <= 0 && w!=t ) + { + next.set(w,first[level[w]]); + first[level[w]]=w; + //active[level[w]].push(w); + } + flow->set(e, (*capacity)[e]); + excess.set(w, excess[w]+rem); + } + } + + InEdgeIt f; + for(g->first(f,s); g->valid(f); g->next(f)) + { + if ( (*flow)[f] <= 0 ) continue; + Node w=g->tail(f); + if ( level[w] < n ) { + if ( excess[w] <= 0 && w!=t ) + { + next.set(w,first[level[w]]); + first[level[w]]=w; + //active[level[w]].push(w); + } + excess.set(w, excess[w]+(*flow)[f]); + flow->set(f, 0); + } + } + break; + } //case PRE_FLOW + } + } //preflowPreproc + + + + void relabel(Node w, int newlevel, NNMap& next, VecFirst& first, + VecNode& level_list, NNMap& left, + NNMap& right, int& b, int& k, bool what_heur ) + { + + Num lev=level[w]; + + Node right_n=right[w]; + Node left_n=left[w]; + + //unlacing starts + if ( g->valid(right_n) ) { + if ( g->valid(left_n) ) { + right.set(left_n, right_n); + left.set(right_n, left_n); + } else { + level_list[lev]=right_n; + left.set(right_n, INVALID); + } + } else { + if ( g->valid(left_n) ) { + right.set(left_n, INVALID); + } else { + level_list[lev]=INVALID; + } + } + //unlacing ends + + if ( !g->valid(level_list[lev]) ) { + + //gapping starts + for (int i=lev; i!=k ; ) { + Node v=level_list[++i]; + while ( g->valid(v) ) { + level.set(v,n); + v=right[v]; + } + level_list[i]=INVALID; + if ( !what_heur ) first[i]=INVALID; + /*{ + while ( !active[i].empty() ) { + active[i].pop(); //FIXME: ezt szebben kene + } + }*/ + } + + level.set(w,n); + b=lev-1; + k=b; + //gapping ends + + } else { + + if ( newlevel == n ) level.set(w,n); + else { + level.set(w,++newlevel); + next.set(w,first[newlevel]); + first[newlevel]=w; + // active[newlevel].push(w); + if ( what_heur ) b=newlevel; + if ( k < newlevel ) ++k; //now k=newlevel + Node z=level_list[newlevel]; + if ( g->valid(z) ) left.set(z,w); + right.set(w,z); + left.set(w,INVALID); + level_list[newlevel]=w; + } + } + } //relabel + }; //class MaxFlow +} //namespace hugo + +#endif //HUGO_MAX_FLOW_H + + + + diff -r 9fa4045571cd -r 835ebe1b3250 src/work/jacint/max_flow_no_stack.h --- a/src/work/jacint/max_flow_no_stack.h Thu Jul 22 14:09:21 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1318 +0,0 @@ -// -*- C++ -*- -#ifndef HUGO_MAX_FLOW_NO_STACK_H -#define HUGO_MAX_FLOW_NO_STACK_H - -#include -#include -//#include - -#include -#include -#include -#include -#include - -/// \file -/// \brief The same as max_flow.h, but without using stl stack for the active nodes. Only for test. -/// \ingroup galgs - -namespace hugo { - - /// \addtogroup galgs - /// @{ - ///Maximum flow algorithms class. - - ///This class provides various algorithms for finding a flow of - ///maximum value in a directed graph. 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 resetSource, \ref resetTarget, \ref resetCap and - ///\ref resetFlow. Before any subsequent runs of any algorithm of - ///the class \ref resetFlow should be called. - - ///After running an algorithm of the class, the actual flow value - ///can be obtained by calling \ref flowValue(). The minimum - ///value cut can be written into a \c node map of \c bools by - ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes - ///the inclusionwise minimum and maximum of the minimum value - ///cuts, resp.) - ///\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 FlowMap The flow map type. - ///\author Marton Makai, Jacint Szabo - template , - typename FlowMap=typename Graph::template EdgeMap > - class MaxFlowNoStack { - protected: - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::EdgeIt EdgeIt; - typedef typename Graph::OutEdgeIt OutEdgeIt; - typedef typename Graph::InEdgeIt InEdgeIt; - - // typedef typename std::vector > VecStack; - typedef typename std::vector VecFirst; - 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 - typedef ResGraphWrapper ResGW; - //typedef ExpResGraphWrapper ResGW; - typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; - typedef typename ResGW::Edge ResGWEdge; - //typedef typename ResGW::template NodeMap ReachedMap; - typedef typename Graph::template NodeMap ReachedMap; - - - //level works as a bool map in augmenting path algorithms and is - //used by bfs for storing reached information. In preflow, it - //shows the levels of nodes. - ReachedMap level; - - //excess is needed only in preflow - typename Graph::template NodeMap excess; - - //fixme -// protected: - // MaxFlow() { } - // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, - // FlowMap& _flow) - // { - // g=&_G; - // s=_s; - // t=_t; - // capacity=&_capacity; - // flow=&_flow; - // n=_G.nodeNum; - // level.set (_G); //kellene vmi ilyesmi fv - // excess(_G,0); //itt is - // } - - // constants used for heuristics - static const int H0=20; - static const int H1=1; - - public: - - ///Indicates the property of the starting flow. - - ///Indicates the property of the starting flow. 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 - ///the \e target. - ///- \c PRE_FLOW: any preflow, i.e. the sum of the in-flows is at - ///least the sum of the out-flows in every node except the \e source. - ///- \c NO_FLOW: indicates an unspecified edge map. \ref flow will be - ///set to the constant zero flow in the beginning of the algorithm in this case. - enum FlowEnum{ - ZERO_FLOW, - GEN_FLOW, - PRE_FLOW, - NO_FLOW - }; - - enum StatusEnum { - AFTER_NOTHING, - AFTER_AUGMENTING, - AFTER_FAST_AUGMENTING, - AFTER_PRE_FLOW_PHASE_1, - AFTER_PRE_FLOW_PHASE_2 - }; - - /// Don not needle this flag only if necessary. - StatusEnum status; - int number_of_augmentations; - - - template - class TrickyReachedMap { - protected: - IntMap* map; - int* number_of_augmentations; - public: - TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) : - map(&_map), number_of_augmentations(&_number_of_augmentations) { } - void set(const Node& n, bool b) { - if (b) - map->set(n, *number_of_augmentations); - else - map->set(n, *number_of_augmentations-1); - } - bool operator[](const Node& n) const { - return (*map)[n]==*number_of_augmentations; - } - }; - - ///Constructor - - ///\todo Document, please. - /// - MaxFlowNoStack(const Graph& _G, Node _s, Node _t, - const CapMap& _capacity, FlowMap& _flow) : - g(&_G), s(_s), t(_t), capacity(&_capacity), - flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0), - status(AFTER_NOTHING), number_of_augmentations(0) { } - - ///Runs a maximum flow algorithm. - - ///Runs a preflow algorithm, which is the fastest maximum flow - ///algorithm up-to-date. The default for \c fe is ZERO_FLOW. - ///\pre The starting flow must be - /// - a constant zero flow if \c fe is \c ZERO_FLOW, - /// - an arbitary flow if \c fe is \c GEN_FLOW, - /// - an arbitary preflow if \c fe is \c PRE_FLOW, - /// - any map if \c fe is NO_FLOW. - void run(FlowEnum fe=ZERO_FLOW) { - preflow(fe); - } - - - ///Runs a preflow algorithm. - - ///Runs a preflow algorithm. The preflow algorithms provide the - ///fastest way to compute a maximum flow in a directed graph. - ///\pre The starting flow must be - /// - a constant zero flow if \c fe is \c ZERO_FLOW, - /// - an arbitary flow if \c fe is \c GEN_FLOW, - /// - an arbitary preflow if \c fe is \c PRE_FLOW, - /// - any map if \c fe is NO_FLOW. - /// - ///\todo NO_FLOW should be the default flow. - void preflow(FlowEnum fe) { - preflowPhase1(fe); - preflowPhase2(); - } - // Heuristics: - // 2 phase - // gap - // list 'level_list' on the nodes on level i implemented by hand - // stack 'active' on the active nodes on level i - // runs heuristic 'highest label' for H1*n relabels - // runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label' - // Parameters H0 and H1 are initialized to 20 and 1. - - ///Runs the first phase of the preflow algorithm. - - ///The preflow algorithm consists of two phases, this method runs the - ///first phase. After the first phase the maximum flow value and a - ///minimum value cut can already be computed, though a maximum flow - ///is net yet obtained. So after calling this method \ref flowValue - ///and \ref actMinCut gives proper results. - ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not - ///give minimum value cuts unless calling \ref preflowPhase2. - ///\pre The starting flow must be - /// - a constant zero flow if \c fe is \c ZERO_FLOW, - /// - an arbitary flow if \c fe is \c GEN_FLOW, - /// - an arbitary preflow if \c fe is \c PRE_FLOW, - /// - any map if \c fe is NO_FLOW. - void preflowPhase1(FlowEnum fe); - - ///Runs the second phase of the preflow algorithm. - - ///The preflow algorithm consists of two phases, this method runs - ///the second phase. After calling \ref preflowPhase1 and then - ///\ref preflowPhase2 the methods \ref flowValue, \ref minCut, - ///\ref minMinCut and \ref maxMinCut give proper results. - ///\pre \ref preflowPhase1 must be called before. - void preflowPhase2(); - - /// Starting from a flow, this method searches for an augmenting path - /// according to the Edmonds-Karp algorithm - /// and augments the flow on if any. - /// The return value shows if the augmentation was succesful. - bool augmentOnShortestPath(); - bool augmentOnShortestPath2(); - - /// Starting from a flow, this method searches for an augmenting blocking - /// flow according to Dinits' algorithm and augments the flow on if any. - /// The blocking flow is computed in a physically constructed - /// residual graph of type \c Mutablegraph. - /// The return value show sif the augmentation was succesful. - template bool augmentOnBlockingFlow(); - - /// The same as \c augmentOnBlockingFlow but the - /// residual graph is not constructed physically. - /// The return value shows if the augmentation was succesful. - bool augmentOnBlockingFlow2(); - - /// Returns the maximum value of a flow. - - /// Returns the maximum value of a flow, by counting the - /// over-flow of the target node \ref t. - /// It can be called already after running \ref preflowPhase1. - Num flowValue() const { - Num a=0; - FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e]; - FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e]; - return a; - //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan - } - - ///Returns a minimum value cut after calling \ref preflowPhase1. - - ///After the first phase of the preflow algorithm the maximum flow - ///value and a minimum value cut can already be computed. This - ///method can be called after running \ref preflowPhase1 for - ///obtaining a minimum value cut. - /// \warning Gives proper result only right after calling \ref - /// preflowPhase1. - /// \todo We have to make some status variable which shows the - /// actual state - /// of the class. This enables us to determine which methods are valid - /// for MinCut computation - template - void actMinCut(_CutMap& M) const { - NodeIt v; - switch (status) { - case AFTER_PRE_FLOW_PHASE_1: - for(g->first(v); g->valid(v); g->next(v)) { - if (level[v] < n) { - M.set(v, false); - } else { - M.set(v, true); - } - } - break; - case AFTER_PRE_FLOW_PHASE_2: - case AFTER_NOTHING: - minMinCut(M); - break; - case AFTER_AUGMENTING: - for(g->first(v); g->valid(v); g->next(v)) { - if (level[v]) { - M.set(v, true); - } else { - M.set(v, false); - } - } - break; - case AFTER_FAST_AUGMENTING: - for(g->first(v); g->valid(v); g->next(v)) { - if (level[v]==number_of_augmentations) { - M.set(v, true); - } else { - M.set(v, false); - } - } - break; - } - } - - ///Returns the inclusionwise minimum of the minimum value cuts. - - ///Sets \c M to the characteristic vector of the minimum value cut - ///which is inclusionwise minimum. It is computed by processing - ///a bfs from the source node \c s in the residual graph. - ///\pre M should be a node map of bools initialized to false. - ///\pre \c flow must be a maximum flow. - template - void minMinCut(_CutMap& M) const { - std::queue queue; - - M.set(s,true); - queue.push(s); - - while (!queue.empty()) { - Node w=queue.front(); - queue.pop(); - - OutEdgeIt e; - for(g->first(e,w) ; g->valid(e); g->next(e)) { - Node v=g->head(e); - if (!M[v] && (*flow)[e] < (*capacity)[e] ) { - queue.push(v); - M.set(v, true); - } - } - - InEdgeIt f; - for(g->first(f,w) ; g->valid(f); g->next(f)) { - Node v=g->tail(f); - if (!M[v] && (*flow)[f] > 0 ) { - queue.push(v); - M.set(v, true); - } - } - } - } - - ///Returns the inclusionwise maximum of the minimum value cuts. - - ///Sets \c M to the characteristic vector of the minimum value cut - ///which is inclusionwise maximum. It is computed by processing a - ///backward bfs from the target node \c t in the residual graph. - ///\pre M should be a node map of bools initialized to false. - ///\pre \c flow must be a maximum flow. - template - void maxMinCut(_CutMap& M) const { - - NodeIt v; - for(g->first(v) ; g->valid(v); g->next(v)) { - M.set(v, true); - } - - std::queue queue; - - M.set(t,false); - queue.push(t); - - while (!queue.empty()) { - Node w=queue.front(); - queue.pop(); - - InEdgeIt e; - for(g->first(e,w) ; g->valid(e); g->next(e)) { - Node v=g->tail(e); - if (M[v] && (*flow)[e] < (*capacity)[e] ) { - queue.push(v); - M.set(v, false); - } - } - - OutEdgeIt f; - for(g->first(f,w) ; g->valid(f); g->next(f)) { - Node v=g->head(f); - if (M[v] && (*flow)[f] > 0 ) { - queue.push(v); - M.set(v, false); - } - } - } - } - - ///Returns a minimum value cut. - - ///Sets \c M to the characteristic vector of a minimum value cut. - ///\pre M should be a node map of bools initialized to false. - ///\pre \c flow must be a maximum flow. - template - void minCut(CutMap& M) const { minMinCut(M); } - - ///Resets the source node to \c _s. - - ///Resets the source node to \c _s. - /// - void resetSource(Node _s) { s=_s; status=AFTER_NOTHING; } - - ///Resets the target node to \c _t. - - ///Resets the target node to \c _t. - /// - void resetTarget(Node _t) { t=_t; status=AFTER_NOTHING; } - - /// Resets the edge map of the capacities to _cap. - - /// Resets the edge map of the capacities to _cap. - /// - void resetCap(const CapMap& _cap) - { capacity=&_cap; status=AFTER_NOTHING; } - - /// Resets the edge map of the flows to _flow. - - /// Resets the edge map of the flows to _flow. - /// - void resetFlow(FlowMap& _flow) { flow=&_flow; status=AFTER_NOTHING; } - - - private: - - int push(Node w, NNMap& next, VecFirst& first) { - - int lev=level[w]; - Num exc=excess[w]; - int newlevel=n; //bound on the next level of w - - OutEdgeIt e; - for(g->first(e,w); g->valid(e); g->next(e)) { - - if ( (*flow)[e] >= (*capacity)[e] ) continue; - Node v=g->head(e); - - if( lev > level[v] ) { //Push is allowed now - - if ( excess[v]<=0 && v!=t && v!=s ) { - next.set(v,first[level[v]]); - first[level[v]]=v; - // int lev_v=level[v]; - //active[lev_v].push(v); - } - - Num cap=(*capacity)[e]; - Num flo=(*flow)[e]; - Num remcap=cap-flo; - - if ( remcap >= exc ) { //A nonsaturating push. - - flow->set(e, flo+exc); - excess.set(v, excess[v]+exc); - exc=0; - break; - - } else { //A saturating push. - flow->set(e, cap); - excess.set(v, excess[v]+remcap); - exc-=remcap; - } - } else if ( newlevel > level[v] ) newlevel = level[v]; - } //for out edges wv - - if ( exc > 0 ) { - InEdgeIt e; - for(g->first(e,w); g->valid(e); g->next(e)) { - - if( (*flow)[e] <= 0 ) continue; - Node v=g->tail(e); - - if( lev > level[v] ) { //Push is allowed now - - if ( excess[v]<=0 && v!=t && v!=s ) { - next.set(v,first[level[v]]); - first[level[v]]=v; - //int lev_v=level[v]; - //active[lev_v].push(v); - } - - Num flo=(*flow)[e]; - - if ( flo >= exc ) { //A nonsaturating push. - - flow->set(e, flo-exc); - excess.set(v, excess[v]+exc); - exc=0; - break; - } else { //A saturating push. - - excess.set(v, excess[v]+flo); - exc-=flo; - flow->set(e,0); - } - } else if ( newlevel > level[v] ) newlevel = level[v]; - } //for in edges vw - - } // if w still has excess after the out edge for cycle - - excess.set(w, exc); - - return newlevel; - } - - - void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first, - VecNode& level_list, NNMap& left, NNMap& right) - { - std::queue bfs_queue; - - switch (fe) { - case NO_FLOW: //flow is already set to const zero in this case - case ZERO_FLOW: - { - //Reverse_bfs from t, to find the starting level. - level.set(t,0); - bfs_queue.push(t); - - while (!bfs_queue.empty()) { - - Node v=bfs_queue.front(); - bfs_queue.pop(); - int l=level[v]+1; - - InEdgeIt e; - for(g->first(e,v); g->valid(e); g->next(e)) { - Node w=g->tail(e); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( g->valid(z) ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } - } - } - - //the starting flow - OutEdgeIt e; - for(g->first(e,s); g->valid(e); g->next(e)) - { - Num c=(*capacity)[e]; - if ( c <= 0 ) continue; - Node w=g->head(e); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) - { - next.set(w,first[level[w]]); - first[level[w]]=w; - //active[level[w]].push(w); - } - flow->set(e, c); - excess.set(w, excess[w]+c); - } - } - break; - } - - case GEN_FLOW: - case PRE_FLOW: - { - //Reverse_bfs from t in the residual graph, - //to find the starting level. - level.set(t,0); - bfs_queue.push(t); - - while (!bfs_queue.empty()) { - - Node v=bfs_queue.front(); - bfs_queue.pop(); - int l=level[v]+1; - - InEdgeIt e; - for(g->first(e,v); g->valid(e); g->next(e)) { - if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node w=g->tail(e); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( g->valid(z) ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } - } - - OutEdgeIt f; - for(g->first(f,v); g->valid(f); g->next(f)) { - if ( 0 >= (*flow)[f] ) continue; - Node w=g->head(f); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( g->valid(z) ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } - } - } - - - //the starting flow - OutEdgeIt e; - for(g->first(e,s); g->valid(e); g->next(e)) - { - Num rem=(*capacity)[e]-(*flow)[e]; - if ( rem <= 0 ) continue; - Node w=g->head(e); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) - { - next.set(w,first[level[w]]); - first[level[w]]=w; - //active[level[w]].push(w); - } - flow->set(e, (*capacity)[e]); - excess.set(w, excess[w]+rem); - } - } - - InEdgeIt f; - for(g->first(f,s); g->valid(f); g->next(f)) - { - if ( (*flow)[f] <= 0 ) continue; - Node w=g->tail(f); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) - { - next.set(w,first[level[w]]); - first[level[w]]=w; - //active[level[w]].push(w); - } - excess.set(w, excess[w]+(*flow)[f]); - flow->set(f, 0); - } - } - break; - } //case PRE_FLOW - } - } //preflowPreproc - - - - void relabel(Node w, int newlevel, NNMap& next, VecFirst& first, - VecNode& level_list, NNMap& left, - NNMap& right, int& b, int& k, bool what_heur ) - { - - Num lev=level[w]; - - Node right_n=right[w]; - Node left_n=left[w]; - - //unlacing starts - if ( g->valid(right_n) ) { - if ( g->valid(left_n) ) { - right.set(left_n, right_n); - left.set(right_n, left_n); - } else { - level_list[lev]=right_n; - left.set(right_n, INVALID); - } - } else { - if ( g->valid(left_n) ) { - right.set(left_n, INVALID); - } else { - level_list[lev]=INVALID; - } - } - //unlacing ends - - if ( !g->valid(level_list[lev]) ) { - - //gapping starts - for (int i=lev; i!=k ; ) { - Node v=level_list[++i]; - while ( g->valid(v) ) { - level.set(v,n); - v=right[v]; - } - level_list[i]=INVALID; - if ( !what_heur ) first[i]=INVALID; - /*{ - while ( !active[i].empty() ) { - active[i].pop(); //FIXME: ezt szebben kene - } - }*/ - } - - level.set(w,n); - b=lev-1; - k=b; - //gapping ends - - } else { - - if ( newlevel == n ) level.set(w,n); - else { - level.set(w,++newlevel); - next.set(w,first[newlevel]); - first[newlevel]=w; - // active[newlevel].push(w); - if ( what_heur ) b=newlevel; - if ( k < newlevel ) ++k; //now k=newlevel - Node z=level_list[newlevel]; - if ( g->valid(z) ) left.set(z,w); - right.set(w,z); - left.set(w,INVALID); - level_list[newlevel]=w; - } - } - - } //relabel - - - template - class DistanceMap { - protected: - const MapGraphWrapper* g; - typename MapGraphWrapper::template NodeMap dist; - public: - DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { } - void set(const typename MapGraphWrapper::Node& n, int a) { - dist.set(n, a); - } - int operator[](const typename MapGraphWrapper::Node& n) const { - return dist[n]; - } - // int get(const typename MapGraphWrapper::Node& n) const { - // return dist[n]; } - // bool get(const typename MapGraphWrapper::Edge& e) const { - // return (dist.get(g->tail(e))head(e))); } - bool operator[](const typename MapGraphWrapper::Edge& e) const { - return (dist[g->tail(e)]head(e)]); - } - }; - - }; - - - template - void MaxFlowNoStack::preflowPhase1(FlowEnum fe) - { - - int heur0=(int)(H0*n); //time while running 'bound decrease' - int heur1=(int)(H1*n); //time while running 'highest label' - int heur=heur1; //starting time interval (#of relabels) - int numrelabel=0; - - bool what_heur=1; - //It is 0 in case 'bound decrease' and 1 in case 'highest label' - - bool end=false; - //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 b=k; //bound on the highest level under n of an active node - - VecFirst first(n, INVALID); - NNMap next(*g, INVALID); //maybe INVALID is not needed - // VecStack active(n); - - NNMap left(*g, INVALID); - NNMap right(*g, INVALID); - VecNode level_list(n,INVALID); - //List of the nodes in level ifirst(v); g->valid(v); g->next(v)) level.set(v,n); - //setting each node to level n - - if ( fe == NO_FLOW ) { - EdgeIt e; - for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0); - } - - switch (fe) { //computing the excess - case PRE_FLOW: - { - NodeIt v; - for(g->first(v); g->valid(v); g->next(v)) { - Num exc=0; - - InEdgeIt e; - for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e]; - OutEdgeIt f; - for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f]; - - excess.set(v,exc); - - //putting the active nodes into the stack - int lev=level[v]; - if ( exc > 0 && lev < n && v != t ) - { - next.set(v,first[lev]); - first[lev]=v; - } - // active[lev].push(v); - } - break; - } - case GEN_FLOW: - { - NodeIt v; - for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0); - - Num exc=0; - InEdgeIt e; - for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e]; - OutEdgeIt f; - for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f]; - excess.set(t,exc); - break; - } - case ZERO_FLOW: - case NO_FLOW: - { - NodeIt v; - for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0); - break; - } - } - - preflowPreproc(fe, next, first,/*active*/ level_list, left, right); - //End of preprocessing - - - //Push/relabel on the highest level active nodes. - while ( true ) { - if ( b == 0 ) { - if ( !what_heur && !end && k > 0 ) { - b=k; - end=true; - } else break; - } - - if ( !g->valid(first[b])/*active[b].empty()*/ ) --b; - else { - end=false; - Node w=first[b]; - first[b]=next[w]; - /* Node w=active[b].top(); - active[b].pop();*/ - int newlevel=push(w,/*active*/next, first); - if ( excess[w] > 0 ) relabel(w, newlevel, /*active*/next, first, level_list, - left, right, b, k, what_heur); - - ++numrelabel; - if ( numrelabel >= heur ) { - numrelabel=0; - if ( what_heur ) { - what_heur=0; - heur=heur0; - end=false; - } else { - what_heur=1; - heur=heur1; - b=k; - } - } - } - } - - status=AFTER_PRE_FLOW_PHASE_1; - } - - - - template - void MaxFlowNoStack::preflowPhase2() - { - - int k=n-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 - - - VecFirst first(n, INVALID); - NNMap next(*g, INVALID); //maybe INVALID is not needed - // VecStack active(n); - level.set(s,0); - std::queue bfs_queue; - bfs_queue.push(s); - - while (!bfs_queue.empty()) { - - Node v=bfs_queue.front(); - bfs_queue.pop(); - int l=level[v]+1; - - InEdgeIt e; - for(g->first(e,v); g->valid(e); g->next(e)) { - if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node u=g->tail(e); - if ( level[u] >= n ) { - bfs_queue.push(u); - level.set(u, l); - if ( excess[u] > 0 ) { - next.set(u,first[l]); - first[l]=u; - //active[l].push(u); - } - } - } - - OutEdgeIt f; - for(g->first(f,v); g->valid(f); g->next(f)) { - if ( 0 >= (*flow)[f] ) continue; - Node u=g->head(f); - if ( level[u] >= n ) { - bfs_queue.push(u); - level.set(u, l); - if ( excess[u] > 0 ) { - next.set(u,first[l]); - first[l]=u; - //active[l].push(u); - } - } - } - } - b=n-2; - - while ( true ) { - - if ( b == 0 ) break; - - if ( !g->valid(first[b])/*active[b].empty()*/ ) --b; - else { - - Node w=first[b]; - first[b]=next[w]; - /* Node w=active[b].top(); - active[b].pop();*/ - int newlevel=push(w,next, first/*active*/); - - //relabel - if ( excess[w] > 0 ) { - level.set(w,++newlevel); - next.set(w,first[newlevel]); - first[newlevel]=w; - //active[newlevel].push(w); - b=newlevel; - } - } // if stack[b] is nonempty - } // while(true) - - status=AFTER_PRE_FLOW_PHASE_2; - } - - - - template - bool MaxFlowNoStack::augmentOnShortestPath() - { - ResGW res_graph(*g, *capacity, *flow); - bool _augment=false; - - //ReachedMap level(res_graph); - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); - BfsIterator bfs(res_graph, level); - bfs.pushAndSetReached(s); - - typename ResGW::template NodeMap pred(res_graph); - pred.set(s, INVALID); - - typename ResGW::template NodeMap free(res_graph); - - //searching for augmenting path - while ( !bfs.finished() ) { - ResGWOutEdgeIt e=bfs; - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); - pred.set(w, e); - if (res_graph.valid(pred[v])) { - free.set(w, std::min(free[v], res_graph.resCap(e))); - } else { - free.set(w, res_graph.resCap(e)); - } - if (res_graph.head(e)==t) { _augment=true; break; } - } - - ++bfs; - } //end of searching augmenting path - - if (_augment) { - Node n=t; - Num augment_value=free[t]; - while (res_graph.valid(pred[n])) { - ResGWEdge e=pred[n]; - res_graph.augment(e, augment_value); - n=res_graph.tail(e); - } - } - - status=AFTER_AUGMENTING; - return _augment; - } - - - template - bool MaxFlowNoStack::augmentOnShortestPath2() - { - ResGW res_graph(*g, *capacity, *flow); - bool _augment=false; - - if (status!=AFTER_FAST_AUGMENTING) { - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); - number_of_augmentations=1; - } else { - ++number_of_augmentations; - } - TrickyReachedMap - tricky_reached_map(level, number_of_augmentations); - //ReachedMap level(res_graph); -// FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); - BfsIterator > - bfs(res_graph, tricky_reached_map); - bfs.pushAndSetReached(s); - - typename ResGW::template NodeMap pred(res_graph); - pred.set(s, INVALID); - - typename ResGW::template NodeMap free(res_graph); - - //searching for augmenting path - while ( !bfs.finished() ) { - ResGWOutEdgeIt e=bfs; - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - Node v=res_graph.tail(e); - Node w=res_graph.head(e); - pred.set(w, e); - if (res_graph.valid(pred[v])) { - free.set(w, std::min(free[v], res_graph.resCap(e))); - } else { - free.set(w, res_graph.resCap(e)); - } - if (res_graph.head(e)==t) { _augment=true; break; } - } - - ++bfs; - } //end of searching augmenting path - - if (_augment) { - Node n=t; - Num augment_value=free[t]; - while (res_graph.valid(pred[n])) { - ResGWEdge e=pred[n]; - res_graph.augment(e, augment_value); - n=res_graph.tail(e); - } - } - - status=AFTER_FAST_AUGMENTING; - return _augment; - } - - - template - template - bool MaxFlowNoStack::augmentOnBlockingFlow() - { - typedef MutableGraph MG; - bool _augment=false; - - ResGW res_graph(*g, *capacity, *flow); - - //bfs for distances on the residual graph - //ReachedMap level(res_graph); - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); - BfsIterator bfs(res_graph, level); - bfs.pushAndSetReached(s); - typename ResGW::template NodeMap - dist(res_graph); //filled up with 0's - - //F will contain the physical copy of the residual graph - //with the set of edges which are on shortest paths - MG F; - typename ResGW::template NodeMap - res_graph_to_F(res_graph); - { - typename ResGW::NodeIt n; - for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { - res_graph_to_F.set(n, F.addNode()); - } - } - - typename MG::Node sF=res_graph_to_F[s]; - typename MG::Node tF=res_graph_to_F[t]; - typename MG::template EdgeMap original_edge(F); - typename MG::template EdgeMap residual_capacity(F); - - while ( !bfs.finished() ) { - ResGWOutEdgeIt e=bfs; - if (res_graph.valid(e)) { - if (bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], - res_graph_to_F[res_graph.head(e)]); - original_edge.update(); - original_edge.set(f, e); - residual_capacity.update(); - residual_capacity.set(f, res_graph.resCap(e)); - } else { - if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], - res_graph_to_F[res_graph.head(e)]); - original_edge.update(); - original_edge.set(f, e); - residual_capacity.update(); - residual_capacity.set(f, res_graph.resCap(e)); - } - } - } - ++bfs; - } //computing distances from s in the residual graph - - bool __augment=true; - - while (__augment) { - __augment=false; - //computing blocking flow with dfs - DfsIterator< MG, typename MG::template NodeMap > dfs(F); - typename MG::template NodeMap pred(F); - pred.set(sF, INVALID); - //invalid iterators for sources - - typename MG::template NodeMap free(F); - - dfs.pushAndSetReached(sF); - while (!dfs.finished()) { - ++dfs; - if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { - if (dfs.isBNodeNewlyReached()) { - typename MG::Node v=F.aNode(dfs); - typename MG::Node w=F.bNode(dfs); - pred.set(w, dfs); - if (F.valid(pred[v])) { - free.set(w, std::min(free[v], residual_capacity[dfs])); - } else { - free.set(w, residual_capacity[dfs]); - } - if (w==tF) { - __augment=true; - _augment=true; - break; - } - - } else { - F.erase(/*typename MG::OutEdgeIt*/(dfs)); - } - } - } - - if (__augment) { - typename MG::Node n=tF; - Num augment_value=free[tF]; - while (F.valid(pred[n])) { - typename MG::Edge e=pred[n]; - res_graph.augment(original_edge[e], augment_value); - n=F.tail(e); - if (residual_capacity[e]==augment_value) - F.erase(e); - else - residual_capacity.set(e, residual_capacity[e]-augment_value); - } - } - - } - - status=AFTER_AUGMENTING; - return _augment; - } - - - - - template - bool MaxFlowNoStack::augmentOnBlockingFlow2() - { - bool _augment=false; - - ResGW res_graph(*g, *capacity, *flow); - - //ReachedMap level(res_graph); - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); - BfsIterator bfs(res_graph, level); - - bfs.pushAndSetReached(s); - DistanceMap dist(res_graph); - while ( !bfs.finished() ) { - ResGWOutEdgeIt e=bfs; - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); - } - ++bfs; - } //computing distances from s in the residual graph - - //Subgraph containing the edges on some shortest paths - ConstMap true_map(true); - typedef SubGraphWrapper, - DistanceMap > FilterResGW; - FilterResGW filter_res_graph(res_graph, true_map, dist); - - //Subgraph, which is able to delete edges which are already - //met by the dfs - typename FilterResGW::template NodeMap - first_out_edges(filter_res_graph); - typename FilterResGW::NodeIt v; - for(filter_res_graph.first(v); filter_res_graph.valid(v); - filter_res_graph.next(v)) - { - typename FilterResGW::OutEdgeIt e; - filter_res_graph.first(e, v); - first_out_edges.set(v, e); - } - typedef ErasingFirstGraphWrapper > ErasingResGW; - ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); - - bool __augment=true; - - while (__augment) { - - __augment=false; - //computing blocking flow with dfs - DfsIterator< ErasingResGW, - typename ErasingResGW::template NodeMap > - dfs(erasing_res_graph); - typename ErasingResGW:: - template NodeMap - pred(erasing_res_graph); - pred.set(s, INVALID); - //invalid iterators for sources - - typename ErasingResGW::template NodeMap - free1(erasing_res_graph); - - dfs.pushAndSetReached - ///\bug hugo 0.2 - (typename ErasingResGW::Node - (typename FilterResGW::Node - (typename ResGW::Node(s) - ) - ) - ); - while (!dfs.finished()) { - ++dfs; - if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs))) - { - if (dfs.isBNodeNewlyReached()) { - - typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); - typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); - - pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); - if (erasing_res_graph.valid(pred[v])) { - free1.set - (w, std::min(free1[v], res_graph.resCap - (typename ErasingResGW::OutEdgeIt(dfs)))); - } else { - free1.set - (w, res_graph.resCap - (typename ErasingResGW::OutEdgeIt(dfs))); - } - - if (w==t) { - __augment=true; - _augment=true; - break; - } - } else { - erasing_res_graph.erase(dfs); - } - } - } - - if (__augment) { - typename ErasingResGW::Node - n=typename FilterResGW::Node(typename ResGW::Node(t)); - // typename ResGW::NodeMap a(res_graph); - // typename ResGW::Node b; - // Num j=a[b]; - // typename FilterResGW::NodeMap a1(filter_res_graph); - // typename FilterResGW::Node b1; - // Num j1=a1[b1]; - // typename ErasingResGW::NodeMap a2(erasing_res_graph); - // typename ErasingResGW::Node b2; - // Num j2=a2[b2]; - Num augment_value=free1[n]; - while (erasing_res_graph.valid(pred[n])) { - typename ErasingResGW::OutEdgeIt e=pred[n]; - res_graph.augment(e, augment_value); - n=erasing_res_graph.tail(e); - if (res_graph.resCap(e)==0) - erasing_res_graph.erase(e); - } - } - - } //while (__augment) - - status=AFTER_AUGMENTING; - return _augment; - } - - -} //namespace hugo - -#endif //HUGO_MAX_FLOW_H - - - -