# HG changeset patch # User marci # Date 1084982978 0 # Node ID 19dd325da0e8adeaa46f16c2f31c7dea2ebbb4d2 # Parent bd7a69231cf888d340fa8ddb5969b262d49f2ecf the same diff -r bd7a69231cf8 -r 19dd325da0e8 src/work/jacint/max_flow.h --- a/src/work/jacint/max_flow.h Wed May 19 16:06:57 2004 +0000 +++ b/src/work/jacint/max_flow.h Wed May 19 16:09:38 2004 +0000 @@ -25,22 +25,22 @@ ///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 can be passed to the algorithm through the + ///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, otherwise it will - ///start from a maximum flow. - ///After running an algorithm of the class, the maximum value of a - ///value can be obtained by calling \ref flowValue(). The minimum + ///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 type of the capacity map. - ///\param FlowMap The type of the flow map. + ///\param CapMap The capacity map type. + ///\param FlowMap The flow map type. ///\author Marton Makai, Jacint Szabo template , @@ -111,17 +111,46 @@ ///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{ + enum FlowEnum{ ZERO_FLOW, GEN_FLOW, PRE_FLOW, NO_FLOW }; + enum StatusEnum { + AFTER_NOTHING, + AFTER_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) { + map->set(n, *number_of_augmentations); + } + 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) {} + flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0), + status(AFTER_NOTHING), number_of_augmentations(0) { } ///Runs a maximum flow algorithm. @@ -132,11 +161,11 @@ /// - 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) { + void run(FlowEnum fe=ZERO_FLOW) { preflow(fe); } - + ///Runs a preflow algorithm. ///Runs a preflow algorithm. The preflow algorithms provide the @@ -146,7 +175,7 @@ /// - 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) { + void preflow(FlowEnum fe) { preflowPhase1(fe); preflowPhase2(); } @@ -173,7 +202,7 @@ /// - 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 ); + void preflowPhase1(FlowEnum fe); ///Runs the second phase of the preflow algorithm. @@ -189,6 +218,7 @@ /// 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. @@ -207,7 +237,7 @@ /// 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() { + 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]; @@ -228,14 +258,31 @@ /// of the class. This enables us to determine which methods are valid /// for MinCut computation template - void actMinCut(_CutMap& M) { + void actMinCut(_CutMap& M) const { NodeIt v; - for(g->first(v); g->valid(v); g->next(v)) { - if ( level[v] < n ) { - M.set(v,false); - } else { - M.set(v,true); + 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; } } @@ -247,8 +294,7 @@ ///\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) { - + void minMinCut(_CutMap& M) const { std::queue queue; M.set(s,true); @@ -286,7 +332,7 @@ ///\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) { + void maxMinCut(_CutMap& M) const { NodeIt v; for(g->first(v) ; g->valid(v); g->next(v)) { @@ -328,31 +374,31 @@ ///\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) { minMinCut(M); } + 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; } + 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; } + 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; } + 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; } + void resetFlow(FlowMap& _flow) { flow=&_flow; status=AFTER_NOTHING; } private: @@ -434,7 +480,7 @@ } - void preflowPreproc(flowEnum fe, VecStack& active, + void preflowPreproc(FlowEnum fe, VecStack& active, VecNode& level_list, NNMap& left, NNMap& right) { std::queue bfs_queue; @@ -638,8 +684,9 @@ void set(const typename MapGraphWrapper::Node& n, int a) { dist.set(n, a); } - int operator[](const typename MapGraphWrapper::Node& n) - { return dist[n]; } + 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 { @@ -653,7 +700,7 @@ template - void MaxFlow::preflowPhase1( flowEnum fe ) + void MaxFlow::preflowPhase1(FlowEnum fe) { int heur0=(int)(H0*n); //time while running 'bound decrease' @@ -766,6 +813,8 @@ } } } + + status=AFTER_PRE_FLOW_PHASE_1; } @@ -830,6 +879,8 @@ } } // if stack[b] is nonempty } // while(true) + + status=AFTER_PRE_FLOW_PHASE_2; } @@ -878,13 +929,67 @@ } } + status=AFTER_AUGMENTING; return _augment; } + template + bool MaxFlow::augmentOnShortestPath2() + { + ResGW res_graph(*g, *capacity, *flow); + bool _augment=false; + if (status!=AFTER_AUGMENTING) { + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, -1); + number_of_augmentations=0; + } 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_AUGMENTING; + return _augment; + } template @@ -999,6 +1104,7 @@ } + status=AFTER_AUGMENTING; return _augment; } @@ -1129,6 +1235,7 @@ } //while (__augment) + status=AFTER_AUGMENTING; return _augment; }