The first step toward function type interface to Preflow alg:
authoralpar
Thu, 17 Mar 2005 10:43:57 +0000
changeset 1222a3fb216a267d
parent 1221 6706c788ebb5
child 1223 decf8076d63c
The first step toward function type interface to Preflow alg:
- Naming changed to be closer in style to the BFD/DFS/Dijkstra triplet.
src/lemon/preflow.h
src/test/preflow_test.cc
     1.1 --- a/src/lemon/preflow.h	Wed Mar 16 17:31:04 2005 +0000
     1.2 +++ b/src/lemon/preflow.h	Thu Mar 17 10:43:57 2005 +0000
     1.3 @@ -37,12 +37,12 @@
     1.4  
     1.5    ///This class provides an implementation of the \e preflow \e
     1.6    ///algorithm producing a flow of maximum value in a directed
     1.7 -  ///graph. The preflow algorithms are the fastest max flow algorithms
     1.8 +  ///graph. The preflow algorithms are the fastest known max flow algorithms
     1.9    ///up to now. The \e source node, the \e target node, the \e
    1.10    ///capacity of the edges and the \e starting \e flow value of the
    1.11    ///edges should be passed to the algorithm through the
    1.12    ///constructor. It is possible to change these quantities using the
    1.13 -  ///functions \ref setSource, \ref setTarget, \ref setCap and \ref
    1.14 +  ///functions \ref source, \ref target, \ref setCap and \ref
    1.15    ///setFlow.
    1.16    ///
    1.17    ///After running \ref lemon::Preflow::phase1() "phase1()"
    1.18 @@ -55,12 +55,12 @@
    1.19    ///
    1.20    ///\param Graph The directed graph type the algorithm runs on.
    1.21    ///\param Num The number type of the capacities and the flow values.
    1.22 -  ///\param CapMap The capacity map type.
    1.23 +  ///\param CapacityMap The capacity map type.
    1.24    ///\param FlowMap The flow map type.
    1.25    ///
    1.26    ///\author Jacint Szabo 
    1.27    template <typename Graph, typename Num,
    1.28 -	    typename CapMap=typename Graph::template EdgeMap<Num>,
    1.29 +	    typename CapacityMap=typename Graph::template EdgeMap<Num>,
    1.30              typename FlowMap=typename Graph::template EdgeMap<Num> >
    1.31    class Preflow {
    1.32    protected:
    1.33 @@ -73,12 +73,12 @@
    1.34      typedef typename Graph::template NodeMap<Node> NNMap;
    1.35      typedef typename std::vector<Node> VecNode;
    1.36  
    1.37 -    const Graph* g;
    1.38 -    Node s;
    1.39 -    Node t;
    1.40 -    const CapMap* capacity;
    1.41 -    FlowMap* flow;
    1.42 -    int n;      //the number of nodes of G
    1.43 +    const Graph* _g;
    1.44 +    Node _source;
    1.45 +    Node _target;
    1.46 +    const CapacityMap* _capacity;
    1.47 +    FlowMap* _flow;
    1.48 +    int _node_num;      //the number of nodes of G
    1.49      
    1.50      typename Graph::template NodeMap<int> level;  
    1.51      typename Graph::template NodeMap<Num> excess;
    1.52 @@ -91,7 +91,8 @@
    1.53  
    1.54      ///Indicates the property of the starting flow map.
    1.55  
    1.56 -    ///Indicates the property of the starting flow map. The meanings are as follows:
    1.57 +    ///Indicates the property of the starting flow map.
    1.58 +    ///The meanings are as follows:
    1.59      ///- \c ZERO_FLOW: constant zero flow
    1.60      ///- \c GEN_FLOW: any flow, i.e. the sum of the in-flows equals to
    1.61      ///the sum of the out-flows in every node except the \e source and
    1.62 @@ -111,8 +112,10 @@
    1.63  
    1.64      ///Indicates the state of the preflow algorithm.
    1.65  
    1.66 -    ///Indicates the state of the preflow algorithm. The meanings are as follows:
    1.67 -    ///- \c AFTER_NOTHING: before running the algorithm or at an unspecified state.
    1.68 +    ///Indicates the state of the preflow algorithm.
    1.69 +    ///The meanings are as follows:
    1.70 +    ///- \c AFTER_NOTHING: before running the algorithm or
    1.71 +    ///  at an unspecified state.
    1.72      ///- \c AFTER_PREFLOW_PHASE_1: right after running \c phase1
    1.73      ///- \c AFTER_PREFLOW_PHASE_2: after running \ref phase2()
    1.74      ///
    1.75 @@ -133,15 +136,15 @@
    1.76      ///\param _G The directed graph the algorithm runs on. 
    1.77      ///\param _s The source node.
    1.78      ///\param _t The target node.
    1.79 -    ///\param _capacity The capacity of the edges. 
    1.80 -    ///\param _flow The flow of the edges. 
    1.81 +    ///\param _cap The capacity of the edges. 
    1.82 +    ///\param _f The flow of the edges. 
    1.83      ///Except the graph, all of these parameters can be reset by
    1.84 -    ///calling \ref setSource, \ref setTarget, \ref setCap and \ref
    1.85 +    ///calling \ref source, \ref target, \ref setCap and \ref
    1.86      ///setFlow, resp.
    1.87 -      Preflow(const Graph& _G, Node _s, Node _t, 
    1.88 -	      const CapMap& _capacity, FlowMap& _flow) :
    1.89 -	g(&_G), s(_s), t(_t), capacity(&_capacity),
    1.90 -	flow(&_flow), n(countNodes(_G)), level(_G), excess(_G,0), 
    1.91 +      Preflow(const Graph& _gr, Node _s, Node _t, 
    1.92 +	      const CapacityMap& _cap, FlowMap& _f) :
    1.93 +	_g(&_gr), _source(_s), _target(_t), _capacity(&_cap),
    1.94 +	_flow(&_f), _node_num(countNodes(_gr)), level(_gr), excess(_gr,0), 
    1.95  	flow_prop(NO_FLOW), status(AFTER_NOTHING) { }
    1.96  
    1.97  
    1.98 @@ -204,8 +207,8 @@
    1.99      ///give minimum value cuts unless calling \ref phase2().
   1.100      void phase1()
   1.101      {
   1.102 -      int heur0=(int)(H0*n);  //time while running 'bound decrease'
   1.103 -      int heur1=(int)(H1*n);  //time while running 'highest label'
   1.104 +      int heur0=(int)(H0*_node_num);  //time while running 'bound decrease'
   1.105 +      int heur1=(int)(H1*_node_num);  //time while running 'highest label'
   1.106        int heur=heur1;         //starting time interval (#of relabels)
   1.107        int numrelabel=0;
   1.108  
   1.109 @@ -216,15 +219,15 @@
   1.110        //Needed for 'bound decrease', true means no active 
   1.111        //nodes are above bound b.
   1.112  
   1.113 -      int k=n-2;  //bound on the highest level under n containing a node
   1.114 +      int k=_node_num-2;  //bound on the highest level under n containing a node
   1.115        int b=k;    //bound on the highest level under n of an active node
   1.116  
   1.117 -      VecNode first(n, INVALID);
   1.118 -      NNMap next(*g, INVALID);
   1.119 +      VecNode first(_node_num, INVALID);
   1.120 +      NNMap next(*_g, INVALID);
   1.121  
   1.122 -      NNMap left(*g, INVALID);
   1.123 -      NNMap right(*g, INVALID);
   1.124 -      VecNode level_list(n,INVALID);
   1.125 +      NNMap left(*_g, INVALID);
   1.126 +      NNMap right(*_g, INVALID);
   1.127 +      VecNode level_list(_node_num,INVALID);
   1.128        //List of the nodes in level i<n, set to n.
   1.129  
   1.130        preflowPreproc(first, next, level_list, left, right);
   1.131 @@ -271,7 +274,8 @@
   1.132      //   list 'level_list' on the nodes on level i implemented by hand
   1.133      //   stack 'active' on the active nodes on level i      
   1.134      //   runs heuristic 'highest label' for H1*n relabels
   1.135 -    //   runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
   1.136 +    //   runs heuristic 'bound decrease' for H0*n relabels,
   1.137 +    //        starts with 'highest label'
   1.138      //   Parameters H0 and H1 are initialized to 20 and 1.
   1.139  
   1.140  
   1.141 @@ -287,15 +291,15 @@
   1.142      void phase2()
   1.143      {
   1.144  
   1.145 -      int k=n-2;  //bound on the highest level under n containing a node
   1.146 +      int k=_node_num-2;  //bound on the highest level under n containing a node
   1.147        int b=k;    //bound on the highest level under n of an active node
   1.148  
   1.149      
   1.150 -      VecNode first(n, INVALID);
   1.151 -      NNMap next(*g, INVALID); 
   1.152 -      level.set(s,0);
   1.153 +      VecNode first(_node_num, INVALID);
   1.154 +      NNMap next(*_g, INVALID); 
   1.155 +      level.set(_source,0);
   1.156        std::queue<Node> bfs_queue;
   1.157 -      bfs_queue.push(s);
   1.158 +      bfs_queue.push(_source);
   1.159  
   1.160        while ( !bfs_queue.empty() ) {
   1.161  
   1.162 @@ -303,10 +307,10 @@
   1.163  	bfs_queue.pop();
   1.164  	int l=level[v]+1;
   1.165  
   1.166 -	for(InEdgeIt e(*g,v); e!=INVALID; ++e) {
   1.167 -	  if ( (*capacity)[e] <= (*flow)[e] ) continue;
   1.168 -	  Node u=g->source(e);
   1.169 -	  if ( level[u] >= n ) {
   1.170 +	for(InEdgeIt e(*_g,v); e!=INVALID; ++e) {
   1.171 +	  if ( (*_capacity)[e] <= (*_flow)[e] ) continue;
   1.172 +	  Node u=_g->source(e);
   1.173 +	  if ( level[u] >= _node_num ) {
   1.174  	    bfs_queue.push(u);
   1.175  	    level.set(u, l);
   1.176  	    if ( excess[u] > 0 ) {
   1.177 @@ -316,10 +320,10 @@
   1.178  	  }
   1.179  	}
   1.180  
   1.181 -	for(OutEdgeIt e(*g,v); e!=INVALID; ++e) {
   1.182 -	  if ( 0 >= (*flow)[e] ) continue;
   1.183 -	  Node u=g->target(e);
   1.184 -	  if ( level[u] >= n ) {
   1.185 +	for(OutEdgeIt e(*_g,v); e!=INVALID; ++e) {
   1.186 +	  if ( 0 >= (*_flow)[e] ) continue;
   1.187 +	  Node u=_g->target(e);
   1.188 +	  if ( level[u] >= _node_num ) {
   1.189  	    bfs_queue.push(u);
   1.190  	    level.set(u, l);
   1.191  	    if ( excess[u] > 0 ) {
   1.192 @@ -329,7 +333,7 @@
   1.193  	  }
   1.194  	}
   1.195        }
   1.196 -      b=n-2;
   1.197 +      b=_node_num-2;
   1.198  
   1.199        while ( true ) {
   1.200  
   1.201 @@ -359,7 +363,7 @@
   1.202      /// of the target node \c t. This value equals to the value of
   1.203      /// the maximum flow already after running \ref phase1.
   1.204      Num flowValue() const {
   1.205 -      return excess[t];
   1.206 +      return excess[_target];
   1.207      }
   1.208  
   1.209  
   1.210 @@ -375,8 +379,8 @@
   1.211      void minCut(_CutMap& M) const {
   1.212        switch ( status ) {
   1.213  	case AFTER_PREFLOW_PHASE_1:
   1.214 -	for(NodeIt v(*g); v!=INVALID; ++v) {
   1.215 -	  if (level[v] < n) {
   1.216 +	for(NodeIt v(*_g); v!=INVALID; ++v) {
   1.217 +	  if (level[v] < _node_num) {
   1.218  	    M.set(v, false);
   1.219  	  } else {
   1.220  	    M.set(v, true);
   1.221 @@ -402,24 +406,24 @@
   1.222      void minMinCut(_CutMap& M) const {
   1.223  
   1.224        std::queue<Node> queue;
   1.225 -      M.set(s,true);
   1.226 +      M.set(_source,true);
   1.227        queue.push(s);
   1.228        
   1.229        while (!queue.empty()) {
   1.230  	Node w=queue.front();
   1.231  	queue.pop();
   1.232  	
   1.233 -	for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
   1.234 -	  Node v=g->target(e);
   1.235 -	  if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
   1.236 +	for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
   1.237 +	  Node v=_g->target(e);
   1.238 +	  if (!M[v] && (*_flow)[e] < (*_capacity)[e] ) {
   1.239  	    queue.push(v);
   1.240  	    M.set(v, true);
   1.241  	  }
   1.242  	}
   1.243  	
   1.244 -	for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
   1.245 -	  Node v=g->source(e);
   1.246 -	  if (!M[v] && (*flow)[e] > 0 ) {
   1.247 +	for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
   1.248 +	  Node v=_g->source(e);
   1.249 +	  if (!M[v] && (*_flow)[e] > 0 ) {
   1.250  	    queue.push(v);
   1.251  	    M.set(v, true);
   1.252  	  }
   1.253 @@ -436,28 +440,28 @@
   1.254      template<typename _CutMap>
   1.255      void maxMinCut(_CutMap& M) const {
   1.256  
   1.257 -      for(NodeIt v(*g) ; v!=INVALID; ++v) M.set(v, true);
   1.258 +      for(NodeIt v(*_g) ; v!=INVALID; ++v) M.set(v, true);
   1.259  
   1.260        std::queue<Node> queue;
   1.261  
   1.262 -      M.set(t,false);
   1.263 -      queue.push(t);
   1.264 +      M.set(_target,false);
   1.265 +      queue.push(_target);
   1.266  
   1.267        while (!queue.empty()) {
   1.268          Node w=queue.front();
   1.269  	queue.pop();
   1.270  
   1.271 -	for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
   1.272 -	  Node v=g->source(e);
   1.273 -	  if (M[v] && (*flow)[e] < (*capacity)[e] ) {
   1.274 +	for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
   1.275 +	  Node v=_g->source(e);
   1.276 +	  if (M[v] && (*_flow)[e] < (*_capacity)[e] ) {
   1.277  	    queue.push(v);
   1.278  	    M.set(v, false);
   1.279  	  }
   1.280  	}
   1.281  
   1.282 -	for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
   1.283 -	  Node v=g->target(e);
   1.284 -	  if (M[v] && (*flow)[e] > 0 ) {
   1.285 +	for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
   1.286 +	  Node v=_g->target(e);
   1.287 +	  if (M[v] && (*_flow)[e] > 0 ) {
   1.288  	    queue.push(v);
   1.289  	    M.set(v, false);
   1.290  	  }
   1.291 @@ -469,41 +473,71 @@
   1.292  
   1.293      ///Sets the source node to \c _s.
   1.294      /// 
   1.295 -    void setSource(Node _s) { 
   1.296 -      s=_s; 
   1.297 +    void source(Node _s) { 
   1.298 +      _source=_s; 
   1.299        if ( flow_prop != ZERO_FLOW ) flow_prop=NO_FLOW;
   1.300        status=AFTER_NOTHING; 
   1.301      }
   1.302  
   1.303 +    ///Returns the source node.
   1.304 +
   1.305 +    ///Returns the source node.
   1.306 +    /// 
   1.307 +    Node source() const { 
   1.308 +      return _source;
   1.309 +    }
   1.310 +
   1.311      ///Sets the target node to \c _t.
   1.312  
   1.313      ///Sets the target node to \c _t.
   1.314      ///
   1.315 -    void setTarget(Node _t) { 
   1.316 -      t=_t; 
   1.317 +    void target(Node _t) { 
   1.318 +      _target=_t; 
   1.319        if ( flow_prop == GEN_FLOW ) flow_prop=PRE_FLOW;
   1.320        status=AFTER_NOTHING; 
   1.321      }
   1.322  
   1.323 +    ///Returns the target node.
   1.324 +
   1.325 +    ///Returns the target node.
   1.326 +    /// 
   1.327 +    Node target() const { 
   1.328 +      return _target;
   1.329 +    }
   1.330 +
   1.331      /// Sets the edge map of the capacities to _cap.
   1.332  
   1.333      /// Sets the edge map of the capacities to _cap.
   1.334      /// 
   1.335 -    void setCap(const CapMap& _cap) { 
   1.336 -      capacity=&_cap; 
   1.337 +    void capacityMap(const CapacityMap& _cap) { 
   1.338 +      _capacity=&_cap; 
   1.339        status=AFTER_NOTHING; 
   1.340      }
   1.341 +    /// Returns a reference to to capacity map.
   1.342 +
   1.343 +    /// Returns a reference to to capacity map.
   1.344 +    /// 
   1.345 +    const CapacityMap &capacityMap() const { 
   1.346 +      return *_capacity;
   1.347 +    }
   1.348  
   1.349      /// Sets the edge map of the flows to _flow.
   1.350  
   1.351      /// Sets the edge map of the flows to _flow.
   1.352      /// 
   1.353 -    void setFlow(FlowMap& _flow) { 
   1.354 -      flow=&_flow; 
   1.355 +    void flowMap(FlowMap& _f) { 
   1.356 +      _flow=&_f; 
   1.357        flow_prop=NO_FLOW;
   1.358        status=AFTER_NOTHING; 
   1.359      }
   1.360 +     
   1.361 +    /// Returns a reference to to flow map.
   1.362  
   1.363 +    /// Returns a reference to to flow map.
   1.364 +    /// 
   1.365 +    const FlowMap &flowMap() const { 
   1.366 +      return *_flow;
   1.367 +    }
   1.368  
   1.369    private:
   1.370  
   1.371 @@ -511,32 +545,32 @@
   1.372  
   1.373        int lev=level[w];
   1.374        Num exc=excess[w];
   1.375 -      int newlevel=n;       //bound on the next level of w
   1.376 +      int newlevel=_node_num;       //bound on the next level of w
   1.377  
   1.378 -      for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
   1.379 -	if ( (*flow)[e] >= (*capacity)[e] ) continue;
   1.380 -	Node v=g->target(e);
   1.381 +      for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
   1.382 +	if ( (*_flow)[e] >= (*_capacity)[e] ) continue;
   1.383 +	Node v=_g->target(e);
   1.384  
   1.385  	if( lev > level[v] ) { //Push is allowed now
   1.386  	  
   1.387 -	  if ( excess[v]<=0 && v!=t && v!=s ) {
   1.388 +	  if ( excess[v]<=0 && v!=_target && v!=_source ) {
   1.389  	    next.set(v,first[level[v]]);
   1.390  	    first[level[v]]=v;
   1.391  	  }
   1.392  
   1.393 -	  Num cap=(*capacity)[e];
   1.394 -	  Num flo=(*flow)[e];
   1.395 +	  Num cap=(*_capacity)[e];
   1.396 +	  Num flo=(*_flow)[e];
   1.397  	  Num remcap=cap-flo;
   1.398  	  
   1.399  	  if ( remcap >= exc ) { //A nonsaturating push.
   1.400  	    
   1.401 -	    flow->set(e, flo+exc);
   1.402 +	    _flow->set(e, flo+exc);
   1.403  	    excess.set(v, excess[v]+exc);
   1.404  	    exc=0;
   1.405  	    break;
   1.406  
   1.407  	  } else { //A saturating push.
   1.408 -	    flow->set(e, cap);
   1.409 +	    _flow->set(e, cap);
   1.410  	    excess.set(v, excess[v]+remcap);
   1.411  	    exc-=remcap;
   1.412  	  }
   1.413 @@ -544,23 +578,23 @@
   1.414        } //for out edges wv
   1.415  
   1.416        if ( exc > 0 ) {
   1.417 -	for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
   1.418 +	for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
   1.419  	  
   1.420 -	  if( (*flow)[e] <= 0 ) continue;
   1.421 -	  Node v=g->source(e);
   1.422 +	  if( (*_flow)[e] <= 0 ) continue;
   1.423 +	  Node v=_g->source(e);
   1.424  
   1.425  	  if( lev > level[v] ) { //Push is allowed now
   1.426  
   1.427 -	    if ( excess[v]<=0 && v!=t && v!=s ) {
   1.428 +	    if ( excess[v]<=0 && v!=_target && v!=_source ) {
   1.429  	      next.set(v,first[level[v]]);
   1.430  	      first[level[v]]=v;
   1.431  	    }
   1.432  
   1.433 -	    Num flo=(*flow)[e];
   1.434 +	    Num flo=(*_flow)[e];
   1.435  
   1.436  	    if ( flo >= exc ) { //A nonsaturating push.
   1.437  
   1.438 -	      flow->set(e, flo-exc);
   1.439 +	      _flow->set(e, flo-exc);
   1.440  	      excess.set(v, excess[v]+exc);
   1.441  	      exc=0;
   1.442  	      break;
   1.443 @@ -568,7 +602,7 @@
   1.444  
   1.445  	      excess.set(v, excess[v]+flo);
   1.446  	      exc-=flo;
   1.447 -	      flow->set(e,0);
   1.448 +	      _flow->set(e,0);
   1.449  	    }
   1.450  	  } else if ( newlevel > level[v] ) newlevel = level[v];
   1.451  	} //for in edges vw
   1.452 @@ -585,14 +619,14 @@
   1.453      void preflowPreproc(VecNode& first, NNMap& next, 
   1.454  			VecNode& level_list, NNMap& left, NNMap& right)
   1.455      {
   1.456 -      for(NodeIt v(*g); v!=INVALID; ++v) level.set(v,n);
   1.457 +      for(NodeIt v(*_g); v!=INVALID; ++v) level.set(v,_node_num);
   1.458        std::queue<Node> bfs_queue;
   1.459        
   1.460        if ( flow_prop == GEN_FLOW || flow_prop == PRE_FLOW ) {
   1.461  	//Reverse_bfs from t in the residual graph,
   1.462  	//to find the starting level.
   1.463 -	level.set(t,0);
   1.464 -	bfs_queue.push(t);
   1.465 +	level.set(_target,0);
   1.466 +	bfs_queue.push(_target);
   1.467  	
   1.468  	while ( !bfs_queue.empty() ) {
   1.469  	  
   1.470 @@ -600,10 +634,10 @@
   1.471  	  bfs_queue.pop();
   1.472  	  int l=level[v]+1;
   1.473  	  
   1.474 -	  for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
   1.475 -	    if ( (*capacity)[e] <= (*flow)[e] ) continue;
   1.476 -	    Node w=g->source(e);
   1.477 -	    if ( level[w] == n && w != s ) {
   1.478 +	  for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
   1.479 +	    if ( (*_capacity)[e] <= (*_flow)[e] ) continue;
   1.480 +	    Node w=_g->source(e);
   1.481 +	    if ( level[w] == _node_num && w != _source ) {
   1.482  	      bfs_queue.push(w);
   1.483  	      Node z=level_list[l];
   1.484  	      if ( z!=INVALID ) left.set(z,w);
   1.485 @@ -613,10 +647,10 @@
   1.486  	    }
   1.487  	  }
   1.488  	  
   1.489 -	  for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
   1.490 -	    if ( 0 >= (*flow)[e] ) continue;
   1.491 -	    Node w=g->target(e);
   1.492 -	    if ( level[w] == n && w != s ) {
   1.493 +	  for(OutEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
   1.494 +	    if ( 0 >= (*_flow)[e] ) continue;
   1.495 +	    Node w=_g->target(e);
   1.496 +	    if ( level[w] == _node_num && w != _source ) {
   1.497  	      bfs_queue.push(w);
   1.498  	      Node z=level_list[l];
   1.499  	      if ( z!=INVALID ) left.set(z,w);
   1.500 @@ -631,13 +665,13 @@
   1.501  
   1.502        switch (flow_prop) {
   1.503  	case NO_FLOW:  
   1.504 -	for(EdgeIt e(*g); e!=INVALID; ++e) flow->set(e,0);
   1.505 +	for(EdgeIt e(*_g); e!=INVALID; ++e) _flow->set(e,0);
   1.506  	case ZERO_FLOW:
   1.507 -	for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
   1.508 +	for(NodeIt v(*_g); v!=INVALID; ++v) excess.set(v,0);
   1.509  	
   1.510  	//Reverse_bfs from t, to find the starting level.
   1.511 -	level.set(t,0);
   1.512 -	bfs_queue.push(t);
   1.513 +	level.set(_target,0);
   1.514 +	bfs_queue.push(_target);
   1.515  	
   1.516  	while ( !bfs_queue.empty() ) {
   1.517  	  
   1.518 @@ -645,9 +679,9 @@
   1.519  	  bfs_queue.pop();
   1.520  	  int l=level[v]+1;
   1.521  	  
   1.522 -	  for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
   1.523 -	    Node w=g->source(e);
   1.524 -	    if ( level[w] == n && w != s ) {
   1.525 +	  for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
   1.526 +	    Node w=_g->source(e);
   1.527 +	    if ( level[w] == _node_num && w != _source ) {
   1.528  	      bfs_queue.push(w);
   1.529  	      Node z=level_list[l];
   1.530  	      if ( z!=INVALID ) left.set(z,w);
   1.531 @@ -659,84 +693,84 @@
   1.532  	}
   1.533  	
   1.534  	//the starting flow
   1.535 -	for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) {
   1.536 -	  Num c=(*capacity)[e];
   1.537 +	for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
   1.538 +	  Num c=(*_capacity)[e];
   1.539  	  if ( c <= 0 ) continue;
   1.540 -	  Node w=g->target(e);
   1.541 -	  if ( level[w] < n ) {
   1.542 -	    if ( excess[w] <= 0 && w!=t ) { //putting into the stack
   1.543 +	  Node w=_g->target(e);
   1.544 +	  if ( level[w] < _node_num ) {
   1.545 +	    if ( excess[w] <= 0 && w!=_target ) { //putting into the stack
   1.546  	      next.set(w,first[level[w]]);
   1.547  	      first[level[w]]=w;
   1.548  	    }
   1.549 -	    flow->set(e, c);
   1.550 +	    _flow->set(e, c);
   1.551  	    excess.set(w, excess[w]+c);
   1.552  	  }
   1.553  	}
   1.554  	break;
   1.555  
   1.556  	case GEN_FLOW:
   1.557 -	for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
   1.558 +	for(NodeIt v(*_g); v!=INVALID; ++v) excess.set(v,0);
   1.559  	{
   1.560  	  Num exc=0;
   1.561 -	  for(InEdgeIt e(*g,t) ; e!=INVALID; ++e) exc+=(*flow)[e];
   1.562 -	  for(OutEdgeIt e(*g,t) ; e!=INVALID; ++e) exc-=(*flow)[e];
   1.563 -	  excess.set(t,exc);
   1.564 +	  for(InEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc+=(*_flow)[e];
   1.565 +	  for(OutEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc-=(*_flow)[e];
   1.566 +	  excess.set(_target,exc);
   1.567  	}
   1.568  
   1.569  	//the starting flow
   1.570 -	for(OutEdgeIt e(*g,s); e!=INVALID; ++e)	{
   1.571 -	  Num rem=(*capacity)[e]-(*flow)[e];
   1.572 +	for(OutEdgeIt e(*_g,_source); e!=INVALID; ++e)	{
   1.573 +	  Num rem=(*_capacity)[e]-(*_flow)[e];
   1.574  	  if ( rem <= 0 ) continue;
   1.575 -	  Node w=g->target(e);
   1.576 -	  if ( level[w] < n ) {
   1.577 -	    if ( excess[w] <= 0 && w!=t ) { //putting into the stack
   1.578 +	  Node w=_g->target(e);
   1.579 +	  if ( level[w] < _node_num ) {
   1.580 +	    if ( excess[w] <= 0 && w!=_target ) { //putting into the stack
   1.581  	      next.set(w,first[level[w]]);
   1.582  	      first[level[w]]=w;
   1.583  	    }   
   1.584 -	    flow->set(e, (*capacity)[e]);
   1.585 +	    _flow->set(e, (*_capacity)[e]);
   1.586  	    excess.set(w, excess[w]+rem);
   1.587  	  }
   1.588  	}
   1.589  	
   1.590 -	for(InEdgeIt e(*g,s); e!=INVALID; ++e) {
   1.591 -	  if ( (*flow)[e] <= 0 ) continue;
   1.592 -	  Node w=g->source(e);
   1.593 -	  if ( level[w] < n ) {
   1.594 -	    if ( excess[w] <= 0 && w!=t ) {
   1.595 +	for(InEdgeIt e(*_g,_source); e!=INVALID; ++e) {
   1.596 +	  if ( (*_flow)[e] <= 0 ) continue;
   1.597 +	  Node w=_g->source(e);
   1.598 +	  if ( level[w] < _node_num ) {
   1.599 +	    if ( excess[w] <= 0 && w!=_target ) {
   1.600  	      next.set(w,first[level[w]]);
   1.601  	      first[level[w]]=w;
   1.602  	    }  
   1.603 -	    excess.set(w, excess[w]+(*flow)[e]);
   1.604 -	    flow->set(e, 0);
   1.605 +	    excess.set(w, excess[w]+(*_flow)[e]);
   1.606 +	    _flow->set(e, 0);
   1.607  	  }
   1.608  	}
   1.609  	break;
   1.610  
   1.611  	case PRE_FLOW:	
   1.612  	//the starting flow
   1.613 -	for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) {
   1.614 -	  Num rem=(*capacity)[e]-(*flow)[e];
   1.615 +	for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
   1.616 +	  Num rem=(*_capacity)[e]-(*_flow)[e];
   1.617  	  if ( rem <= 0 ) continue;
   1.618 -	  Node w=g->target(e);
   1.619 -	  if ( level[w] < n ) flow->set(e, (*capacity)[e]);
   1.620 +	  Node w=_g->target(e);
   1.621 +	  if ( level[w] < _node_num ) _flow->set(e, (*_capacity)[e]);
   1.622  	}
   1.623  	
   1.624 -	for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) {
   1.625 -	  if ( (*flow)[e] <= 0 ) continue;
   1.626 -	  Node w=g->source(e);
   1.627 -	  if ( level[w] < n ) flow->set(e, 0);
   1.628 +	for(InEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
   1.629 +	  if ( (*_flow)[e] <= 0 ) continue;
   1.630 +	  Node w=_g->source(e);
   1.631 +	  if ( level[w] < _node_num ) _flow->set(e, 0);
   1.632  	}
   1.633  	
   1.634  	//computing the excess
   1.635 -	for(NodeIt w(*g); w!=INVALID; ++w) {
   1.636 +	for(NodeIt w(*_g); w!=INVALID; ++w) {
   1.637  	  Num exc=0;
   1.638 -	  for(InEdgeIt e(*g,w); e!=INVALID; ++e) exc+=(*flow)[e];
   1.639 -	  for(OutEdgeIt e(*g,w); e!=INVALID; ++e) exc-=(*flow)[e];
   1.640 +	  for(InEdgeIt e(*_g,w); e!=INVALID; ++e) exc+=(*_flow)[e];
   1.641 +	  for(OutEdgeIt e(*_g,w); e!=INVALID; ++e) exc-=(*_flow)[e];
   1.642  	  excess.set(w,exc);
   1.643  	  
   1.644  	  //putting the active nodes into the stack
   1.645  	  int lev=level[w];
   1.646 -	    if ( exc > 0 && lev < n && Node(w) != t ) {
   1.647 +	    if ( exc > 0 && lev < _node_num && Node(w) != _target ) {
   1.648  	      next.set(w,first[lev]);
   1.649  	      first[lev]=w;
   1.650  	    }
   1.651 @@ -780,21 +814,21 @@
   1.652  	for (int i=lev; i!=k ; ) {
   1.653  	  Node v=level_list[++i];
   1.654  	  while ( v!=INVALID ) {
   1.655 -	    level.set(v,n);
   1.656 +	    level.set(v,_node_num);
   1.657  	    v=right[v];
   1.658  	  }
   1.659  	  level_list[i]=INVALID;
   1.660  	  if ( !what_heur ) first[i]=INVALID;
   1.661  	}
   1.662  
   1.663 -	level.set(w,n);
   1.664 +	level.set(w,_node_num);
   1.665  	b=lev-1;
   1.666  	k=b;
   1.667  	//gapping ends
   1.668  
   1.669        } else {
   1.670  
   1.671 -	if ( newlevel == n ) level.set(w,n);
   1.672 +	if ( newlevel == _node_num ) level.set(w,_node_num);
   1.673  	else {
   1.674  	  level.set(w,++newlevel);
   1.675  	  next.set(w,first[newlevel]);
     2.1 --- a/src/test/preflow_test.cc	Wed Mar 16 17:31:04 2005 +0000
     2.2 +++ b/src/test/preflow_test.cc	Thu Mar 17 10:43:57 2005 +0000
     2.3 @@ -49,15 +49,15 @@
     2.4  
     2.5    preflow_test.run();
     2.6    preflow_test.flowValue();
     2.7 -  preflow_test.setSource(n);
     2.8 -  preflow_test.setFlow(flow);
     2.9 +  preflow_test.source(n);
    2.10 +  preflow_test.flowMap(flow);
    2.11  
    2.12    preflow_test.phase1(PType::NO_FLOW);
    2.13    preflow_test.minCut(cut);
    2.14  
    2.15    preflow_test.phase2();
    2.16 -  preflow_test.setTarget(n);
    2.17 -  preflow_test.setCap(cap);
    2.18 +  preflow_test.target(n);
    2.19 +  preflow_test.capacityMap(cap);
    2.20    preflow_test.minMinCut(cut);
    2.21    preflow_test.maxMinCut(cut);
    2.22  }
    2.23 @@ -129,7 +129,7 @@
    2.24  
    2.25  
    2.26    for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; 
    2.27 -  preflow_test.setCap(cap);  
    2.28 +  preflow_test.capacityMap(cap);  
    2.29  
    2.30    preflow_test.phase1(PType::PRE_FLOW);
    2.31  
    2.32 @@ -168,7 +168,7 @@
    2.33      ++e;
    2.34    }
    2.35  
    2.36 -  preflow_test.setFlow(flow); 
    2.37 +  preflow_test.flowMap(flow); 
    2.38  
    2.39    NodeIt tmp1(g,s);
    2.40    ++tmp1;
    2.41 @@ -178,8 +178,8 @@
    2.42    ++tmp2;
    2.43    if ( tmp2 != INVALID ) t=tmp2;
    2.44  
    2.45 -  preflow_test.setSource(s);
    2.46 -  preflow_test.setTarget(t); 
    2.47 +  preflow_test.source(s);
    2.48 +  preflow_test.target(t); 
    2.49    
    2.50    preflow_test.run();
    2.51