# HG changeset patch # User marci # Date 1095332392 0 # Node ID 732f2acb7239748ac945810b76ee8d710e025f00 # Parent 021e513a2d8314d0ca1549d07f64fd31315d150e bug correction diff -r 021e513a2d83 -r 732f2acb7239 src/work/marci/augmenting_flow.h --- a/src/work/marci/augmenting_flow.h Thu Sep 16 10:59:30 2004 +0000 +++ b/src/work/marci/augmenting_flow.h Thu Sep 16 10:59:52 2004 +0000 @@ -3,15 +3,14 @@ #define HUGO_AUGMENTING_FLOW_H #include -#include -#include +//#include +//#include #include #include #include #include #include -//#include /// \file /// \brief Maximum flow algorithms. @@ -19,849 +18,68 @@ namespace hugo { + /// \brief A map for filtering the edge-set to those edges + /// which are tight w.r.t. some node_potential map and + /// edge_distance map. + /// + /// A node-map node_potential is said to be a potential w.r.t. + /// an edge-map edge_distance + /// if and only if for each edge e, node_potential[g.head(e)] + /// <= edge_distance[e]+node_potential[g.tail(e)] + /// (or the reverse inequality holds for each edge). + /// An edge is said to be tight if this inequality holds with equality, + /// and the map returns true exactly for those edges. + /// To avoid rounding errors, it is recommended to use this class with exact + /// types, e.g. with int. + template + class TightEdgeFilterMap { + protected: + const Graph* g; + NodePotentialMap* node_potential; + EdgeDistanceMap* edge_distance; + public: + TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, + EdgeDistanceMap& _edge_distance) : + g(&_g), node_potential(&_node_potential), + edge_distance(&_edge_distance) { } +// void set(const typename Graph::Node& n, int a) { +// pot->set(n, a); +// } +// int operator[](const typename Graph::Node& n) const { +// return (*node_potential)[n]; +// } + bool operator[](const typename Graph::Edge& e) const { + return ((*node_potential)[g->head(e)] == + (*edge_distance)[e]+(*node_potential)[g->tail(e)]); + } + }; + /// \addtogroup galgs /// @{ - ///Maximum flow algorithms class. + /// Class for augmenting path flow algorithms. - ///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. + /// 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.) + /// 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 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; -// // } -// // }; - -// 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. -// 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(); - -// /// 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: -// case AFTER_AUGMENTING: -// case AFTER_FAST_AUGMENTING: -// 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, VecStack& active) { - -// 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 ) { -// 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 ) { -// 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, VecStack& active, -// 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 first=level_list[l]; -// if ( g->valid(first) ) left.set(first,w); -// right.set(w,first); -// 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 ) 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 first=level_list[l]; -// if ( g->valid(first) ) left.set(first,w); -// right.set(w,first); -// 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 first=level_list[l]; -// if ( g->valid(first) ) left.set(first,w); -// right.set(w,first); -// 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 ) 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 ) 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, VecStack& active, -// VecNode& level_list, NNMap& left, -// NNMap& right, int& b, int& k, bool what_heur ) -// { - -// //FIXME jacint: ez mitol num -// // Num lev=level[w]; -// int 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 ) { -// 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); -// active[newlevel].push(w); -// if ( what_heur ) b=newlevel; -// if ( k < newlevel ) ++k; //now k=newlevel -// Node first=level_list[newlevel]; -// if ( g->valid(first) ) left.set(first,w); -// right.set(w,first); -// left.set(w,INVALID); -// level_list[newlevel]=w; -// } -// } - -// } //relabel - -// }; - - - -// template -// void MaxFlow::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 - -// 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 ) 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, 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 ( active[b].empty() ) --b; -// else { -// end=false; -// Node w=active[b].top(); -// active[b].pop(); -// int newlevel=push(w,active); -// if ( excess[w] > 0 ) relabel(w, newlevel, active, 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 MaxFlow::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 - -// 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 ) 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 ) active[l].push(u); -// } -// } -// } -// b=n-2; - -// while ( true ) { - -// if ( b == 0 ) break; - -// if ( active[b].empty() ) --b; -// else { -// Node w=active[b].top(); -// active[b].pop(); -// int newlevel=push(w,active); - -// //relabel -// if ( excess[w] > 0 ) { -// level.set(w,++newlevel); -// active[newlevel].push(w); -// b=newlevel; -// } -// } // if stack[b] is nonempty -// } // while(true) - -// status=AFTER_PRE_FLOW_PHASE_2; -// } - - + ///\author Marton Makai template , typename FlowMap=typename Graph::template EdgeMap > @@ -873,10 +91,6 @@ typedef typename Graph::OutEdgeIt OutEdgeIt; typedef typename Graph::InEdgeIt InEdgeIt; -// typedef typename std::vector > VecStack; -// typedef typename Graph::template NodeMap NNMap; -// typedef typename std::vector VecNode; - const Graph* g; Node s; Node t; @@ -890,37 +104,12 @@ //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: @@ -1088,28 +277,6 @@ //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan } - 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)]); - } - }; - }; @@ -1244,9 +411,8 @@ res_graph_to_F(res_graph); { typename ResGW::NodeIt n; - for(res_graph.first(n); n!=INVALID; ++n) { + for(res_graph.first(n); n!=INVALID; ++n) res_graph_to_F.set(n, F.addNode()); - } } typename MG::Node sF=res_graph_to_F[s]; @@ -1336,7 +502,8 @@ return _augment; } - + /// Blocking flow augmentation without constructing the layered + /// graph physically in which the blocking flow is computed. template bool AugmentingFlow::augmentOnBlockingFlow2() { @@ -1344,37 +511,41 @@ ResGW res_graph(*g, *capacity, *flow); - //ReachedMap level(res_graph); + //Potential map, for distances from s + typename ResGW::template NodeMap potential(res_graph, 0); + typedef ConstMap Const1Map; + Const1Map const_1_map(1); + TightEdgeFilterMap, + Const1Map> tight_edge_filter(res_graph, potential, const_1_map); + for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); BfsIterator bfs(res_graph, level); + bfs.pushAndSetReached(s); - bfs.pushAndSetReached(s); - DistanceMap dist(res_graph); + //computing distances from s in the residual graph while ( !bfs.finished() ) { ResGWEdge e=bfs; - if (e!=INVALID && bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); - } + if (e!=INVALID && bfs.isBNodeNewlyReached()) + potential.set(res_graph.head(e), potential[res_graph.tail(e)]+1); ++bfs; - } //computing distances from s in the residual graph + } - //Subgraph containing the edges on some shortest paths + //Subgraph containing the edges on some shortest paths + //(i.e. tight edges) ConstMap true_map(true); typedef SubGraphWrapper, - DistanceMap > FilterResGW; - FilterResGW filter_res_graph(res_graph, true_map, dist); + TightEdgeFilterMap, + Const1Map> > FilterResGW; + FilterResGW filter_res_graph(res_graph, true_map, tight_edge_filter); //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); v!=INVALID; ++v) - { - typename FilterResGW::OutEdgeIt e; - filter_res_graph.first(e, v); - first_out_edges.set(v, e); - } + for (typename FilterResGW::NodeIt v(filter_res_graph); v!=INVALID; ++v) + first_out_edges.set + (v, typename FilterResGW::OutEdgeIt(filter_res_graph, v)); + typedef ErasingFirstGraphWrapper > ErasingResGW; ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); @@ -1407,47 +578,37 @@ while (!dfs.finished()) { ++dfs; - if (typename ErasingResGW::Edge(dfs)!=INVALID) - { - if (dfs.isBNodeNewlyReached()) { + if (typename ErasingResGW::Edge(dfs)!=INVALID) { + if (dfs.isBNodeNewlyReached()) { + + typename ErasingResGW::Node v=erasing_res_graph.tail(dfs); + typename ErasingResGW::Node w=erasing_res_graph.head(dfs); - typename ErasingResGW::Node v=erasing_res_graph.tail(dfs); - typename ErasingResGW::Node w=erasing_res_graph.head(dfs); + pred.set(w, typename ErasingResGW::Edge(dfs)); + if (pred[v]!=INVALID) { + free1.set + (w, std::min(free1[v], res_graph.resCap + (typename ErasingResGW::Edge(dfs)))); + } else { + free1.set + (w, res_graph.resCap + (typename ErasingResGW::Edge(dfs))); + } - pred.set(w, typename ErasingResGW::Edge(dfs)); - if (pred[v]!=INVALID) { - free1.set - (w, std::min(free1[v], res_graph.resCap - (typename ErasingResGW::Edge(dfs)))); - } else { - free1.set - (w, res_graph.resCap - (typename ErasingResGW::Edge(dfs))); - } - - if (w==t) { - __augment=true; - _augment=true; - break; - } - } else { - erasing_res_graph.erase(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 (pred[n]!=INVALID) { typename ErasingResGW::Edge e=pred[n]; @@ -1470,5 +631,3 @@ #endif //HUGO_AUGMENTING_FLOW_H - -