# HG changeset patch # User jacint # Date 1084444220 0 # Node ID 26819ef1611f7b9a608509087d9eaa4872c9564b # Parent 9ea585de06ea2edbcfba5049c67751ee9f9228c5 Almost full documentation added, NO_FLOW incorporated, Phase0(1) changed to Phase1(2) diff -r 9ea585de06ea -r 26819ef1611f src/work/jacint/max_flow.h --- a/src/work/jacint/max_flow.h Thu May 13 10:29:19 2004 +0000 +++ b/src/work/jacint/max_flow.h Thu May 13 10:30:20 2004 +0000 @@ -1,38 +1,4 @@ // -*- C++ -*- - -/* - 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. - - Constructors: - - Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if - FlowMap is not constant zero, and should be true if it is - - Members: - - void run() - - Num flowValue() : returns the value of a maximum flow - - void minMinCut(CutMap& M) : sets M to the characteristic vector of the - minimum min cut. M should be a map of bools initialized to false. ??Is it OK? - - void maxMinCut(CutMap& M) : sets M to the characteristic vector of the - maximum min cut. M should be a map of bools initialized to false. - - void minCut(CutMap& M) : sets M to the characteristic vector of - a min cut. M should be a map of bools initialized to false. - -*/ - #ifndef HUGO_MAX_FLOW_H #define HUGO_MAX_FLOW_H @@ -47,15 +13,35 @@ #include /// \file -/// \brief Maximum flows. +/// \brief Maximum flow algorithms. /// \ingroup galgs namespace hugo { + /// \addtogroup galgs + /// @{ + ///Maximum flow algorithms class. - // ///\author Marton Makai, Jacint Szabo - /// A class for computing max flows and related quantities. - /// \ingroup galgs + ///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 + ///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 + ///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 undirected 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. + ///\author Marton Makai, Jacint Szabo template , typename FlowMap=typename Graph::template EdgeMap > @@ -63,6 +49,7 @@ 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; @@ -81,13 +68,18 @@ 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; - //level works as a bool map in augmenting path algorithms - //and is used by bfs for storing reached information. - //In preflow, it shows levels of nodes. - //typename Graph::template NodeMap level; + + //excess is needed only in preflow typename Graph::template NodeMap excess; - // protected: + + //fixme +// protected: // MaxFlow() { } // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, // FlowMap& _flow) @@ -108,12 +100,17 @@ public: - ///\todo Document this. - ///\todo Maybe, it should be PRE_FLOW instead. - ///- \c NO_FLOW means nothing, - ///- \c ZERO_FLOW means something, - ///- \c GEN_FLOW means something else, - ///- \c PRE_FLOW is something different. + ///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, @@ -126,30 +123,66 @@ g(&_G), s(_s), t(_t), capacity(&_capacity), flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} - /// A max flow algorithm is run. - /// \pre The flow have to satisfy the requirements - /// stated in fe. + ///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); } - /// A preflow algorithm is run. - /// \pre The initial edge-map have to be a - /// zero flow if \c fe is \c ZERO_FLOW, - /// a flow if \c fe is \c GEN_FLOW, - /// a pre-flow if fe is \c PRE_FLOW and - /// anything if fe is NO_FLOW. + + ///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) { - preflowPhase0(fe); - preflowPhase1(); + 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. - /// Run the first phase of preflow, starting from a 0 flow, from a flow, - /// or from a preflow, of from undefined value according to \c fe. - void preflowPhase0(flowEnum fe); + ///Runs the first phase of the preflow algorithm. - /// Second phase of preflow. - void preflowPhase1(); + ///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 @@ -169,17 +202,27 @@ /// The return value shows if the augmentation was succesful. bool augmentOnBlockingFlow2(); - /// Returns the actual flow value. - /// More precisely, it returns the negative excess of s, thus - /// this works also for preflows. + /// 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() { 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 } - /// Should be used between preflowPhase0 and preflowPhase1. + ///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 @@ -196,9 +239,13 @@ } } - /// The unique inclusionwise minimum cut is computed by - /// processing a bfs from s in the residual graph. - /// \pre flow have to be a max flow otherwise it will the whole node-set. + ///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) { @@ -231,10 +278,13 @@ } } + ///Returns the inclusionwise maximum of the minimum value cuts. - /// The unique inclusionwise maximum cut is computed by - /// processing a reverse bfs from t in the residual graph. - /// \pre flow have to be a max flow otherwise it will be empty. + ///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) { @@ -272,20 +322,36 @@ } } + ///Returns a minimum value cut. - /// A minimum cut is computed. + ///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) { minMinCut(M); } - /// + ///Resets the source node to \c _s. + + ///Resets the source node to \c _s. + /// void resetSource(Node _s) { s=_s; } + + ///Resets the target node to \c _t. + + ///Resets the target node to \c _t. /// void resetTarget(Node _t) { t=_t; } - /// capacity-map is changed. + /// 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; } - /// flow-map is changed. + /// Resets the edge map of the flows to _flow. + + /// Resets the edge map of the flows to _flow. + /// void resetFlow(FlowMap& _flow) { flow=&_flow; } @@ -374,6 +440,7 @@ 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. @@ -586,7 +653,7 @@ template - void MaxFlow::preflowPhase0( flowEnum fe ) + void MaxFlow::preflowPhase1( flowEnum fe ) { int heur0=(int)(H0*n); //time while running 'bound decrease' @@ -615,10 +682,14 @@ for(g->first(v); g->valid(v); g->next(v)) level.set(v,n); //setting each node to level n - switch (fe) { + 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: { - //computing the excess NodeIt v; for(g->first(v); g->valid(v); g->next(v)) { Num exc=0; @@ -638,19 +709,24 @@ } case GEN_FLOW: { - //computing the excess of t + 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; } - default:; + 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); @@ -695,7 +771,7 @@ template - void MaxFlow::preflowPhase1() + void MaxFlow::preflowPhase2() { int k=n-2; //bound on the highest level under n containing a node