1.1 --- a/src/work/Doxyfile Tue May 11 19:38:00 2004 +0000
1.2 +++ b/src/work/Doxyfile Tue May 11 19:50:21 2004 +0000
1.3 @@ -394,7 +394,6 @@
1.4 INPUT = ../hugo \
1.5 ../hugo/skeletons \
1.6 ../test/test_tools.h \
1.7 - athos/minlengthpaths.h \
1.8 klao/path.h \
1.9 jacint/max_flow.h \
1.10 jacint/max_matching.h \
2.1 --- a/src/work/jacint/max_flow.h Tue May 11 19:38:00 2004 +0000
2.2 +++ b/src/work/jacint/max_flow.h Tue May 11 19:50:21 2004 +0000
2.3 @@ -1,19 +1,19 @@
2.4 // -*- C++ -*-
2.5
2.6 /*
2.7 - Heuristics:
2.8 + Heuristics:
2.9 2 phase
2.10 gap
2.11 list 'level_list' on the nodes on level i implemented by hand
2.12 stack 'active' on the active nodes on level i
2.13 runs heuristic 'highest label' for H1*n relabels
2.14 runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
2.15 -
2.16 +
2.17 Parameters H0 and H1 are initialized to 20 and 1.
2.18
2.19 Constructors:
2.20
2.21 - Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
2.22 + Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
2.23 FlowMap is not constant zero, and should be true if it is
2.24
2.25 Members:
2.26 @@ -22,13 +22,13 @@
2.27
2.28 Num flowValue() : returns the value of a maximum flow
2.29
2.30 - void minMinCut(CutMap& M) : sets M to the characteristic vector of the
2.31 + void minMinCut(CutMap& M) : sets M to the characteristic vector of the
2.32 minimum min cut. M should be a map of bools initialized to false. ??Is it OK?
2.33
2.34 - void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
2.35 + void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
2.36 maximum min cut. M should be a map of bools initialized to false.
2.37
2.38 - void minCut(CutMap& M) : sets M to the characteristic vector of
2.39 + void minCut(CutMap& M) : sets M to the characteristic vector of
2.40 a min cut. M should be a map of bools initialized to false.
2.41
2.42 */
2.43 @@ -36,9 +36,6 @@
2.44 #ifndef HUGO_MAX_FLOW_H
2.45 #define HUGO_MAX_FLOW_H
2.46
2.47 -#define H0 20
2.48 -#define H1 1
2.49 -
2.50 #include <vector>
2.51 #include <queue>
2.52 #include <stack>
2.53 @@ -50,18 +47,20 @@
2.54 #include <for_each_macros.h>
2.55
2.56 /// \file
2.57 -/// \brief Dimacs file format reader.
2.58 +/// \brief Maximum flows.
2.59 +/// \ingroup galgs
2.60
2.61 namespace hugo {
2.62
2.63
2.64 // ///\author Marton Makai, Jacint Szabo
2.65 /// A class for computing max flows and related quantities.
2.66 - template <typename Graph, typename Num,
2.67 - typename CapMap=typename Graph::template EdgeMap<Num>,
2.68 + /// \ingroup galgs
2.69 + template <typename Graph, typename Num,
2.70 + typename CapMap=typename Graph::template EdgeMap<Num>,
2.71 typename FlowMap=typename Graph::template EdgeMap<Num> >
2.72 class MaxFlow {
2.73 -
2.74 + protected:
2.75 typedef typename Graph::Node Node;
2.76 typedef typename Graph::NodeIt NodeIt;
2.77 typedef typename Graph::OutEdgeIt OutEdgeIt;
2.78 @@ -74,7 +73,7 @@
2.79 const Graph* g;
2.80 Node s;
2.81 Node t;
2.82 - const CapMap* capacity;
2.83 + const CapMap* capacity;
2.84 FlowMap* flow;
2.85 int n; //the number of nodes of G
2.86 typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
2.87 @@ -83,98 +82,107 @@
2.88 //typedef typename ResGW::template NodeMap<bool> ReachedMap;
2.89 typedef typename Graph::template NodeMap<int> ReachedMap;
2.90 ReachedMap level;
2.91 - //level works as a bool map in augmenting path algorithms
2.92 + //level works as a bool map in augmenting path algorithms
2.93 //and is used by bfs for storing reached information.
2.94 //In preflow, it shows levels of nodes.
2.95 - //typename Graph::template NodeMap<int> level;
2.96 - typename Graph::template NodeMap<Num> excess;
2.97 + //typename Graph::template NodeMap<int> level;
2.98 + typename Graph::template NodeMap<Num> excess;
2.99 // protected:
2.100 // MaxFlow() { }
2.101 - // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
2.102 - // FlowMap& _flow)
2.103 + // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
2.104 + // FlowMap& _flow)
2.105 // {
2.106 - // g=&_G;
2.107 - // s=_s;
2.108 - // t=_t;
2.109 + // g=&_G;
2.110 + // s=_s;
2.111 + // t=_t;
2.112 // capacity=&_capacity;
2.113 // flow=&_flow;
2.114 // n=_G.nodeNum;
2.115 - // level.set (_G); //kellene vmi ilyesmi fv
2.116 + // level.set (_G); //kellene vmi ilyesmi fv
2.117 // excess(_G,0); //itt is
2.118 // }
2.119
2.120 + // constants used for heuristics
2.121 + static const int H0=20;
2.122 + static const int H1=1;
2.123 +
2.124 public:
2.125 -
2.126 +
2.127 ///\todo Document this.
2.128 ///\todo Maybe, it should be PRE_FLOW instead.
2.129 + ///- \c NO_FLOW means nothing,
2.130 ///- \c ZERO_FLOW means something,
2.131 ///- \c GEN_FLOW means something else,
2.132 - ///- \c PREFLOW is something different.
2.133 + ///- \c PRE_FLOW is something different.
2.134 enum flowEnum{
2.135 - ZERO_FLOW=0,
2.136 - GEN_FLOW=1,
2.137 - PREFLOW=2
2.138 + ZERO_FLOW,
2.139 + GEN_FLOW,
2.140 + PRE_FLOW,
2.141 + NO_FLOW
2.142 };
2.143
2.144 - MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
2.145 + MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
2.146 FlowMap& _flow) :
2.147 - g(&_G), s(_s), t(_t), capacity(&_capacity),
2.148 + g(&_G), s(_s), t(_t), capacity(&_capacity),
2.149 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
2.150
2.151 /// A max flow algorithm is run.
2.152 - ///\pre the flow have to be 0 at the beginning.
2.153 - void run() {
2.154 - preflow(ZERO_FLOW);
2.155 + /// \pre The flow have to satisfy the requirements
2.156 + /// stated in fe.
2.157 + void run(flowEnum fe=ZERO_FLOW) {
2.158 + preflow(fe);
2.159 }
2.160 -
2.161 - /// A preflow algorithm is run.
2.162 - ///\pre The initial edge-map have to be a
2.163 +
2.164 + /// A preflow algorithm is run.
2.165 + /// \pre The initial edge-map have to be a
2.166 /// zero flow if \c fe is \c ZERO_FLOW,
2.167 - /// a flow if \c fe is \c GEN_FLOW,
2.168 - /// and a pre-flow it is \c PREFLOW.
2.169 + /// a flow if \c fe is \c GEN_FLOW,
2.170 + /// a pre-flow if fe is \c PRE_FLOW and
2.171 + /// anything if fe is NO_FLOW.
2.172 void preflow(flowEnum fe) {
2.173 preflowPhase0(fe);
2.174 preflowPhase1();
2.175 }
2.176
2.177 - /// Run the first phase of preflow, starting from a 0 flow, from a flow,
2.178 - /// or from a preflow, according to \c fe.
2.179 - void preflowPhase0( flowEnum fe );
2.180 + /// Run the first phase of preflow, starting from a 0 flow, from a flow,
2.181 + /// or from a preflow, of from undefined value according to \c fe.
2.182 + void preflowPhase0(flowEnum fe);
2.183
2.184 /// Second phase of preflow.
2.185 void preflowPhase1();
2.186
2.187 - /// Starting from a flow, this method searches for an augmenting path
2.188 - /// according to the Edmonds-Karp algorithm
2.189 - /// and augments the flow on if any.
2.190 + /// Starting from a flow, this method searches for an augmenting path
2.191 + /// according to the Edmonds-Karp algorithm
2.192 + /// and augments the flow on if any.
2.193 /// The return value shows if the augmentation was succesful.
2.194 bool augmentOnShortestPath();
2.195
2.196 - /// Starting from a flow, this method searches for an augmenting blockin
2.197 - /// flow according to Dinits' algorithm and augments the flow on if any.
2.198 - /// The blocking flow is computed in a physically constructed
2.199 + /// Starting from a flow, this method searches for an augmenting blocking
2.200 + /// flow according to Dinits' algorithm and augments the flow on if any.
2.201 + /// The blocking flow is computed in a physically constructed
2.202 /// residual graph of type \c Mutablegraph.
2.203 /// The return value show sif the augmentation was succesful.
2.204 template<typename MutableGraph> bool augmentOnBlockingFlow();
2.205
2.206 - /// The same as \c augmentOnBlockingFlow<MutableGraph> but the
2.207 + /// The same as \c augmentOnBlockingFlow<MutableGraph> but the
2.208 /// residual graph is not constructed physically.
2.209 /// The return value shows if the augmentation was succesful.
2.210 bool augmentOnBlockingFlow2();
2.211
2.212 /// Returns the actual flow value.
2.213 - /// More precisely, it returns the negative excess of s, thus
2.214 + /// More precisely, it returns the negative excess of s, thus
2.215 /// this works also for preflows.
2.216 - Num flowValue() {
2.217 + Num flowValue() {
2.218 Num a=0;
2.219 - FOR_EACH_INC_LOC(OutEdgeIt, e, *g, s) a+=(*flow)[e];
2.220 - FOR_EACH_INC_LOC(InEdgeIt, e, *g, s) a-=(*flow)[e];
2.221 + FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
2.222 + FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
2.223 return a;
2.224 }
2.225
2.226 /// Should be used between preflowPhase0 and preflowPhase1.
2.227 - ///\todo We have to make some status variable which shows the actual state
2.228 - /// of the class. This enables us to determine which methods are valid
2.229 + /// \todo We have to make some status variable which shows the
2.230 + /// actual state
2.231 + /// of the class. This enables us to determine which methods are valid
2.232 /// for MinCut computation
2.233 template<typename _CutMap>
2.234 void actMinCut(_CutMap& M) {
2.235 @@ -188,15 +196,15 @@
2.236 }
2.237 }
2.238
2.239 - /// The unique inclusionwise minimum cut is computed by
2.240 + /// The unique inclusionwise minimum cut is computed by
2.241 /// processing a bfs from s in the residual graph.
2.242 - ///\pre flow have to be a max flow otherwise it will the whole node-set.
2.243 + /// \pre flow have to be a max flow otherwise it will the whole node-set.
2.244 template<typename _CutMap>
2.245 void minMinCut(_CutMap& M) {
2.246 -
2.247 +
2.248 std::queue<Node> queue;
2.249 -
2.250 - M.set(s,true);
2.251 +
2.252 + M.set(s,true);
2.253 queue.push(s);
2.254
2.255 while (!queue.empty()) {
2.256 @@ -210,7 +218,7 @@
2.257 queue.push(v);
2.258 M.set(v, true);
2.259 }
2.260 - }
2.261 + }
2.262
2.263 InEdgeIt f;
2.264 for(g->first(f,w) ; g->valid(f); g->next(f)) {
2.265 @@ -219,14 +227,14 @@
2.266 queue.push(v);
2.267 M.set(v, true);
2.268 }
2.269 - }
2.270 + }
2.271 }
2.272 }
2.273
2.274
2.275 - /// The unique inclusionwise maximum cut is computed by
2.276 + /// The unique inclusionwise maximum cut is computed by
2.277 /// processing a reverse bfs from t in the residual graph.
2.278 - ///\pre flow have to be a max flow otherwise it will be empty.
2.279 + /// \pre flow have to be a max flow otherwise it will be empty.
2.280 template<typename _CutMap>
2.281 void maxMinCut(_CutMap& M) {
2.282
2.283 @@ -236,15 +244,14 @@
2.284 }
2.285
2.286 std::queue<Node> queue;
2.287 -
2.288 - M.set(t,false);
2.289 +
2.290 + M.set(t,false);
2.291 queue.push(t);
2.292
2.293 while (!queue.empty()) {
2.294 Node w=queue.front();
2.295 queue.pop();
2.296
2.297 -
2.298 InEdgeIt e;
2.299 for(g->first(e,w) ; g->valid(e); g->next(e)) {
2.300 Node v=g->tail(e);
2.301 @@ -253,7 +260,7 @@
2.302 M.set(v, false);
2.303 }
2.304 }
2.305 -
2.306 +
2.307 OutEdgeIt f;
2.308 for(g->first(f,w) ; g->valid(f); g->next(f)) {
2.309 Node v=g->head(f);
2.310 @@ -274,112 +281,111 @@
2.311 void resetSource(Node _s) { s=_s; }
2.312 ///
2.313 void resetTarget(Node _t) { t=_t; }
2.314 -
2.315 +
2.316 /// capacity-map is changed.
2.317 void resetCap(const CapMap& _cap) { capacity=&_cap; }
2.318 -
2.319 - /// flow-map is changed.
2.320 +
2.321 + /// flow-map is changed.
2.322 void resetFlow(FlowMap& _flow) { flow=&_flow; }
2.323
2.324
2.325 private:
2.326
2.327 int push(Node w, VecStack& active) {
2.328 -
2.329 +
2.330 int lev=level[w];
2.331 Num exc=excess[w];
2.332 int newlevel=n; //bound on the next level of w
2.333 -
2.334 +
2.335 OutEdgeIt e;
2.336 for(g->first(e,w); g->valid(e); g->next(e)) {
2.337 -
2.338 - if ( (*flow)[e] >= (*capacity)[e] ) continue;
2.339 - Node v=g->head(e);
2.340 -
2.341 +
2.342 + if ( (*flow)[e] >= (*capacity)[e] ) continue;
2.343 + Node v=g->head(e);
2.344 +
2.345 if( lev > level[v] ) { //Push is allowed now
2.346 -
2.347 +
2.348 if ( excess[v]<=0 && v!=t && v!=s ) {
2.349 int lev_v=level[v];
2.350 active[lev_v].push(v);
2.351 }
2.352 -
2.353 +
2.354 Num cap=(*capacity)[e];
2.355 Num flo=(*flow)[e];
2.356 Num remcap=cap-flo;
2.357 -
2.358 +
2.359 if ( remcap >= exc ) { //A nonsaturating push.
2.360 -
2.361 +
2.362 flow->set(e, flo+exc);
2.363 excess.set(v, excess[v]+exc);
2.364 exc=0;
2.365 - break;
2.366 -
2.367 + break;
2.368 +
2.369 } else { //A saturating push.
2.370 flow->set(e, cap);
2.371 excess.set(v, excess[v]+remcap);
2.372 exc-=remcap;
2.373 }
2.374 } else if ( newlevel > level[v] ) newlevel = level[v];
2.375 - } //for out edges wv
2.376 -
2.377 - if ( exc > 0 ) {
2.378 + } //for out edges wv
2.379 +
2.380 + if ( exc > 0 ) {
2.381 InEdgeIt e;
2.382 for(g->first(e,w); g->valid(e); g->next(e)) {
2.383 -
2.384 - if( (*flow)[e] <= 0 ) continue;
2.385 - Node v=g->tail(e);
2.386 -
2.387 +
2.388 + if( (*flow)[e] <= 0 ) continue;
2.389 + Node v=g->tail(e);
2.390 +
2.391 if( lev > level[v] ) { //Push is allowed now
2.392 -
2.393 +
2.394 if ( excess[v]<=0 && v!=t && v!=s ) {
2.395 int lev_v=level[v];
2.396 active[lev_v].push(v);
2.397 }
2.398 -
2.399 +
2.400 Num flo=(*flow)[e];
2.401 -
2.402 +
2.403 if ( flo >= exc ) { //A nonsaturating push.
2.404 -
2.405 +
2.406 flow->set(e, flo-exc);
2.407 excess.set(v, excess[v]+exc);
2.408 exc=0;
2.409 - break;
2.410 + break;
2.411 } else { //A saturating push.
2.412 -
2.413 +
2.414 excess.set(v, excess[v]+flo);
2.415 exc-=flo;
2.416 flow->set(e,0);
2.417 - }
2.418 + }
2.419 } else if ( newlevel > level[v] ) newlevel = level[v];
2.420 } //for in edges vw
2.421 -
2.422 +
2.423 } // if w still has excess after the out edge for cycle
2.424 -
2.425 +
2.426 excess.set(w, exc);
2.427 -
2.428 +
2.429 return newlevel;
2.430 }
2.431
2.432
2.433 - void preflowPreproc ( flowEnum fe, VecStack& active,
2.434 - VecNode& level_list, NNMap& left, NNMap& right )
2.435 + void preflowPreproc(flowEnum fe, VecStack& active,
2.436 + VecNode& level_list, NNMap& left, NNMap& right)
2.437 {
2.438 + std::queue<Node> bfs_queue;
2.439
2.440 - std::queue<Node> bfs_queue;
2.441 -
2.442 - switch ( fe ) {
2.443 - case ZERO_FLOW:
2.444 + switch (fe) {
2.445 + case ZERO_FLOW:
2.446 {
2.447 //Reverse_bfs from t, to find the starting level.
2.448 level.set(t,0);
2.449 bfs_queue.push(t);
2.450 -
2.451 +
2.452 while (!bfs_queue.empty()) {
2.453 -
2.454 - Node v=bfs_queue.front();
2.455 +
2.456 + Node v=bfs_queue.front();
2.457 bfs_queue.pop();
2.458 int l=level[v]+1;
2.459 -
2.460 +
2.461 InEdgeIt e;
2.462 for(g->first(e,v); g->valid(e); g->next(e)) {
2.463 Node w=g->tail(e);
2.464 @@ -393,37 +399,37 @@
2.465 }
2.466 }
2.467 }
2.468 -
2.469 +
2.470 //the starting flow
2.471 OutEdgeIt e;
2.472 - for(g->first(e,s); g->valid(e); g->next(e))
2.473 + for(g->first(e,s); g->valid(e); g->next(e))
2.474 {
2.475 Num c=(*capacity)[e];
2.476 if ( c <= 0 ) continue;
2.477 Node w=g->head(e);
2.478 - if ( level[w] < n ) {
2.479 + if ( level[w] < n ) {
2.480 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
2.481 - flow->set(e, c);
2.482 + flow->set(e, c);
2.483 excess.set(w, excess[w]+c);
2.484 }
2.485 }
2.486 break;
2.487 }
2.488 -
2.489 +
2.490 case GEN_FLOW:
2.491 - case PREFLOW:
2.492 + case PRE_FLOW:
2.493 {
2.494 - //Reverse_bfs from t in the residual graph,
2.495 + //Reverse_bfs from t in the residual graph,
2.496 //to find the starting level.
2.497 level.set(t,0);
2.498 bfs_queue.push(t);
2.499 -
2.500 +
2.501 while (!bfs_queue.empty()) {
2.502 -
2.503 - Node v=bfs_queue.front();
2.504 +
2.505 + Node v=bfs_queue.front();
2.506 bfs_queue.pop();
2.507 int l=level[v]+1;
2.508 -
2.509 +
2.510 InEdgeIt e;
2.511 for(g->first(e,v); g->valid(e); g->next(e)) {
2.512 if ( (*capacity)[e] <= (*flow)[e] ) continue;
2.513 @@ -437,7 +443,7 @@
2.514 level.set(w, l);
2.515 }
2.516 }
2.517 -
2.518 +
2.519 OutEdgeIt f;
2.520 for(g->first(f,v); g->valid(f); g->next(f)) {
2.521 if ( 0 >= (*flow)[f] ) continue;
2.522 @@ -452,70 +458,70 @@
2.523 }
2.524 }
2.525 }
2.526 -
2.527 -
2.528 +
2.529 +
2.530 //the starting flow
2.531 OutEdgeIt e;
2.532 - for(g->first(e,s); g->valid(e); g->next(e))
2.533 + for(g->first(e,s); g->valid(e); g->next(e))
2.534 {
2.535 Num rem=(*capacity)[e]-(*flow)[e];
2.536 if ( rem <= 0 ) continue;
2.537 Node w=g->head(e);
2.538 - if ( level[w] < n ) {
2.539 + if ( level[w] < n ) {
2.540 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
2.541 - flow->set(e, (*capacity)[e]);
2.542 + flow->set(e, (*capacity)[e]);
2.543 excess.set(w, excess[w]+rem);
2.544 }
2.545 }
2.546 -
2.547 +
2.548 InEdgeIt f;
2.549 - for(g->first(f,s); g->valid(f); g->next(f))
2.550 + for(g->first(f,s); g->valid(f); g->next(f))
2.551 {
2.552 if ( (*flow)[f] <= 0 ) continue;
2.553 Node w=g->tail(f);
2.554 - if ( level[w] < n ) {
2.555 + if ( level[w] < n ) {
2.556 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
2.557 excess.set(w, excess[w]+(*flow)[f]);
2.558 - flow->set(f, 0);
2.559 + flow->set(f, 0);
2.560 }
2.561 - }
2.562 + }
2.563 break;
2.564 - } //case PREFLOW
2.565 + } //case PRE_FLOW
2.566 }
2.567 } //preflowPreproc
2.568
2.569
2.570
2.571 - void relabel(Node w, int newlevel, VecStack& active,
2.572 - VecNode& level_list, NNMap& left,
2.573 - NNMap& right, int& b, int& k, bool what_heur )
2.574 + void relabel(Node w, int newlevel, VecStack& active,
2.575 + VecNode& level_list, NNMap& left,
2.576 + NNMap& right, int& b, int& k, bool what_heur )
2.577 {
2.578
2.579 - Num lev=level[w];
2.580 -
2.581 + Num lev=level[w];
2.582 +
2.583 Node right_n=right[w];
2.584 Node left_n=left[w];
2.585 -
2.586 +
2.587 //unlacing starts
2.588 if ( g->valid(right_n) ) {
2.589 if ( g->valid(left_n) ) {
2.590 right.set(left_n, right_n);
2.591 left.set(right_n, left_n);
2.592 } else {
2.593 - level_list[lev]=right_n;
2.594 + level_list[lev]=right_n;
2.595 left.set(right_n, INVALID);
2.596 - }
2.597 + }
2.598 } else {
2.599 if ( g->valid(left_n) ) {
2.600 right.set(left_n, INVALID);
2.601 - } else {
2.602 - level_list[lev]=INVALID;
2.603 - }
2.604 - }
2.605 + } else {
2.606 + level_list[lev]=INVALID;
2.607 + }
2.608 + }
2.609 //unlacing ends
2.610 -
2.611 +
2.612 if ( !g->valid(level_list[lev]) ) {
2.613 -
2.614 +
2.615 //gapping starts
2.616 for (int i=lev; i!=k ; ) {
2.617 Node v=level_list[++i];
2.618 @@ -528,17 +534,17 @@
2.619 while ( !active[i].empty() ) {
2.620 active[i].pop(); //FIXME: ezt szebben kene
2.621 }
2.622 - }
2.623 + }
2.624 }
2.625 -
2.626 +
2.627 level.set(w,n);
2.628 b=lev-1;
2.629 k=b;
2.630 //gapping ends
2.631 -
2.632 +
2.633 } else {
2.634 -
2.635 - if ( newlevel == n ) level.set(w,n);
2.636 +
2.637 + if ( newlevel == n ) level.set(w,n);
2.638 else {
2.639 level.set(w,++newlevel);
2.640 active[newlevel].push(w);
2.641 @@ -551,54 +557,55 @@
2.642 level_list[newlevel]=w;
2.643 }
2.644 }
2.645 -
2.646 +
2.647 } //relabel
2.648
2.649
2.650 - template<typename MapGraphWrapper>
2.651 + template<typename MapGraphWrapper>
2.652 class DistanceMap {
2.653 protected:
2.654 const MapGraphWrapper* g;
2.655 - typename MapGraphWrapper::template NodeMap<int> dist;
2.656 + typename MapGraphWrapper::template NodeMap<int> dist;
2.657 public:
2.658 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
2.659 - void set(const typename MapGraphWrapper::Node& n, int a) {
2.660 - dist.set(n, a);
2.661 + void set(const typename MapGraphWrapper::Node& n, int a) {
2.662 + dist.set(n, a);
2.663 }
2.664 - int operator[](const typename MapGraphWrapper::Node& n)
2.665 + int operator[](const typename MapGraphWrapper::Node& n)
2.666 { return dist[n]; }
2.667 - // int get(const typename MapGraphWrapper::Node& n) const {
2.668 + // int get(const typename MapGraphWrapper::Node& n) const {
2.669 // return dist[n]; }
2.670 - // bool get(const typename MapGraphWrapper::Edge& e) const {
2.671 + // bool get(const typename MapGraphWrapper::Edge& e) const {
2.672 // return (dist.get(g->tail(e))<dist.get(g->head(e))); }
2.673 - bool operator[](const typename MapGraphWrapper::Edge& e) const {
2.674 - return (dist[g->tail(e)]<dist[g->head(e)]);
2.675 + bool operator[](const typename MapGraphWrapper::Edge& e) const {
2.676 + return (dist[g->tail(e)]<dist[g->head(e)]);
2.677 }
2.678 };
2.679 -
2.680 +
2.681 };
2.682
2.683
2.684 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
2.685 - void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
2.686 + void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
2.687 {
2.688 -
2.689 - int heur0=(int)(H0*n); //time while running 'bound decrease'
2.690 +
2.691 + int heur0=(int)(H0*n); //time while running 'bound decrease'
2.692 int heur1=(int)(H1*n); //time while running 'highest label'
2.693 int heur=heur1; //starting time interval (#of relabels)
2.694 int numrelabel=0;
2.695 -
2.696 - bool what_heur=1;
2.697 +
2.698 + bool what_heur=1;
2.699 //It is 0 in case 'bound decrease' and 1 in case 'highest label'
2.700
2.701 - bool end=false;
2.702 - //Needed for 'bound decrease', true means no active nodes are above bound b.
2.703 + bool end=false;
2.704 + //Needed for 'bound decrease', true means no active nodes are above bound
2.705 + //b.
2.706
2.707 int k=n-2; //bound on the highest level under n containing a node
2.708 int b=k; //bound on the highest level under n of an active node
2.709 -
2.710 +
2.711 VecStack active(n);
2.712 -
2.713 +
2.714 NNMap left(*g, INVALID);
2.715 NNMap right(*g, INVALID);
2.716 VecNode level_list(n,INVALID);
2.717 @@ -607,22 +614,22 @@
2.718 NodeIt v;
2.719 for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
2.720 //setting each node to level n
2.721 -
2.722 - switch ( fe ) {
2.723 - case PREFLOW:
2.724 +
2.725 + switch (fe) {
2.726 + case PRE_FLOW:
2.727 {
2.728 - //counting the excess
2.729 + //computing the excess
2.730 NodeIt v;
2.731 for(g->first(v); g->valid(v); g->next(v)) {
2.732 Num exc=0;
2.733 -
2.734 +
2.735 InEdgeIt e;
2.736 for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
2.737 OutEdgeIt f;
2.738 for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
2.739 -
2.740 - excess.set(v,exc);
2.741 -
2.742 +
2.743 + excess.set(v,exc);
2.744 +
2.745 //putting the active nodes into the stack
2.746 int lev=level[v];
2.747 if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
2.748 @@ -631,26 +638,25 @@
2.749 }
2.750 case GEN_FLOW:
2.751 {
2.752 - //Counting the excess of t
2.753 + //computing the excess of t
2.754 Num exc=0;
2.755 -
2.756 +
2.757 InEdgeIt e;
2.758 for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
2.759 OutEdgeIt f;
2.760 for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
2.761 -
2.762 - excess.set(t,exc);
2.763 -
2.764 +
2.765 + excess.set(t,exc);
2.766 +
2.767 break;
2.768 }
2.769 - default:
2.770 - break;
2.771 + default:;
2.772 }
2.773 -
2.774 - preflowPreproc( fe, active, level_list, left, right );
2.775 - //End of preprocessing
2.776 -
2.777 -
2.778 +
2.779 + preflowPreproc(fe, active, level_list, left, right);
2.780 + //End of preprocessing
2.781 +
2.782 +
2.783 //Push/relabel on the highest level active nodes.
2.784 while ( true ) {
2.785 if ( b == 0 ) {
2.786 @@ -659,17 +665,17 @@
2.787 end=true;
2.788 } else break;
2.789 }
2.790 -
2.791 - if ( active[b].empty() ) --b;
2.792 +
2.793 + if ( active[b].empty() ) --b;
2.794 else {
2.795 - end=false;
2.796 + end=false;
2.797 Node w=active[b].top();
2.798 active[b].pop();
2.799 int newlevel=push(w,active);
2.800 - if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
2.801 + if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
2.802 left, right, b, k, what_heur);
2.803 -
2.804 - ++numrelabel;
2.805 +
2.806 + ++numrelabel;
2.807 if ( numrelabel >= heur ) {
2.808 numrelabel=0;
2.809 if ( what_heur ) {
2.810 @@ -679,49 +685,49 @@
2.811 } else {
2.812 what_heur=1;
2.813 heur=heur1;
2.814 - b=k;
2.815 + b=k;
2.816 }
2.817 }
2.818 - }
2.819 - }
2.820 + }
2.821 + }
2.822 }
2.823
2.824
2.825
2.826 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
2.827 - void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
2.828 + void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
2.829 {
2.830 -
2.831 +
2.832 int k=n-2; //bound on the highest level under n containing a node
2.833 int b=k; //bound on the highest level under n of an active node
2.834 -
2.835 +
2.836 VecStack active(n);
2.837 level.set(s,0);
2.838 std::queue<Node> bfs_queue;
2.839 bfs_queue.push(s);
2.840 -
2.841 +
2.842 while (!bfs_queue.empty()) {
2.843 -
2.844 - Node v=bfs_queue.front();
2.845 +
2.846 + Node v=bfs_queue.front();
2.847 bfs_queue.pop();
2.848 int l=level[v]+1;
2.849 -
2.850 +
2.851 InEdgeIt e;
2.852 for(g->first(e,v); g->valid(e); g->next(e)) {
2.853 if ( (*capacity)[e] <= (*flow)[e] ) continue;
2.854 Node u=g->tail(e);
2.855 - if ( level[u] >= n ) {
2.856 + if ( level[u] >= n ) {
2.857 bfs_queue.push(u);
2.858 level.set(u, l);
2.859 if ( excess[u] > 0 ) active[l].push(u);
2.860 }
2.861 }
2.862 -
2.863 +
2.864 OutEdgeIt f;
2.865 for(g->first(f,v); g->valid(f); g->next(f)) {
2.866 if ( 0 >= (*flow)[f] ) continue;
2.867 Node u=g->head(f);
2.868 - if ( level[u] >= n ) {
2.869 + if ( level[u] >= n ) {
2.870 bfs_queue.push(u);
2.871 level.set(u, l);
2.872 if ( excess[u] > 0 ) active[l].push(u);
2.873 @@ -731,14 +737,14 @@
2.874 b=n-2;
2.875
2.876 while ( true ) {
2.877 -
2.878 +
2.879 if ( b == 0 ) break;
2.880
2.881 - if ( active[b].empty() ) --b;
2.882 + if ( active[b].empty() ) --b;
2.883 else {
2.884 Node w=active[b].top();
2.885 active[b].pop();
2.886 - int newlevel=push(w,active);
2.887 + int newlevel=push(w,active);
2.888
2.889 //relabel
2.890 if ( excess[w] > 0 ) {
2.891 @@ -753,23 +759,23 @@
2.892
2.893
2.894 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
2.895 - bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
2.896 + bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
2.897 {
2.898 ResGW res_graph(*g, *capacity, *flow);
2.899 bool _augment=false;
2.900 -
2.901 +
2.902 //ReachedMap level(res_graph);
2.903 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.904 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.905 bfs.pushAndSetReached(s);
2.906 -
2.907 - typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
2.908 +
2.909 + typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
2.910 pred.set(s, INVALID);
2.911 -
2.912 +
2.913 typename ResGW::template NodeMap<Num> free(res_graph);
2.914 -
2.915 +
2.916 //searching for augmenting path
2.917 - while ( !bfs.finished() ) {
2.918 + while ( !bfs.finished() ) {
2.919 ResGWOutEdgeIt e=bfs;
2.920 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.921 Node v=res_graph.tail(e);
2.922 @@ -778,20 +784,20 @@
2.923 if (res_graph.valid(pred[v])) {
2.924 free.set(w, std::min(free[v], res_graph.resCap(e)));
2.925 } else {
2.926 - free.set(w, res_graph.resCap(e));
2.927 + free.set(w, res_graph.resCap(e));
2.928 }
2.929 if (res_graph.head(e)==t) { _augment=true; break; }
2.930 }
2.931 -
2.932 +
2.933 ++bfs;
2.934 } //end of searching augmenting path
2.935
2.936 if (_augment) {
2.937 Node n=t;
2.938 Num augment_value=free[t];
2.939 - while (res_graph.valid(pred[n])) {
2.940 + while (res_graph.valid(pred[n])) {
2.941 ResGWEdge e=pred[n];
2.942 - res_graph.augment(e, augment_value);
2.943 + res_graph.augment(e, augment_value);
2.944 n=res_graph.tail(e);
2.945 }
2.946 }
2.947 @@ -805,12 +811,10 @@
2.948
2.949
2.950
2.951 -
2.952 -
2.953 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
2.954 - template<typename MutableGraph>
2.955 - bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
2.956 - {
2.957 + template<typename MutableGraph>
2.958 + bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
2.959 + {
2.960 typedef MutableGraph MG;
2.961 bool _augment=false;
2.962
2.963 @@ -821,13 +825,13 @@
2.964 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.965 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.966 bfs.pushAndSetReached(s);
2.967 - typename ResGW::template NodeMap<int>
2.968 + typename ResGW::template NodeMap<int>
2.969 dist(res_graph); //filled up with 0's
2.970
2.971 //F will contain the physical copy of the residual graph
2.972 //with the set of edges which are on shortest paths
2.973 MG F;
2.974 - typename ResGW::template NodeMap<typename MG::Node>
2.975 + typename ResGW::template NodeMap<typename MG::Node>
2.976 res_graph_to_F(res_graph);
2.977 {
2.978 typename ResGW::NodeIt n;
2.979 @@ -841,19 +845,21 @@
2.980 typename MG::template EdgeMap<ResGWEdge> original_edge(F);
2.981 typename MG::template EdgeMap<Num> residual_capacity(F);
2.982
2.983 - while ( !bfs.finished() ) {
2.984 + while ( !bfs.finished() ) {
2.985 ResGWOutEdgeIt e=bfs;
2.986 if (res_graph.valid(e)) {
2.987 if (bfs.isBNodeNewlyReached()) {
2.988 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.989 - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
2.990 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
2.991 + res_graph_to_F[res_graph.head(e)]);
2.992 original_edge.update();
2.993 original_edge.set(f, e);
2.994 residual_capacity.update();
2.995 residual_capacity.set(f, res_graph.resCap(e));
2.996 } else {
2.997 if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
2.998 - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
2.999 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
2.1000 + res_graph_to_F[res_graph.head(e)]);
2.1001 original_edge.update();
2.1002 original_edge.set(f, e);
2.1003 residual_capacity.update();
2.1004 @@ -876,7 +882,7 @@
2.1005
2.1006 typename MG::template NodeMap<Num> free(F);
2.1007
2.1008 - dfs.pushAndSetReached(sF);
2.1009 + dfs.pushAndSetReached(sF);
2.1010 while (!dfs.finished()) {
2.1011 ++dfs;
2.1012 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
2.1013 @@ -887,58 +893,56 @@
2.1014 if (F.valid(pred[v])) {
2.1015 free.set(w, std::min(free[v], residual_capacity[dfs]));
2.1016 } else {
2.1017 - free.set(w, residual_capacity[dfs]);
2.1018 + free.set(w, residual_capacity[dfs]);
2.1019 }
2.1020 - if (w==tF) {
2.1021 - __augment=true;
2.1022 + if (w==tF) {
2.1023 + __augment=true;
2.1024 _augment=true;
2.1025 - break;
2.1026 + break;
2.1027 }
2.1028 -
2.1029 +
2.1030 } else {
2.1031 F.erase(/*typename MG::OutEdgeIt*/(dfs));
2.1032 }
2.1033 - }
2.1034 + }
2.1035 }
2.1036
2.1037 if (__augment) {
2.1038 typename MG::Node n=tF;
2.1039 Num augment_value=free[tF];
2.1040 - while (F.valid(pred[n])) {
2.1041 + while (F.valid(pred[n])) {
2.1042 typename MG::Edge e=pred[n];
2.1043 - res_graph.augment(original_edge[e], augment_value);
2.1044 + res_graph.augment(original_edge[e], augment_value);
2.1045 n=F.tail(e);
2.1046 - if (residual_capacity[e]==augment_value)
2.1047 - F.erase(e);
2.1048 - else
2.1049 + if (residual_capacity[e]==augment_value)
2.1050 + F.erase(e);
2.1051 + else
2.1052 residual_capacity.set(e, residual_capacity[e]-augment_value);
2.1053 }
2.1054 }
2.1055 -
2.1056 +
2.1057 }
2.1058 -
2.1059 +
2.1060 return _augment;
2.1061 }
2.1062
2.1063
2.1064
2.1065
2.1066 -
2.1067 -
2.1068 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
2.1069 - bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
2.1070 + bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
2.1071 {
2.1072 bool _augment=false;
2.1073
2.1074 ResGW res_graph(*g, *capacity, *flow);
2.1075 -
2.1076 +
2.1077 //ReachedMap level(res_graph);
2.1078 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.1079 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.1080
2.1081 bfs.pushAndSetReached(s);
2.1082 DistanceMap<ResGW> dist(res_graph);
2.1083 - while ( !bfs.finished() ) {
2.1084 + while ( !bfs.finished() ) {
2.1085 ResGWOutEdgeIt e=bfs;
2.1086 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.1087 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.1088 @@ -948,17 +952,17 @@
2.1089
2.1090 //Subgraph containing the edges on some shortest paths
2.1091 ConstMap<typename ResGW::Node, bool> true_map(true);
2.1092 - typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
2.1093 + typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
2.1094 DistanceMap<ResGW> > FilterResGW;
2.1095 FilterResGW filter_res_graph(res_graph, true_map, dist);
2.1096
2.1097 - //Subgraph, which is able to delete edges which are already
2.1098 + //Subgraph, which is able to delete edges which are already
2.1099 //met by the dfs
2.1100 - typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
2.1101 + typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
2.1102 first_out_edges(filter_res_graph);
2.1103 typename FilterResGW::NodeIt v;
2.1104 - for(filter_res_graph.first(v); filter_res_graph.valid(v);
2.1105 - filter_res_graph.next(v))
2.1106 + for(filter_res_graph.first(v); filter_res_graph.valid(v);
2.1107 + filter_res_graph.next(v))
2.1108 {
2.1109 typename FilterResGW::OutEdgeIt e;
2.1110 filter_res_graph.first(e, v);
2.1111 @@ -974,57 +978,60 @@
2.1112
2.1113 __augment=false;
2.1114 //computing blocking flow with dfs
2.1115 - DfsIterator< ErasingResGW,
2.1116 - typename ErasingResGW::template NodeMap<bool> >
2.1117 + DfsIterator< ErasingResGW,
2.1118 + typename ErasingResGW::template NodeMap<bool> >
2.1119 dfs(erasing_res_graph);
2.1120 typename ErasingResGW::
2.1121 - template NodeMap<typename ErasingResGW::OutEdgeIt>
2.1122 - pred(erasing_res_graph);
2.1123 + template NodeMap<typename ErasingResGW::OutEdgeIt>
2.1124 + pred(erasing_res_graph);
2.1125 pred.set(s, INVALID);
2.1126 //invalid iterators for sources
2.1127
2.1128 - typename ErasingResGW::template NodeMap<Num>
2.1129 + typename ErasingResGW::template NodeMap<Num>
2.1130 free1(erasing_res_graph);
2.1131
2.1132 - dfs.pushAndSetReached(
2.1133 - typename ErasingResGW::Node(
2.1134 - typename FilterResGW::Node(
2.1135 - typename ResGW::Node(s)
2.1136 - )
2.1137 - )
2.1138 - );
2.1139 + dfs.pushAndSetReached
2.1140 + ///\bug hugo 0.2
2.1141 + (typename ErasingResGW::Node
2.1142 + (typename FilterResGW::Node
2.1143 + (typename ResGW::Node(s)
2.1144 + )
2.1145 + )
2.1146 + );
2.1147 while (!dfs.finished()) {
2.1148 ++dfs;
2.1149 - if (erasing_res_graph.valid(
2.1150 - typename ErasingResGW::OutEdgeIt(dfs)))
2.1151 - {
2.1152 + if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs)))
2.1153 + {
2.1154 if (dfs.isBNodeNewlyReached()) {
2.1155 -
2.1156 +
2.1157 typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
2.1158 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
2.1159
2.1160 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
2.1161 if (erasing_res_graph.valid(pred[v])) {
2.1162 - free1.set(w, std::min(free1[v], res_graph.resCap(
2.1163 - typename ErasingResGW::OutEdgeIt(dfs))));
2.1164 + free1.set
2.1165 + (w, std::min(free1[v], res_graph.resCap
2.1166 + (typename ErasingResGW::OutEdgeIt(dfs))));
2.1167 } else {
2.1168 - free1.set(w, res_graph.resCap(
2.1169 - typename ErasingResGW::OutEdgeIt(dfs)));
2.1170 + free1.set
2.1171 + (w, res_graph.resCap
2.1172 + (typename ErasingResGW::OutEdgeIt(dfs)));
2.1173 }
2.1174 -
2.1175 - if (w==t) {
2.1176 - __augment=true;
2.1177 +
2.1178 + if (w==t) {
2.1179 + __augment=true;
2.1180 _augment=true;
2.1181 - break;
2.1182 + break;
2.1183 }
2.1184 } else {
2.1185 erasing_res_graph.erase(dfs);
2.1186 }
2.1187 }
2.1188 - }
2.1189 + }
2.1190
2.1191 if (__augment) {
2.1192 - typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
2.1193 + typename ErasingResGW::Node
2.1194 + n=typename FilterResGW::Node(typename ResGW::Node(t));
2.1195 // typename ResGW::NodeMap<Num> a(res_graph);
2.1196 // typename ResGW::Node b;
2.1197 // Num j=a[b];
2.1198 @@ -1035,7 +1042,7 @@
2.1199 // typename ErasingResGW::Node b2;
2.1200 // Num j2=a2[b2];
2.1201 Num augment_value=free1[n];
2.1202 - while (erasing_res_graph.valid(pred[n])) {
2.1203 + while (erasing_res_graph.valid(pred[n])) {
2.1204 typename ErasingResGW::OutEdgeIt e=pred[n];
2.1205 res_graph.augment(e, augment_value);
2.1206 n=erasing_res_graph.tail(e);
2.1207 @@ -1043,15 +1050,13 @@
2.1208 erasing_res_graph.erase(e);
2.1209 }
2.1210 }
2.1211 -
2.1212 - } //while (__augment)
2.1213 -
2.1214 +
2.1215 + } //while (__augment)
2.1216 +
2.1217 return _augment;
2.1218 }
2.1219
2.1220
2.1221 -
2.1222 -
2.1223 } //namespace hugo
2.1224
2.1225 #endif //HUGO_MAX_FLOW_H
3.1 --- a/src/work/marci/bfs_dfs.h Tue May 11 19:38:00 2004 +0000
3.2 +++ b/src/work/marci/bfs_dfs.h Tue May 11 19:50:21 2004 +0000
3.3 @@ -2,13 +2,13 @@
3.4 #ifndef HUGO_BFS_DFS_H
3.5 #define HUGO_BFS_DFS_H
3.6
3.7 -// ///\ingroup gwrappers
3.8 -///\file
3.9 -///\brief Bfs and dfs iterators.
3.10 +/// \ingroup galgs
3.11 +/// \file
3.12 +/// \brief Bfs and dfs iterators.
3.13 ///
3.14 -///This file contains bfs and dfs iterator classes.
3.15 +/// This file contains bfs and dfs iterator classes.
3.16 ///
3.17 -// ///\author Marton Makai
3.18 +// /// \author Marton Makai
3.19
3.20 #include <queue>
3.21 #include <stack>
3.22 @@ -21,6 +21,7 @@
3.23 /// Bfs searches for the nodes wich are not marked in
3.24 /// \c reached_map
3.25 /// Reached have to work as read-write bool Node-map.
3.26 + /// \ingroup galgs
3.27 template <typename Graph, /*typename OutEdgeIt,*/
3.28 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
3.29 class BfsIterator {
3.30 @@ -105,33 +106,32 @@
3.31 }
3.32 return *this;
3.33 }
3.34 - ///
3.35 + /// Guess what?
3.36 bool finished() const { return bfs_queue.empty(); }
3.37 /// The conversion operator makes for converting the bfs-iterator
3.38 /// to an \c out-edge-iterator.
3.39 ///\bug Edge have to be in HUGO 0.2
3.40 operator OutEdgeIt() const { return actual_edge; }
3.41 - ///
3.42 + /// Guess what?
3.43 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.44 - ///
3.45 + /// Guess what?
3.46 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
3.47 - ///
3.48 + /// Guess what?
3.49 Node aNode() const { return bfs_queue.front(); }
3.50 - ///
3.51 + /// Guess what?
3.52 Node bNode() const { return graph->bNode(actual_edge); }
3.53 - ///
3.54 + /// Guess what?
3.55 const ReachedMap& getReachedMap() const { return reached; }
3.56 - ///
3.57 + /// Guess what?
3.58 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
3.59 - };
3.60 + };
3.61
3.62 /// Bfs searches for the nodes wich are not marked in
3.63 /// \c reached_map
3.64 /// Reached have to work as a read-write bool Node-map,
3.65 /// Pred is a write Edge Node-map and
3.66 - /// Dist is a read-write int Node-map, have to be.
3.67 - ///\todo In fact onsly simple operations requirement are needed for
3.68 - /// Dist::Value.
3.69 + /// Dist is a read-write Node-map of integral value, have to be.
3.70 + /// \ingroup galgs
3.71 template <typename Graph,
3.72 typename ReachedMap=typename Graph::template NodeMap<bool>,
3.73 typename PredMap
3.74 @@ -178,15 +178,16 @@
3.75 }
3.76 return *this;
3.77 }
3.78 - ///
3.79 + /// Guess what?
3.80 const PredMap& getPredMap() const { return pred; }
3.81 - ///
3.82 + /// Guess what?
3.83 const DistMap& getDistMap() const { return dist; }
3.84 };
3.85
3.86 /// Dfs searches for the nodes wich are not marked in
3.87 /// \c reached_map
3.88 /// Reached have to be a read-write bool Node-map.
3.89 + /// \ingroup galgs
3.90 template <typename Graph, /*typename OutEdgeIt,*/
3.91 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
3.92 class DfsIterator {
3.93 @@ -248,21 +249,21 @@
3.94 }
3.95 return *this;
3.96 }
3.97 - ///
3.98 + /// Guess what?
3.99 bool finished() const { return dfs_stack.empty(); }
3.100 - ///
3.101 + /// Guess what?
3.102 operator OutEdgeIt() const { return actual_edge; }
3.103 - ///
3.104 + /// Guess what?
3.105 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.106 - ///
3.107 + /// Guess what?
3.108 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
3.109 - ///
3.110 + /// Guess what?
3.111 Node aNode() const { return actual_node; /*FIXME*/}
3.112 - ///
3.113 + /// Guess what?
3.114 Node bNode() const { return graph->bNode(actual_edge); }
3.115 - ///
3.116 + /// Guess what?
3.117 const ReachedMap& getReachedMap() const { return reached; }
3.118 - ///
3.119 + /// Guess what?
3.120 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
3.121 };
3.122
3.123 @@ -270,6 +271,7 @@
3.124 /// \c reached_map
3.125 /// Reached is a read-write bool Node-map,
3.126 /// Pred is a write Node-map, have to be.
3.127 + /// \ingroup galgs
3.128 template <typename Graph,
3.129 typename ReachedMap=typename Graph::template NodeMap<bool>,
3.130 typename PredMap
3.131 @@ -312,7 +314,7 @@
3.132 }
3.133 return *this;
3.134 }
3.135 - ///
3.136 + /// Guess what?
3.137 const PredMap& getPredMap() const { return pred; }
3.138 };
3.139
4.1 --- a/src/work/marci/bfs_dfs_misc.h Tue May 11 19:38:00 2004 +0000
4.2 +++ b/src/work/marci/bfs_dfs_misc.h Tue May 11 19:50:21 2004 +0000
4.3 @@ -2,11 +2,11 @@
4.4 #ifndef HUGO_BFS_DFS_MISC_H
4.5 #define HUGO_BFS_DFS_MISC_H
4.6
4.7 -// ///\ingroup gwrappers
4.8 -///\file
4.9 -///\brief Miscellaneous algorithms using bfs and dfs.
4.10 +/// \ingroup galgs
4.11 +/// \file
4.12 +/// \brief Miscellaneous algorithms using bfs and dfs.
4.13 ///
4.14 -///This file contains several algorithms using bfs and dfs.
4.15 +/// This file contains several algorithms using bfs and dfs.
4.16 ///
4.17 // ///\author Marton Makai
4.18
4.19 @@ -15,10 +15,11 @@
4.20
4.21 namespace hugo {
4.22
4.23 - /// This function eat a read-write \c BoolMap& bool_map,
4.24 + /// This function eats a read-write \c BoolMap& bool_map,
4.25 /// which have to work well up
4.26 /// to its \c set and \c operator[]() method. Thus we have to deal
4.27 /// very carefully with an uninitialized \c IterableBoolMap.
4.28 + /// \ingroup galgs
4.29 template<typename Graph, typename BoolMap>
4.30 bool isBipartite(const Graph& g, BoolMap& bool_map) {
4.31 typedef typename Graph::template NodeMap<bool> ReachedMap;
4.32 @@ -52,6 +53,7 @@
4.33 /// If the graph is directed and not acyclic,
4.34 /// then going back from the returned node via the pred information, a
4.35 /// cycle is obtained.
4.36 + /// \ingroup galgs
4.37 template<typename Graph, typename PredMap>
4.38 typename Graph::Node
4.39 topSort(const Graph& g, std::list<typename Graph::Node>& l,
4.40 @@ -89,6 +91,7 @@
4.41 }
4.42 return INVALID;
4.43 }
4.44 +
4.45 } //namespace hugo
4.46
4.47 #endif //HUGO_BFS_DFS_MISC_H
5.1 --- a/src/work/marci/makefile Tue May 11 19:38:00 2004 +0000
5.2 +++ b/src/work/marci/makefile Tue May 11 19:50:21 2004 +0000
5.3 @@ -4,7 +4,7 @@
5.4 INCLUDEDIRS ?= -I../.. -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
5.5
5.6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
5.7 -BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test
5.8 +BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
5.9 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
5.10
5.11 include ../makefile
6.1 --- a/src/work/marci/max_bipartite_matching.h Tue May 11 19:38:00 2004 +0000
6.2 +++ b/src/work/marci/max_bipartite_matching.h Tue May 11 19:50:21 2004 +0000
6.3 @@ -2,6 +2,16 @@
6.4 #ifndef HUGO_MAX_BIPARTITE_MATCHING_H
6.5 #define HUGO_MAX_BIPARTITE_MATCHING_H
6.6
6.7 +/// \ingroup galgs
6.8 +/// \file
6.9 +/// \brief Maximum bipartite matchings, b-matchings and
6.10 +/// capacitated b-matchings.
6.11 +///
6.12 +/// This file contains a class for bipartite maximum matching, b-matchings
6.13 +/// and capacitated b-matching computations.
6.14 +///
6.15 +// /// \author Marton Makai
6.16 +
6.17 //#include <for_each_macros.h>
6.18 #include <bipartite_graph_wrapper.h>
6.19 //#include <hugo/maps.h>
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/work/marci/max_flow_1.cc Tue May 11 19:50:21 2004 +0000
7.3 @@ -0,0 +1,60 @@
7.4 +// -*- c++ -*-
7.5 +#include <iostream>
7.6 +#include <fstream>
7.7 +
7.8 +#include <list_graph.h>
7.9 +#include <hugo/smart_graph.h>
7.10 +#include <hugo/dimacs.h>
7.11 +#include <hugo/time_measure.h>
7.12 +//#include <graph_wrapper.h>
7.13 +#include <max_flow.h>
7.14 +//#include <preflow_res.h>
7.15 +#include <for_each_macros.h>
7.16 +
7.17 +using namespace hugo;
7.18 +
7.19 +// Use a DIMACS max flow file as stdin.
7.20 +// read_dimacs_demo < dimacs_max_flow_file
7.21 +
7.22 +
7.23 +int main(int, char **) {
7.24 +
7.25 + typedef ListGraph MutableGraph;
7.26 +
7.27 + typedef SmartGraph Graph;
7.28 + // typedef ListGraph Graph;
7.29 + typedef Graph::Node Node;
7.30 + typedef Graph::EdgeIt EdgeIt;
7.31 +
7.32 +
7.33 + Graph g;
7.34 + Node s, t;
7.35 + Graph::EdgeMap<int> cap(g);
7.36 + //readDimacsMaxFlow(std::cin, g, s, t, cap);
7.37 + readDimacs(std::cin, g, cap, s, t);
7.38 + Timer ts;
7.39 + Graph::EdgeMap<int> flow(g); //0 flow
7.40 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
7.41 + max_flow_test(g, s, t, cap, flow);
7.42 +
7.43 + {
7.44 + std::cout << "preflow ..." << std::endl;
7.45 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.46 + ts.reset();
7.47 + max_flow_test.preflowPhase0(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::ZERO_FLOW);
7.48 + std::cout << "elapsed time: " << ts << std::endl;
7.49 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
7.50 + }
7.51 +
7.52 + {
7.53 + std::cout << "preflow ..." << std::endl;
7.54 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
7.55 + ts.reset();
7.56 + max_flow_test.preflowPhase0(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::ZERO_FLOW);
7.57 + std::cout << "elapsed time: " << ts << std::endl;
7.58 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
7.59 + }
7.60 +
7.61 +
7.62 + return 0;
7.63 +}