lemon-0.x: comparison src/hugo/max

equal deleted inserted replaced

-:5027979724cc
+:b943fe5279af
 ///Constructor
 ///\todo Document, please.
 ///
 MaxFlow(const Graph& _G, Node _s, Node _t,
-		   const CapMap& _capacity, FlowMap& _flow) :
+	    const CapMap& _capacity, FlowMap& _flow) :
 g(&_G), s(_s), t(_t), capacity(&_capacity),
 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0),
 status(AFTER_NOTHING) { }
 ///Runs a maximum flow algorithm.
 int k=n-2;  //bound on the highest level under n containing a node
 int b=k;    //bound on the highest level under n of an active node
 VecFirst first(n, INVALID);
 NNMap next(*g, INVALID); //maybe INVALID is not needed
-//    VecStack active(n);
 NNMap left(*g, INVALID);
 NNMap right(*g, INVALID);
 VecNode level_list(n,INVALID);
 //List of the nodes in level i<n, set to n.
 	    if ( exc > 0 && lev < n && v != t )
 	      {
 		next.set(v,first[lev]);
 		first[lev]=v;
 	      }
-	    //	  active[lev].push(v);
 	  }
 	  break;
 	}
 case GEN_FLOW:
 	{
 	  for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
 	  break;
 	}
 }
-preflowPreproc(fe, next, first,/*active*/ level_list, left, right);
+preflowPreproc(fe, next, first, level_list, left, right);
 //End of preprocessing
 //Push/relabel on the highest level active nodes.
 while ( true ) {
 	    b=k;
 	    end=true;
 	  } else break;
 	}
-	if ( !g->valid(first[b])/*active[b].empty()*/ ) --b;
+	if ( !g->valid(first[b]) ) --b;
 	else {
 	  end=false;
 	  Node w=first[b];
 	  first[b]=next[w];
-	  /*	Node w=active[b].top();
+	  int newlevel=push(w, next, first);
-		active[b].pop();*/
+	  if ( excess[w] > 0 ) relabel(w, newlevel, next, first, level_list,
-	  int newlevel=push(w,/*active*/next, first);
-	  if ( excess[w] > 0 ) relabel(w, newlevel, /*active*/next, first, level_list,
 				       left, right, b, k, what_heur);
 	  ++numrelabel;
 	  if ( numrelabel >= heur ) {
 	    numrelabel=0;
 int b=k;    //bound on the highest level under n of an active node
 VecFirst first(n, INVALID);
 NNMap next(*g, INVALID); //maybe INVALID is not needed
-//    VecStack active(n);
 level.set(s,0);
 std::queue<Node> bfs_queue;
 bfs_queue.push(s);
 while (!bfs_queue.empty()) {
 	    bfs_queue.push(u);
 	    level.set(u, l);
 	    if ( excess[u] > 0 ) {
 	      next.set(u,first[l]);
 	      first[l]=u;
-	      //active[l].push(u);
 	    }
 	  }
 	}
 	OutEdgeIt f;
 	    bfs_queue.push(u);
 	    level.set(u, l);
 	    if ( excess[u] > 0 ) {
 	      next.set(u,first[l]);
 	      first[l]=u;
-	      //active[l].push(u);
 	    }
 	  }
 	}
 }
 b=n-2;
 while ( true ) {
 	if ( b == 0 ) break;
-	if ( !g->valid(first[b])/*active[b].empty()*/ ) --b;
+	if ( !g->valid(first[b]) ) --b;
 	else {
 	  Node w=first[b];
 	  first[b]=next[w];
-	  /*	Node w=active[b].top();
-		active[b].pop();*/
 	  int newlevel=push(w,next, first/*active*/);
 	  //relabel
 	  if ( excess[w] > 0 ) {
 	    level.set(w,++newlevel);
 	    next.set(w,first[newlevel]);
 	    first[newlevel]=w;
-	    //active[newlevel].push(w);
 	    b=newlevel;
 	  }
 	}  // if stack[b] is nonempty
 } // while(true)
 /// It can be called already after running \ref preflowPhase1.
 Num flowValue() const {
 Num a=0;
 for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
 for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
+return a;
 //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
+}
+Num flowValue2() const {
+return excess[t];
+//       Num a=0;
+//       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
+//       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
+//       return a;
+//       //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
 }
 ///Returns a minimum value cut after calling \ref preflowPhase1.
 ///After the first phase of the preflow algorithm the maximum flow
 	  }
 	}
 	break;
 case AFTER_PRE_FLOW_PHASE_2:
 case AFTER_NOTHING:
+case AFTER_AUGMENTING:
+case AFTER_FAST_AUGMENTING:
 	minMinCut(M);
 	break;
 }
 }
 	if( lev > level[v] ) { //Push is allowed now
 	  if ( excess[v]<=0 && v!=t && v!=s ) {
 	    next.set(v,first[level[v]]);
 	    first[level[v]]=v;
-	    //	    int lev_v=level[v];
-	    //active[lev_v].push(v);
 	  }
 	  Num cap=(*capacity)[e];
 	  Num flo=(*flow)[e];
 	  Num remcap=cap-flo;
 	  if( lev > level[v] ) { //Push is allowed now
 	    if ( excess[v]<=0 && v!=t && v!=s ) {
 	      next.set(v,first[level[v]]);
 	      first[level[v]]=v;
-	      //int lev_v=level[v];
-	      //active[lev_v].push(v);
 	    }
 	    Num flo=(*flow)[e];
 	    if ( flo >= exc ) { //A nonsaturating push.
 	      if ( level[w] < n ) {
 		if ( excess[w] <= 0 && w!=t )
 		  {
 		    next.set(w,first[level[w]]);
 		    first[level[w]]=w;
-		    //active[level[w]].push(w);
 		  }
 		flow->set(e, c);
 		excess.set(w, excess[w]+c);
 	      }
 	    }
 	      if ( level[w] < n ) {
 		if ( excess[w] <= 0 && w!=t )
 		  {
 		    next.set(w,first[level[w]]);
 		    first[level[w]]=w;
-		    //active[level[w]].push(w);
 		  }
 		flow->set(e, (*capacity)[e]);
 		excess.set(w, excess[w]+rem);
 	      }
 	    }
 	      if ( level[w] < n ) {
 		if ( excess[w] <= 0 && w!=t )
 		  {
 		    next.set(w,first[level[w]]);
 		    first[level[w]]=w;
-		    //active[level[w]].push(w);
 		  }
 		excess.set(w, excess[w]+(*flow)[f]);
 		flow->set(f, 0);
 	      }
 	    }
 	    level.set(v,n);
 	    v=right[v];
 	  }
 	  level_list[i]=INVALID;
 	  if ( !what_heur ) first[i]=INVALID;
-	  /*{
-	    while ( !active[i].empty() ) {
-	    active[i].pop();    //FIXME: ezt szebben kene
-	    }
-	    }*/
 	}
 	level.set(w,n);
 	b=lev-1;
 	k=b;
 	if ( newlevel == n ) level.set(w,n);
 	else {
 	  level.set(w,++newlevel);
 	  next.set(w,first[newlevel]);
 	  first[newlevel]=w;
-	  //	  active[newlevel].push(w);
 	  if ( what_heur ) b=newlevel;
 	  if ( k < newlevel ) ++k;      //now k=newlevel
 	  Node z=level_list[newlevel];
 	  if ( g->valid(z) ) left.set(z,w);
 	  right.set(w,z);

changeset 747	be163d94c109
parent 735	2859c45c31dd
child 749	8e933219691e