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

equal deleted inserted replaced

-:b943fe5279af
+:da19b45181c9
 // -*- C++ -*-
-#ifndef HUGO_MAX_FLOW_NO_STACK_H
+#ifndef HUGO_MAX_FLOW_H
-#define HUGO_MAX_FLOW_NO_STACK_H
+#define HUGO_MAX_FLOW_H
 #include <vector>
 #include <queue>
-//#include <stack>
 #include <hugo/graph_wrapper.h>
 #include <hugo/invalid.h>
 #include <hugo/maps.h>
 /// \file
-/// \brief The same as max_flow.h, but without using stl stack for the active nodes. Only for test.
 /// \ingroup galgs
 namespace hugo {
 /// \addtogroup galgs
 typedef typename Graph::NodeIt NodeIt;
 typedef typename Graph::EdgeIt EdgeIt;
 typedef typename Graph::OutEdgeIt OutEdgeIt;
 typedef typename Graph::InEdgeIt InEdgeIt;
-//    typedef typename std::vector<std::stack<Node> > VecStack;
 typedef typename std::vector<Node> VecFirst;
 typedef typename Graph::template NodeMap<Node> NNMap;
 typedef typename std::vector<Node> VecNode;
 const Graph* g;
 int n;      //the number of nodes of G
 typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
 //typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
 typedef typename ResGW::Edge ResGWEdge;
-//typedef typename ResGW::template NodeMap<bool> ReachedMap;
 typedef typename Graph::template NodeMap<int> ReachedMap;
 //level works as a bool map in augmenting path algorithms and is
 //used by bfs for storing reached information.  In preflow, it
 AFTER_FAST_AUGMENTING,
 AFTER_PRE_FLOW_PHASE_1,
 AFTER_PRE_FLOW_PHASE_2
 };
-/// Don not needle this flag only if necessary.
+/// Do not needle this flag only if necessary.
 StatusEnum status;
 //     int number_of_augmentations;
 ///Runs the first phase of the preflow algorithm.
 ///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
+///is not 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,
 NNMap left(*g, INVALID);
 NNMap right(*g, INVALID);
 VecNode level_list(n,INVALID);
 //List of the nodes in level i<n, set to n.
-NodeIt v;
-for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
-//setting each node to level n
-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:
-	{
-	  NodeIt v;
-	  for(g->first(v); g->valid(v); g->next(v)) {
-	    Num exc=0;
-	    InEdgeIt e;
-	    for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
-	    OutEdgeIt f;
-	    for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
-	    excess.set(v,exc);
-	    //putting the active nodes into the stack
-	    int lev=level[v];
-	    if ( exc > 0 && lev < n && v != t )
-	      {
-		next.set(v,first[lev]);
-		first[lev]=v;
-	      }
-	  }
-	  break;
-	}
-case GEN_FLOW:
-	{
-	  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;
-	}
-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, next, first, level_list, left, right);
 //End of preprocessing
 //Push/relabel on the highest level active nodes.
 while ( true ) {
 	if ( b == 0 ) {
 	  if ( !what_heur && !end && k > 0 ) {
 	    level.set(w,++newlevel);
 	    next.set(w,first[newlevel]);
 	    first[newlevel]=w;
 	    b=newlevel;
 	  }
-	}  // if stack[b] is nonempty
+	}
 } // while(true)
 status=AFTER_PRE_FLOW_PHASE_2;
 }
 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
 ///value and a minimum value cut can already be computed. This
 return newlevel;
 }
 void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first,
 			VecNode& level_list, NNMap& left, NNMap& right)
 {
+switch (fe) { //setting excess
+	case NO_FLOW:
+	{
+	  EdgeIt e;
+	  for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
+	  NodeIt v;
+	  for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
+	  break;
+	}
+	case ZERO_FLOW:
+	{
+	  NodeIt v;
+	  for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
+	  break;
+	}
+	case GEN_FLOW:
+	{
+	  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: break;
+}
+NodeIt v;
+for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
+//setting each node to level n
 std::queue<Node> bfs_queue;
 switch (fe) {
-case NO_FLOW:   //flow is already set to const zero in this case
+case NO_FLOW:   //flow is already set to const zero
 case ZERO_FLOW:
 	{
 	  //Reverse_bfs from t, to find the starting level.
 	  level.set(t,0);
 	  bfs_queue.push(t);
 	    {
 	      Num c=(*capacity)[e];
 	      if ( c <= 0 ) continue;
 	      Node w=g->head(e);
 	      if ( level[w] < n ) {
-		if ( excess[w] <= 0 && w!=t )
+		if ( excess[w] <= 0 && w!=t ) //putting into the stack
 		  {
 		    next.set(w,first[level[w]]);
 		    first[level[w]]=w;
 		  }
 		flow->set(e, c);
 		excess.set(w, excess[w]+c);
 	    }
 	  break;
 	}
 case GEN_FLOW:
-case PRE_FLOW:
 	{
 	  //Reverse_bfs from t in the residual graph,
 	  //to find the starting level.
 	  level.set(t,0);
 	  bfs_queue.push(t);
 		level.set(w, l);
 	      }
 	    }
 	  }
 	  //the starting flow
 	  OutEdgeIt e;
 	  for(g->first(e,s); g->valid(e); g->next(e))
 	    {
 	      Num rem=(*capacity)[e]-(*flow)[e];
 	      if ( rem <= 0 ) continue;
 	      Node w=g->head(e);
 	      if ( level[w] < n ) {
-		if ( excess[w] <= 0 && w!=t )
+		if ( excess[w] <= 0 && w!=t ) //putting into the stack
 		  {
 		    next.set(w,first[level[w]]);
 		    first[level[w]]=w;
 		  }
 		flow->set(e, (*capacity)[e]);
 	      if ( level[w] < n ) {
 		if ( excess[w] <= 0 && w!=t )
 		  {
 		    next.set(w,first[level[w]]);
 		    first[level[w]]=w;
 		  }
 		excess.set(w, excess[w]+(*flow)[f]);
 		flow->set(f, 0);
 	      }
 	    }
 	  break;
+	} //case GEN_FLOW
+case PRE_FLOW:
+	{
+	  //Reverse_bfs from t in the residual graph,
+	  //to find the starting level.
+	  level.set(t,0);
+	  bfs_queue.push(t);
+	  while (!bfs_queue.empty()) {
+	    Node v=bfs_queue.front();
+	    bfs_queue.pop();
+	    int l=level[v]+1;
+	    InEdgeIt e;
+	    for(g->first(e,v); g->valid(e); g->next(e)) {
+	      if ( (*capacity)[e] <= (*flow)[e] ) continue;
+	      Node w=g->tail(e);
+	      if ( level[w] == n && w != s ) {
+		bfs_queue.push(w);
+		Node z=level_list[l];
+		if ( g->valid(z) ) left.set(z,w);
+		right.set(w,z);
+		level_list[l]=w;
+		level.set(w, l);
+	      }
+	    }
+	    OutEdgeIt f;
+	    for(g->first(f,v); g->valid(f); g->next(f)) {
+	      if ( 0 >= (*flow)[f] ) continue;
+	      Node w=g->head(f);
+	      if ( level[w] == n && w != s ) {
+		bfs_queue.push(w);
+		Node z=level_list[l];
+		if ( g->valid(z) ) left.set(z,w);
+		right.set(w,z);
+		level_list[l]=w;
+		level.set(w, l);
+	      }
+	    }
+	  }
+	  //the starting flow
+	  OutEdgeIt e;
+	  for(g->first(e,s); g->valid(e); g->next(e))
+	    {
+	      Num rem=(*capacity)[e]-(*flow)[e];
+	      if ( rem <= 0 ) continue;
+	      Node w=g->head(e);
+	      if ( level[w] < n ) {
+		flow->set(e, (*capacity)[e]);
+		excess.set(w, excess[w]+rem);
+	      }
+	    }
+	  InEdgeIt f;
+	  for(g->first(f,s); g->valid(f); g->next(f))
+	    {
+	      if ( (*flow)[f] <= 0 ) continue;
+	      Node w=g->tail(f);
+	      if ( level[w] < n ) {
+		excess.set(w, excess[w]+(*flow)[f]);
+		flow->set(f, 0);
+	      }
+	    }
+	  NodeIt w; //computing the excess
+	  for(g->first(w); g->valid(w); g->next(w)) {
+	    Num exc=0;
+	    InEdgeIt e;
+	    for(g->first(e,w); g->valid(e); g->next(e)) exc+=(*flow)[e];
+	    OutEdgeIt f;
+	    for(g->first(f,w); g->valid(f); g->next(f)) exc-=(*flow)[f];
+	    excess.set(w,exc);
+	    //putting the active nodes into the stack
+	    int lev=level[w];
+	    if ( exc > 0 && lev < n && w != t )
+	      {
+		next.set(w,first[lev]);
+		first[lev]=w;
+	      }
+	  }
+	  break;
 	} //case PRE_FLOW
 }
 } //preflowPreproc
 void relabel(Node w, int newlevel, NNMap& next, VecFirst& first,
 		 VecNode& level_list, NNMap& left,
 		 NNMap& right, int& b, int& k, bool what_heur )
 	  left.set(w,INVALID);
 	  level_list[newlevel]=w;
 	}
 }
 } //relabel
+void printexcess() {////
+std::cout << "Excesses:" <<std::endl;
+NodeIt v;
+for(g->first(v); g->valid(v); g->next(v)) {
+	std::cout << 1+(g->id(v)) << ":" << excess[v]<<std::endl;
+}
+}
+void printlevel() {////
+std::cout << "Levels:" <<std::endl;
+NodeIt v;
+for(g->first(v); g->valid(v); g->next(v)) {
+	std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
+}
+}
+void printactive() {////
+std::cout << "Levels:" <<std::endl;
+NodeIt v;
+for(g->first(v); g->valid(v); g->next(v)) {
+	std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
+}
+}
 };  //class MaxFlow
 } //namespace hugo
 #endif //HUGO_MAX_FLOW_H

changeset 754	2471ef33b4a0
parent 745	d976ba609099
child 757	8680351d0c28