Almost full documentation added, NO_FLOW incorporated, Phase0(1) changed to Phase1(2)
1.1 --- a/src/work/jacint/max_flow.h Thu May 13 10:29:19 2004 +0000
1.2 +++ b/src/work/jacint/max_flow.h Thu May 13 10:30:20 2004 +0000
1.3 @@ -1,38 +1,4 @@
1.4 // -*- C++ -*-
1.5 -
1.6 -/*
1.7 - Heuristics:
1.8 - 2 phase
1.9 - gap
1.10 - list 'level_list' on the nodes on level i implemented by hand
1.11 - stack 'active' on the active nodes on level i
1.12 - runs heuristic 'highest label' for H1*n relabels
1.13 - runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
1.14 -
1.15 - Parameters H0 and H1 are initialized to 20 and 1.
1.16 -
1.17 - Constructors:
1.18 -
1.19 - Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
1.20 - FlowMap is not constant zero, and should be true if it is
1.21 -
1.22 - Members:
1.23 -
1.24 - void run()
1.25 -
1.26 - Num flowValue() : returns the value of a maximum flow
1.27 -
1.28 - void minMinCut(CutMap& M) : sets M to the characteristic vector of the
1.29 - minimum min cut. M should be a map of bools initialized to false. ??Is it OK?
1.30 -
1.31 - void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
1.32 - maximum min cut. M should be a map of bools initialized to false.
1.33 -
1.34 - void minCut(CutMap& M) : sets M to the characteristic vector of
1.35 - a min cut. M should be a map of bools initialized to false.
1.36 -
1.37 -*/
1.38 -
1.39 #ifndef HUGO_MAX_FLOW_H
1.40 #define HUGO_MAX_FLOW_H
1.41
1.42 @@ -47,15 +13,35 @@
1.43 #include <for_each_macros.h>
1.44
1.45 /// \file
1.46 -/// \brief Maximum flows.
1.47 +/// \brief Maximum flow algorithms.
1.48 /// \ingroup galgs
1.49
1.50 namespace hugo {
1.51
1.52 + /// \addtogroup galgs
1.53 + /// @{
1.54 + ///Maximum flow algorithms class.
1.55
1.56 - // ///\author Marton Makai, Jacint Szabo
1.57 - /// A class for computing max flows and related quantities.
1.58 - /// \ingroup galgs
1.59 + ///This class provides various algorithms for finding a flow of
1.60 + ///maximum value in a directed graph. The \e source node, the \e
1.61 + ///target node, the \e capacity of the edges and the \e starting \e
1.62 + ///flow value of the edges can be passed to the algorithm through the
1.63 + ///constructor. It is possible to change these quantities using the
1.64 + ///functions \ref resetSource, \ref resetTarget, \ref resetCap and
1.65 + ///\ref resetFlow. Before any subsequent runs of any algorithm of
1.66 + ///the class \ref resetFlow should be called, otherwise it will
1.67 + ///start from a maximum flow.
1.68 + ///After running an algorithm of the class, the maximum value of a
1.69 + ///value can be obtained by calling \ref flowValue(). The minimum
1.70 + ///value cut can be written into a \c node map of \c bools by
1.71 + ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes
1.72 + ///the inclusionwise minimum and maximum of the minimum value
1.73 + ///cuts, resp.)
1.74 + ///\param Graph The undirected graph type the algorithm runs on.
1.75 + ///\param Num The number type of the capacities and the flow values.
1.76 + ///\param CapMap The type of the capacity map.
1.77 + ///\param FlowMap The type of the flow map.
1.78 + ///\author Marton Makai, Jacint Szabo
1.79 template <typename Graph, typename Num,
1.80 typename CapMap=typename Graph::template EdgeMap<Num>,
1.81 typename FlowMap=typename Graph::template EdgeMap<Num> >
1.82 @@ -63,6 +49,7 @@
1.83 protected:
1.84 typedef typename Graph::Node Node;
1.85 typedef typename Graph::NodeIt NodeIt;
1.86 + typedef typename Graph::EdgeIt EdgeIt;
1.87 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.88 typedef typename Graph::InEdgeIt InEdgeIt;
1.89
1.90 @@ -81,13 +68,18 @@
1.91 typedef typename ResGW::Edge ResGWEdge;
1.92 //typedef typename ResGW::template NodeMap<bool> ReachedMap;
1.93 typedef typename Graph::template NodeMap<int> ReachedMap;
1.94 +
1.95 +
1.96 + //level works as a bool map in augmenting path algorithms and is
1.97 + //used by bfs for storing reached information. In preflow, it
1.98 + //shows the levels of nodes.
1.99 ReachedMap level;
1.100 - //level works as a bool map in augmenting path algorithms
1.101 - //and is used by bfs for storing reached information.
1.102 - //In preflow, it shows levels of nodes.
1.103 - //typename Graph::template NodeMap<int> level;
1.104 +
1.105 + //excess is needed only in preflow
1.106 typename Graph::template NodeMap<Num> excess;
1.107 - // protected:
1.108 +
1.109 + //fixme
1.110 +// protected:
1.111 // MaxFlow() { }
1.112 // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
1.113 // FlowMap& _flow)
1.114 @@ -108,12 +100,17 @@
1.115
1.116 public:
1.117
1.118 - ///\todo Document this.
1.119 - ///\todo Maybe, it should be PRE_FLOW instead.
1.120 - ///- \c NO_FLOW means nothing,
1.121 - ///- \c ZERO_FLOW means something,
1.122 - ///- \c GEN_FLOW means something else,
1.123 - ///- \c PRE_FLOW is something different.
1.124 + ///Indicates the property of the starting flow.
1.125 +
1.126 + ///Indicates the property of the starting flow. The meanings are as follows:
1.127 + ///- \c ZERO_FLOW: constant zero flow
1.128 + ///- \c GEN_FLOW: any flow, i.e. the sum of the in-flows equals to
1.129 + ///the sum of the out-flows in every node except the \e source and
1.130 + ///the \e target.
1.131 + ///- \c PRE_FLOW: any preflow, i.e. the sum of the in-flows is at
1.132 + ///least the sum of the out-flows in every node except the \e source.
1.133 + ///- \c NO_FLOW: indicates an unspecified edge map. \ref flow will be
1.134 + ///set to the constant zero flow in the beginning of the algorithm in this case.
1.135 enum flowEnum{
1.136 ZERO_FLOW,
1.137 GEN_FLOW,
1.138 @@ -126,30 +123,66 @@
1.139 g(&_G), s(_s), t(_t), capacity(&_capacity),
1.140 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
1.141
1.142 - /// A max flow algorithm is run.
1.143 - /// \pre The flow have to satisfy the requirements
1.144 - /// stated in fe.
1.145 + ///Runs a maximum flow algorithm.
1.146 +
1.147 + ///Runs a preflow algorithm, which is the fastest maximum flow
1.148 + ///algorithm up-to-date. The default for \c fe is ZERO_FLOW.
1.149 + ///\pre The starting flow must be
1.150 + /// - a constant zero flow if \c fe is \c ZERO_FLOW,
1.151 + /// - an arbitary flow if \c fe is \c GEN_FLOW,
1.152 + /// - an arbitary preflow if \c fe is \c PRE_FLOW,
1.153 + /// - any map if \c fe is NO_FLOW.
1.154 void run(flowEnum fe=ZERO_FLOW) {
1.155 preflow(fe);
1.156 }
1.157
1.158 - /// A preflow algorithm is run.
1.159 - /// \pre The initial edge-map have to be a
1.160 - /// zero flow if \c fe is \c ZERO_FLOW,
1.161 - /// a flow if \c fe is \c GEN_FLOW,
1.162 - /// a pre-flow if fe is \c PRE_FLOW and
1.163 - /// anything if fe is NO_FLOW.
1.164 +
1.165 + ///Runs a preflow algorithm.
1.166 +
1.167 + ///Runs a preflow algorithm. The preflow algorithms provide the
1.168 + ///fastest way to compute a maximum flow in a directed graph.
1.169 + ///\pre The starting flow must be
1.170 + /// - a constant zero flow if \c fe is \c ZERO_FLOW,
1.171 + /// - an arbitary flow if \c fe is \c GEN_FLOW,
1.172 + /// - an arbitary preflow if \c fe is \c PRE_FLOW,
1.173 + /// - any map if \c fe is NO_FLOW.
1.174 void preflow(flowEnum fe) {
1.175 - preflowPhase0(fe);
1.176 - preflowPhase1();
1.177 + preflowPhase1(fe);
1.178 + preflowPhase2();
1.179 }
1.180 + // Heuristics:
1.181 + // 2 phase
1.182 + // gap
1.183 + // list 'level_list' on the nodes on level i implemented by hand
1.184 + // stack 'active' on the active nodes on level i
1.185 + // runs heuristic 'highest label' for H1*n relabels
1.186 + // runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
1.187 + // Parameters H0 and H1 are initialized to 20 and 1.
1.188
1.189 - /// Run the first phase of preflow, starting from a 0 flow, from a flow,
1.190 - /// or from a preflow, of from undefined value according to \c fe.
1.191 - void preflowPhase0(flowEnum fe);
1.192 + ///Runs the first phase of the preflow algorithm.
1.193
1.194 - /// Second phase of preflow.
1.195 - void preflowPhase1();
1.196 + ///The preflow algorithm consists of two phases, this method runs the
1.197 + ///first phase. After the first phase the maximum flow value and a
1.198 + ///minimum value cut can already be computed, though a maximum flow
1.199 + ///is net yet obtained. So after calling this method \ref flowValue
1.200 + ///and \ref actMinCut gives proper results.
1.201 + ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not
1.202 + ///give minimum value cuts unless calling \ref preflowPhase2.
1.203 + ///\pre The starting flow must be
1.204 + /// - a constant zero flow if \c fe is \c ZERO_FLOW,
1.205 + /// - an arbitary flow if \c fe is \c GEN_FLOW,
1.206 + /// - an arbitary preflow if \c fe is \c PRE_FLOW,
1.207 + /// - any map if \c fe is NO_FLOW.
1.208 + void preflowPhase1( flowEnum fe );
1.209 +
1.210 + ///Runs the second phase of the preflow algorithm.
1.211 +
1.212 + ///The preflow algorithm consists of two phases, this method runs
1.213 + ///the second phase. After calling \ref preflowPhase1 and then
1.214 + ///\ref preflowPhase2 the methods \ref flowValue, \ref minCut,
1.215 + ///\ref minMinCut and \ref maxMinCut give proper results.
1.216 + ///\pre \ref preflowPhase1 must be called before.
1.217 + void preflowPhase2();
1.218
1.219 /// Starting from a flow, this method searches for an augmenting path
1.220 /// according to the Edmonds-Karp algorithm
1.221 @@ -169,17 +202,27 @@
1.222 /// The return value shows if the augmentation was succesful.
1.223 bool augmentOnBlockingFlow2();
1.224
1.225 - /// Returns the actual flow value.
1.226 - /// More precisely, it returns the negative excess of s, thus
1.227 - /// this works also for preflows.
1.228 + /// Returns the maximum value of a flow.
1.229 +
1.230 + /// Returns the maximum value of a flow, by counting the
1.231 + /// over-flow of the target node \ref t.
1.232 + /// It can be called already after running \ref preflowPhase1.
1.233 Num flowValue() {
1.234 Num a=0;
1.235 FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
1.236 FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
1.237 return a;
1.238 + //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
1.239 }
1.240
1.241 - /// Should be used between preflowPhase0 and preflowPhase1.
1.242 + ///Returns a minimum value cut after calling \ref preflowPhase1.
1.243 +
1.244 + ///After the first phase of the preflow algorithm the maximum flow
1.245 + ///value and a minimum value cut can already be computed. This
1.246 + ///method can be called after running \ref preflowPhase1 for
1.247 + ///obtaining a minimum value cut.
1.248 + /// \warning Gives proper result only right after calling \ref
1.249 + /// preflowPhase1.
1.250 /// \todo We have to make some status variable which shows the
1.251 /// actual state
1.252 /// of the class. This enables us to determine which methods are valid
1.253 @@ -196,9 +239,13 @@
1.254 }
1.255 }
1.256
1.257 - /// The unique inclusionwise minimum cut is computed by
1.258 - /// processing a bfs from s in the residual graph.
1.259 - /// \pre flow have to be a max flow otherwise it will the whole node-set.
1.260 + ///Returns the inclusionwise minimum of the minimum value cuts.
1.261 +
1.262 + ///Sets \c M to the characteristic vector of the minimum value cut
1.263 + ///which is inclusionwise minimum. It is computed by processing
1.264 + ///a bfs from the source node \c s in the residual graph.
1.265 + ///\pre M should be a node map of bools initialized to false.
1.266 + ///\pre \c flow must be a maximum flow.
1.267 template<typename _CutMap>
1.268 void minMinCut(_CutMap& M) {
1.269
1.270 @@ -231,10 +278,13 @@
1.271 }
1.272 }
1.273
1.274 + ///Returns the inclusionwise maximum of the minimum value cuts.
1.275
1.276 - /// The unique inclusionwise maximum cut is computed by
1.277 - /// processing a reverse bfs from t in the residual graph.
1.278 - /// \pre flow have to be a max flow otherwise it will be empty.
1.279 + ///Sets \c M to the characteristic vector of the minimum value cut
1.280 + ///which is inclusionwise maximum. It is computed by processing a
1.281 + ///backward bfs from the target node \c t in the residual graph.
1.282 + ///\pre M should be a node map of bools initialized to false.
1.283 + ///\pre \c flow must be a maximum flow.
1.284 template<typename _CutMap>
1.285 void maxMinCut(_CutMap& M) {
1.286
1.287 @@ -272,20 +322,36 @@
1.288 }
1.289 }
1.290
1.291 + ///Returns a minimum value cut.
1.292
1.293 - /// A minimum cut is computed.
1.294 + ///Sets \c M to the characteristic vector of a minimum value cut.
1.295 + ///\pre M should be a node map of bools initialized to false.
1.296 + ///\pre \c flow must be a maximum flow.
1.297 template<typename CutMap>
1.298 void minCut(CutMap& M) { minMinCut(M); }
1.299
1.300 - ///
1.301 + ///Resets the source node to \c _s.
1.302 +
1.303 + ///Resets the source node to \c _s.
1.304 + ///
1.305 void resetSource(Node _s) { s=_s; }
1.306 +
1.307 + ///Resets the target node to \c _t.
1.308 +
1.309 + ///Resets the target node to \c _t.
1.310 ///
1.311 void resetTarget(Node _t) { t=_t; }
1.312
1.313 - /// capacity-map is changed.
1.314 + /// Resets the edge map of the capacities to _cap.
1.315 +
1.316 + /// Resets the edge map of the capacities to _cap.
1.317 + ///
1.318 void resetCap(const CapMap& _cap) { capacity=&_cap; }
1.319
1.320 - /// flow-map is changed.
1.321 + /// Resets the edge map of the flows to _flow.
1.322 +
1.323 + /// Resets the edge map of the flows to _flow.
1.324 + ///
1.325 void resetFlow(FlowMap& _flow) { flow=&_flow; }
1.326
1.327
1.328 @@ -374,6 +440,7 @@
1.329 std::queue<Node> bfs_queue;
1.330
1.331 switch (fe) {
1.332 + case NO_FLOW: //flow is already set to const zero in this case
1.333 case ZERO_FLOW:
1.334 {
1.335 //Reverse_bfs from t, to find the starting level.
1.336 @@ -586,7 +653,7 @@
1.337
1.338
1.339 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
1.340 - void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
1.341 + void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1( flowEnum fe )
1.342 {
1.343
1.344 int heur0=(int)(H0*n); //time while running 'bound decrease'
1.345 @@ -615,10 +682,14 @@
1.346 for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
1.347 //setting each node to level n
1.348
1.349 - switch (fe) {
1.350 + if ( fe == NO_FLOW ) {
1.351 + EdgeIt e;
1.352 + for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
1.353 + }
1.354 +
1.355 + switch (fe) { //computing the excess
1.356 case PRE_FLOW:
1.357 {
1.358 - //computing the excess
1.359 NodeIt v;
1.360 for(g->first(v); g->valid(v); g->next(v)) {
1.361 Num exc=0;
1.362 @@ -638,19 +709,24 @@
1.363 }
1.364 case GEN_FLOW:
1.365 {
1.366 - //computing the excess of t
1.367 + NodeIt v;
1.368 + for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
1.369 +
1.370 Num exc=0;
1.371 -
1.372 InEdgeIt e;
1.373 for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.374 OutEdgeIt f;
1.375 for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.376 -
1.377 excess.set(t,exc);
1.378 -
1.379 break;
1.380 }
1.381 - default:;
1.382 + case ZERO_FLOW:
1.383 + case NO_FLOW:
1.384 + {
1.385 + NodeIt v;
1.386 + for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
1.387 + break;
1.388 + }
1.389 }
1.390
1.391 preflowPreproc(fe, active, level_list, left, right);
1.392 @@ -695,7 +771,7 @@
1.393
1.394
1.395 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
1.396 - void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
1.397 + void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase2()
1.398 {
1.399
1.400 int k=n-2; //bound on the highest level under n containing a node