1.1 --- a/src/hugo/max_flow.h Tue Jul 27 19:08:23 2004 +0000
1.2 +++ b/src/hugo/max_flow.h Thu Jul 29 17:18:49 2004 +0000
1.3 @@ -140,7 +140,7 @@
1.4 ///\todo Document, please.
1.5 ///
1.6 MaxFlow(const Graph& _G, Node _s, Node _t,
1.7 - const CapMap& _capacity, FlowMap& _flow) :
1.8 + const CapMap& _capacity, FlowMap& _flow) :
1.9 g(&_G), s(_s), t(_t), capacity(&_capacity),
1.10 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0),
1.11 status(AFTER_NOTHING) { }
1.12 @@ -217,7 +217,6 @@
1.13
1.14 VecFirst first(n, INVALID);
1.15 NNMap next(*g, INVALID); //maybe INVALID is not needed
1.16 - // VecStack active(n);
1.17
1.18 NNMap left(*g, INVALID);
1.19 NNMap right(*g, INVALID);
1.20 @@ -254,7 +253,6 @@
1.21 next.set(v,first[lev]);
1.22 first[lev]=v;
1.23 }
1.24 - // active[lev].push(v);
1.25 }
1.26 break;
1.27 }
1.28 @@ -280,7 +278,7 @@
1.29 }
1.30 }
1.31
1.32 - preflowPreproc(fe, next, first,/*active*/ level_list, left, right);
1.33 + preflowPreproc(fe, next, first, level_list, left, right);
1.34 //End of preprocessing
1.35
1.36
1.37 @@ -293,15 +291,13 @@
1.38 } else break;
1.39 }
1.40
1.41 - if ( !g->valid(first[b])/*active[b].empty()*/ ) --b;
1.42 + if ( !g->valid(first[b]) ) --b;
1.43 else {
1.44 end=false;
1.45 Node w=first[b];
1.46 first[b]=next[w];
1.47 - /* Node w=active[b].top();
1.48 - active[b].pop();*/
1.49 - int newlevel=push(w,/*active*/next, first);
1.50 - if ( excess[w] > 0 ) relabel(w, newlevel, /*active*/next, first, level_list,
1.51 + int newlevel=push(w, next, first);
1.52 + if ( excess[w] > 0 ) relabel(w, newlevel, next, first, level_list,
1.53 left, right, b, k, what_heur);
1.54
1.55 ++numrelabel;
1.56 @@ -340,7 +336,6 @@
1.57
1.58 VecFirst first(n, INVALID);
1.59 NNMap next(*g, INVALID); //maybe INVALID is not needed
1.60 - // VecStack active(n);
1.61 level.set(s,0);
1.62 std::queue<Node> bfs_queue;
1.63 bfs_queue.push(s);
1.64 @@ -361,7 +356,6 @@
1.65 if ( excess[u] > 0 ) {
1.66 next.set(u,first[l]);
1.67 first[l]=u;
1.68 - //active[l].push(u);
1.69 }
1.70 }
1.71 }
1.72 @@ -376,7 +370,6 @@
1.73 if ( excess[u] > 0 ) {
1.74 next.set(u,first[l]);
1.75 first[l]=u;
1.76 - //active[l].push(u);
1.77 }
1.78 }
1.79 }
1.80 @@ -387,13 +380,11 @@
1.81
1.82 if ( b == 0 ) break;
1.83
1.84 - if ( !g->valid(first[b])/*active[b].empty()*/ ) --b;
1.85 + if ( !g->valid(first[b]) ) --b;
1.86 else {
1.87
1.88 Node w=first[b];
1.89 first[b]=next[w];
1.90 - /* Node w=active[b].top();
1.91 - active[b].pop();*/
1.92 int newlevel=push(w,next, first/*active*/);
1.93
1.94 //relabel
1.95 @@ -401,7 +392,6 @@
1.96 level.set(w,++newlevel);
1.97 next.set(w,first[newlevel]);
1.98 first[newlevel]=w;
1.99 - //active[newlevel].push(w);
1.100 b=newlevel;
1.101 }
1.102 } // if stack[b] is nonempty
1.103 @@ -420,9 +410,18 @@
1.104 Num a=0;
1.105 for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
1.106 for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
1.107 -
1.108 + return a;
1.109 //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
1.110 }
1.111 + Num flowValue2() const {
1.112 + return excess[t];
1.113 +// Num a=0;
1.114 +// for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
1.115 +// for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
1.116 +// return a;
1.117 +// //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
1.118 +
1.119 + }
1.120
1.121 ///Returns a minimum value cut after calling \ref preflowPhase1.
1.122
1.123 @@ -451,6 +450,8 @@
1.124 break;
1.125 case AFTER_PRE_FLOW_PHASE_2:
1.126 case AFTER_NOTHING:
1.127 + case AFTER_AUGMENTING:
1.128 + case AFTER_FAST_AUGMENTING:
1.129 minMinCut(M);
1.130 break;
1.131 }
1.132 @@ -591,8 +592,6 @@
1.133 if ( excess[v]<=0 && v!=t && v!=s ) {
1.134 next.set(v,first[level[v]]);
1.135 first[level[v]]=v;
1.136 - // int lev_v=level[v];
1.137 - //active[lev_v].push(v);
1.138 }
1.139
1.140 Num cap=(*capacity)[e];
1.141 @@ -626,8 +625,6 @@
1.142 if ( excess[v]<=0 && v!=t && v!=s ) {
1.143 next.set(v,first[level[v]]);
1.144 first[level[v]]=v;
1.145 - //int lev_v=level[v];
1.146 - //active[lev_v].push(v);
1.147 }
1.148
1.149 Num flo=(*flow)[e];
1.150 @@ -700,7 +697,6 @@
1.151 {
1.152 next.set(w,first[level[w]]);
1.153 first[level[w]]=w;
1.154 - //active[level[w]].push(w);
1.155 }
1.156 flow->set(e, c);
1.157 excess.set(w, excess[w]+c);
1.158 @@ -765,7 +761,6 @@
1.159 {
1.160 next.set(w,first[level[w]]);
1.161 first[level[w]]=w;
1.162 - //active[level[w]].push(w);
1.163 }
1.164 flow->set(e, (*capacity)[e]);
1.165 excess.set(w, excess[w]+rem);
1.166 @@ -782,7 +777,6 @@
1.167 {
1.168 next.set(w,first[level[w]]);
1.169 first[level[w]]=w;
1.170 - //active[level[w]].push(w);
1.171 }
1.172 excess.set(w, excess[w]+(*flow)[f]);
1.173 flow->set(f, 0);
1.174 @@ -834,11 +828,6 @@
1.175 }
1.176 level_list[i]=INVALID;
1.177 if ( !what_heur ) first[i]=INVALID;
1.178 - /*{
1.179 - while ( !active[i].empty() ) {
1.180 - active[i].pop(); //FIXME: ezt szebben kene
1.181 - }
1.182 - }*/
1.183 }
1.184
1.185 level.set(w,n);
1.186 @@ -853,7 +842,6 @@
1.187 level.set(w,++newlevel);
1.188 next.set(w,first[newlevel]);
1.189 first[newlevel]=w;
1.190 - // active[newlevel].push(w);
1.191 if ( what_heur ) b=newlevel;
1.192 if ( k < newlevel ) ++k; //now k=newlevel
1.193 Node z=level_list[newlevel];