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

equal deleted inserted replaced

-:9f1a4a2a8c63
+:9a220d72378d
 #define HUGO_MAX_FLOW_H
 #include <vector>
 #include <queue>
-#include <hugo/graph_wrapper.h>
+//#include <hugo/graph_wrapper.h>
 #include <hugo/invalid.h>
 #include <hugo/maps.h>
 /// \file
 /// \ingroup flowalgs
 Node s;
 Node t;
 const CapMap* capacity;
 FlowMap* flow;
 int n;      //the number of nodes of G
-typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
+//    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
 //typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
-typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
+//    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
-typedef typename ResGW::Edge ResGWEdge;
+//    typedef typename ResGW::Edge ResGWEdge;
 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
 };
 /// Do not needle this flag only if necessary.
 StatusEnum status;
 //     int number_of_augmentations;
 //     template<typename IntMap>
 //     class TrickyReachedMap {
 //     protected:
 //       IntMap* map;
 //       int* number_of_augmentations;
 //     public:
 //       TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
 // 	map(&_map), number_of_augmentations(&_number_of_augmentations) { }
 //       void set(const Node& n, bool b) {
 // 	if (b)
 // 	  map->set(n, *number_of_augmentations);
 // 	else
 // 	  map->set(n, *number_of_augmentations-1);
 //       }
 //       bool operator[](const Node& n) const {
 // 	return (*map)[n]==*number_of_augmentations;
 //       }
 //     };
 ///Constructor
 ///\todo Document, please.
 ///
 	    b=k;
 	    end=true;
 	  } else break;
 	}
-	if ( !g->valid(first[b]) ) --b;
+	if ( first[b]==INVALID ) --b;
 	else {
 	  end=false;
 	  Node w=first[b];
 	  first[b]=next[w];
 	  int newlevel=push(w, next, first);
 	Node v=bfs_queue.front();
 	bfs_queue.pop();
 	int l=level[v]+1;
-	InEdgeIt e;
+	for(InEdgeIt e(*g,v); e!=INVALID; ++e) {
-	for(g->first(e,v); g->valid(e); g->next(e)) {
 	  if ( (*capacity)[e] <= (*flow)[e] ) continue;
 	  Node u=g->tail(e);
 	  if ( level[u] >= n ) {
 	    bfs_queue.push(u);
 	    level.set(u, l);
 	      first[l]=u;
 	    }
 	  }
 	}
-	OutEdgeIt f;
+	for(OutEdgeIt e(*g,v); e!=INVALID; ++e) {
-	for(g->first(f,v); g->valid(f); g->next(f)) {
+	  if ( 0 >= (*flow)[e] ) continue;
-	  if ( 0 >= (*flow)[f] ) continue;
+	  Node u=g->head(e);
-	  Node u=g->head(f);
 	  if ( level[u] >= n ) {
 	    bfs_queue.push(u);
 	    level.set(u, l);
 	    if ( excess[u] > 0 ) {
 	      next.set(u,first[l]);
 while ( true ) {
 	if ( b == 0 ) break;
-	if ( !g->valid(first[b]) ) --b;
+	if ( first[b]==INVALID ) --b;
 	else {
 	  Node w=first[b];
 	  first[b]=next[w];
 	  int newlevel=push(w,next, first/*active*/);
 /// Returns the excess of the target node \ref t.
 /// After running \ref preflowPhase1, this is the value of
 /// the maximum flow.
 /// 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;
 return excess[t];
 //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
 }
 /// actual state
 /// of the class. This enables us to determine which methods are valid
 /// for MinCut computation
 template<typename _CutMap>
 void actMinCut(_CutMap& M) const {
-NodeIt v;
 switch (status) {
-case AFTER_PRE_FLOW_PHASE_1:
+	case AFTER_PRE_FLOW_PHASE_1:
-	for(g->first(v); g->valid(v); g->next(v)) {
+	for(NodeIt v(*g); v!=INVALID; ++v) {
 	  if (level[v] < n) {
 	    M.set(v, false);
 	  } else {
 	    M.set(v, true);
 	  }
 	}
 	break;
-case AFTER_PRE_FLOW_PHASE_2:
+	case AFTER_PRE_FLOW_PHASE_2:
-case AFTER_NOTHING:
+	case AFTER_NOTHING:
-case AFTER_AUGMENTING:
+	case AFTER_AUGMENTING:
-case AFTER_FAST_AUGMENTING:
+	case AFTER_FAST_AUGMENTING:
 	minMinCut(M);
 	break;
 }
 }
 while (!queue.empty()) {
 Node w=queue.front();
 	queue.pop();
-	OutEdgeIt e;
+	for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
-	for(g->first(e,w) ; g->valid(e); g->next(e)) {
 	  Node v=g->head(e);
 	  if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
 	    queue.push(v);
 	    M.set(v, true);
 	  }
 	}
-	InEdgeIt f;
+	for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
-	for(g->first(f,w) ; g->valid(f); g->next(f)) {
+	  Node v=g->tail(e);
-	  Node v=g->tail(f);
+	  if (!M[v] && (*flow)[e] > 0 ) {
-	  if (!M[v] && (*flow)[f] > 0 ) {
 	    queue.push(v);
 	    M.set(v, true);
 	  }
 	}
 }
 ///\pre M should be a node map of bools initialized to false.
 ///\pre \c flow must be a maximum flow.
 template<typename _CutMap>
 void maxMinCut(_CutMap& M) const {
-NodeIt v;
+for(NodeIt v(*g) ; v!=INVALID; ++v) M.set(v, true);
-for(g->first(v) ; g->valid(v); g->next(v)) {
-	M.set(v, true);
-}
 std::queue<Node> queue;
 M.set(t,false);
 queue.push(t);
 while (!queue.empty()) {
 Node w=queue.front();
 	queue.pop();
-	InEdgeIt e;
+	for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
-	for(g->first(e,w) ; g->valid(e); g->next(e)) {
 	  Node v=g->tail(e);
 	  if (M[v] && (*flow)[e] < (*capacity)[e] ) {
 	    queue.push(v);
 	    M.set(v, false);
 	  }
 	}
-	OutEdgeIt f;
+	for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
-	for(g->first(f,w) ; g->valid(f); g->next(f)) {
+	  Node v=g->head(e);
-	  Node v=g->head(f);
+	  if (M[v] && (*flow)[e] > 0 ) {
-	  if (M[v] && (*flow)[f] > 0 ) {
 	    queue.push(v);
 	    M.set(v, false);
 	  }
 	}
 }
 int lev=level[w];
 Num exc=excess[w];
 int newlevel=n;       //bound on the next level of w
-OutEdgeIt e;
+for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
-for(g->first(e,w); g->valid(e); g->next(e)) {
 	if ( (*flow)[e] >= (*capacity)[e] ) continue;
 	Node v=g->head(e);
 	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;
 	  }
 	  Num cap=(*capacity)[e];
 	  Num flo=(*flow)[e];
 	  Num remcap=cap-flo;
 	  if ( remcap >= exc ) { //A nonsaturating push.
 	    flow->set(e, flo+exc);
 	    excess.set(v, excess[v]+exc);
 	    exc=0;
 	    break;
 	  }
 	} else if ( newlevel > level[v] ) newlevel = level[v];
 } //for out edges wv
 if ( exc > 0 ) {
-	InEdgeIt e;
+	for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
-	for(g->first(e,w); g->valid(e); g->next(e)) {
 	  if( (*flow)[e] <= 0 ) continue;
 	  Node v=g->tail(e);
 	  if( lev > level[v] ) { //Push is allowed now
 	} //for in edges vw
 } // if w still has excess after the out edge for cycle
 excess.set(w, exc);
 return newlevel;
 }
 void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first,
 			VecNode& level_list, NNMap& left, NNMap& right)
 {
-switch (fe) { //setting excess
+switch (fe) {  //setting excess
 	case NO_FLOW:
+	for(EdgeIt e(*g); e!=INVALID; ++e) flow->set(e,0);
+	for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
+	break;
+	case ZERO_FLOW:
+	for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
+	break;
+	case GEN_FLOW:
+	for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
 	{
-	  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(InEdgeIt e(*g,t) ; e!=INVALID; ++e) exc+=(*flow)[e];
-	  for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
+	  for(OutEdgeIt e(*g,t) ; e!=INVALID; ++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;
+	}
-	}
+	break;
-	default: break;
+	default:
-}
+	break;
+}
-NodeIt v;
-for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
+for(NodeIt v(*g); v!=INVALID; ++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
 case ZERO_FLOW:
-	{
+	//Reverse_bfs from t, to find the starting level.
-	  //Reverse_bfs from t, to find the starting level.
+	level.set(t,0);
-	  level.set(t,0);
+	bfs_queue.push(t);
-	  bfs_queue.push(t);
+	while (!bfs_queue.empty()) {
-	  while (!bfs_queue.empty()) {
+	  Node v=bfs_queue.front();
-	    Node v=bfs_queue.front();
+	  bfs_queue.pop();
-	    bfs_queue.pop();
+	  int l=level[v]+1;
-	    int l=level[v]+1;
+	  for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
-	    InEdgeIt e;
+	    Node w=g->tail(e);
-	    for(g->first(e,v); g->valid(e); g->next(e)) {
+	    if ( level[w] == n && w != s ) {
-	      Node w=g->tail(e);
+	      bfs_queue.push(w);
-	      if ( level[w] == n && w != s ) {
+	      Node z=level_list[l];
-		bfs_queue.push(w);
+	      if ( z!=INVALID ) left.set(z,w);
-		Node z=level_list[l];
+	      right.set(w,z);
-		if ( g->valid(z) ) left.set(z,w);
+	      level_list[l]=w;
-		right.set(w,z);
+	      level.set(w, l);
-		level_list[l]=w;
+	    }
-		level.set(w, l);
+	  }
-	      }
+	}
-	    }
-	  }
+	//the starting flow
+	for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e)
-	  //the starting flow
+	  {
-	  OutEdgeIt e;
+	    Num c=(*capacity)[e];
-	  for(g->first(e,s); g->valid(e); g->next(e))
+	    if ( c <= 0 ) continue;
+	    Node w=g->head(e);
+	    if ( level[w] < n ) {
+	      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:
+	//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;
+	  for(InEdgeIt e(*g,v) ; e!=INVALID; ++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 ( z!=INVALID ) left.set(z,w);
+	      right.set(w,z);
+	      level_list[l]=w;
+	      level.set(w, l);
+	    }
+	  }
+	  for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
+	    if ( 0 >= (*flow)[e] ) continue;
+	    Node w=g->head(e);
+	    if ( level[w] == n && w != s ) {
+	      bfs_queue.push(w);
+	      Node z=level_list[l];
+	      if ( z!=INVALID ) left.set(z,w);
+	      right.set(w,z);
+	      level_list[l]=w;
+	      level.set(w, l);
+	    }
+	  }
+	}
+	//the starting flow
+	for(OutEdgeIt e(*g,s); e!=INVALID; ++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 ) //putting into the stack
+		{
+		  next.set(w,first[level[w]]);
+		  first[level[w]]=w;
+		}
+	      flow->set(e, (*capacity)[e]);
+	      excess.set(w, excess[w]+rem);
+	    }
+	  }
+	for(InEdgeIt e(*g,s); e!=INVALID; ++e)
+	  {
+	    if ( (*flow)[e] <= 0 ) continue;
+	    Node w=g->tail(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)[e]);
+	      flow->set(e, 0);
+	    }
+	  }
+	break;
+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;
+	  for(InEdgeIt e(*g,v) ; e!=INVALID; ++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 ( z!=INVALID ) left.set(z,w);
+	      right.set(w,z);
+	      level_list[l]=w;
+	      level.set(w, l);
+	    }
+	  }
+	  for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
+	    if ( 0 >= (*flow)[e] ) continue;
+	    Node w=g->head(e);
+	    if ( level[w] == n && w != s ) {
+	      bfs_queue.push(w);
+	      Node z=level_list[l];
+	      if ( z!=INVALID ) left.set(z,w);
+	      right.set(w,z);
+	      level_list[l]=w;
+	      level.set(w, l);
+	    }
+	  }
+	}
+	//the starting flow
+	for(OutEdgeIt e(*g,s) ; e!=INVALID; ++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);
+	  }
+	}
+	for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) {
+	  if ( (*flow)[e] <= 0 ) continue;
+	  Node w=g->tail(e);
+	  if ( level[w] < n ) {
+	    excess.set(w, excess[w]+(*flow)[e]);
+	    flow->set(e, 0);
+	  }
+	}
+	//computing the excess
+	for(NodeIt w(*g); w!=INVALID; ++w) {
+	  Num exc=0;
+	  for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) exc+=(*flow)[e];
+	  for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) exc-=(*flow)[e];
+	  excess.set(w,exc);
+	  //putting the active nodes into the stack
+	  int lev=level[w];
+	    if ( exc > 0 && lev < n && Node(w) != t )
+	      ///\bug	    if ( exc > 0 && lev < n && w != t ) temporarily for working with wrappers.
 	    {
-	      Num c=(*capacity)[e];
+	      next.set(w,first[lev]);
-	      if ( c <= 0 ) continue;
+	      first[lev]=w;
-	      Node w=g->head(e);
+	    }
-	      if ( level[w] < n ) {
+	}
-		if ( excess[w] <= 0 && w!=t ) //putting into the stack
+	break;
-		  {
+} //switch
-		    next.set(w,first[level[w]]);
-		    first[level[w]]=w;
-		  }
-		flow->set(e, c);
-		excess.set(w, excess[w]+c);
-	      }
-	    }
-	  break;
-	}
-case GEN_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 ) {
-		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]);
-		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 ) {
-		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 && Node(w) != t )
-///\bug	    if ( exc > 0 && lev < n && w != t ) tempararily for working with wrappers. in hugo 0.2 it will work. Amugy mukodik sage_graph-fal, de smart_graph-fal nem, azt hozzatennem.
-	      {
-		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,
 Node right_n=right[w];
 Node left_n=left[w];
 //unlacing starts
-if ( g->valid(right_n) ) {
+if ( right_n!=INVALID ) {
-	if ( g->valid(left_n) ) {
+	if ( left_n!=INVALID ) {
 	  right.set(left_n, right_n);
 	  left.set(right_n, left_n);
 	} else {
 	  level_list[lev]=right_n;
 	  left.set(right_n, INVALID);
 	}
 } else {
-	if ( g->valid(left_n) ) {
+	if ( left_n!=INVALID ) {
 	  right.set(left_n, INVALID);
 	} else {
 	  level_list[lev]=INVALID;
 	}
 }
 //unlacing ends
-if ( !g->valid(level_list[lev]) ) {
+if ( level_list[lev]==INVALID ) {
 	//gapping starts
 	for (int i=lev; i!=k ; ) {
 	  Node v=level_list[++i];
-	  while ( g->valid(v) ) {
+	  while ( v!=INVALID ) {
 	    level.set(v,n);
 	    v=right[v];
 	  }
 	  level_list[i]=INVALID;
 	  if ( !what_heur ) first[i]=INVALID;
 	  next.set(w,first[newlevel]);
 	  first[newlevel]=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);
+	  if ( z!=INVALID ) left.set(z,w);
 	  right.set(w,z);
 	  left.set(w,INVALID);
 	  level_list[newlevel]=w;
 	}
 }
 } //relabel
 void printexcess() {////
 std::cout << "Excesses:" <<std::endl;
-NodeIt v;
+for(NodeIt v(*g); v!=INVALID ; ++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(NodeIt v(*g); v!=INVALID ; ++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(NodeIt v(*g); v!=INVALID ; ++v) {
-for(g->first(v); g->valid(v); g->next(v)) {
 	std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
 }
 }

changeset 815	468c9ec86928
parent 773	ce9438c5a82d