1.1 --- a/lemon/elevator.h	Tue Nov 20 21:40:55 2007 +0000
     1.2 +++ b/lemon/elevator.h	Wed Nov 21 13:34:38 2007 +0000
     1.3 @@ -50,11 +50,13 @@
     1.4    template<class Graph, class Item>
     1.5    class Elevator 
     1.6    {
     1.7 -  private:
     1.8 +  public:
     1.9  
    1.10      typedef Item Key;
    1.11      typedef int Value;
    1.12  
    1.13 +  private:
    1.14 +
    1.15      typedef typename std::vector<Item>::iterator Vit;
    1.16      typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
    1.17      typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
    1.18 @@ -377,6 +379,16 @@
    1.19        _level[i]=new_level;
    1.20        if(new_level>_highest_active) _highest_active=new_level;
    1.21      }
    1.22 +
    1.23 +    ///Mark the node as it did not reach the max level
    1.24 +    
    1.25 +    ///Mark the node as it did not reach the max level. It sets the
    1.26 +    ///level of the node to a low value, which is not connected to the
    1.27 +    ///real levels of elevator. The node should be lifted previously
    1.28 +    ///to the top level.
    1.29 +    void markToBottom(Item i) {
    1.30 +      _level[i] = - _max_level;
    1.31 +    }
    1.32      
    1.33      ///Lift all nodes on and above a level to the top (and deactivate them).
    1.34  
    1.35 @@ -491,11 +503,13 @@
    1.36    ///Graph::Edge, Graph::UEdge)
    1.37    template <class Graph, class Item>
    1.38    class LinkedElevator {
    1.39 -  private:
    1.40 +  public:
    1.41  
    1.42      typedef Item Key;
    1.43      typedef int Value;
    1.44  
    1.45 +  private:
    1.46 +
    1.47      typedef typename ItemSetTraits<Graph,Item>::
    1.48      template Map<Item>::Type ItemMap;
    1.49      typedef typename ItemSetTraits<Graph,Item>::
    1.50 @@ -882,6 +896,16 @@
    1.51        }
    1.52      }
    1.53      
    1.54 +    ///Mark the node as it did not reach the max level
    1.55 +    
    1.56 +    ///Mark the node as it did not reach the max level. It sets the
    1.57 +    ///level of the node to a low value, which is not connected to the
    1.58 +    ///real levels of elevator. The node should be lifted previously
    1.59 +    ///to the top level.
    1.60 +    void markToBottom(Item i) {
    1.61 +      _level[i] = - _max_level;
    1.62 +    }
    1.63 +
    1.64      ///Lift all nodes on and above a level to the top (and deactivate them).
    1.65  
    1.66      ///This function lifts all nodes on and above level \c l to \c

     2.1 --- a/lemon/goldberg_tarjan.h	Tue Nov 20 21:40:55 2007 +0000
     2.2 +++ b/lemon/goldberg_tarjan.h	Wed Nov 21 13:34:38 2007 +0000
     2.3 @@ -395,8 +395,8 @@
     2.4      void createStructures() {
     2.5        _node_num = countNodes(_graph);
     2.6  
     2.7 -      _max_tree_size = (double(_node_num) * double(_node_num)) / 
     2.8 -	double(countEdges(_graph));
     2.9 +      _max_tree_size = int((double(_node_num) * double(_node_num)) / 
    2.10 +			   double(countEdges(_graph)));
    2.11  
    2.12        if (!_flow) {
    2.13  	_flow = Traits::createFlowMap(_graph);
    2.14 @@ -827,7 +827,9 @@
    2.15        _level->initFinish();
    2.16  
    2.17        for (NodeIt n(_graph); n != INVALID; ++n) {
    2.18 -	if ((*_excess)[n] > 0 && _target != n) {
    2.19 +	if (!reached[n]) {
    2.20 +	  _level->markToBottom(n);
    2.21 +	} else if ((*_excess)[n] > 0 && _target != n) {
    2.22  	  _level->activate(n);
    2.23  	}
    2.24        }

     3.1 --- a/lemon/preflow.h	Tue Nov 20 21:40:55 2007 +0000
     3.2 +++ b/lemon/preflow.h	Wed Nov 21 13:34:38 2007 +0000
     3.3 @@ -711,7 +711,7 @@
     3.4      void startSecondPhase() {
     3.5        _phase = false;
     3.6  
     3.7 -      typename Graph::template NodeMap<bool> reached(_graph, false);
     3.8 +      typename Graph::template NodeMap<bool> reached(_graph);
     3.9        for (NodeIt n(_graph); n != INVALID; ++n) {
    3.10  	reached.set(n, (*_level)[n] < _level->maxLevel());
    3.11        }
    3.12 @@ -751,7 +751,9 @@
    3.13        _level->initFinish();
    3.14  
    3.15        for (NodeIt n(_graph); n != INVALID; ++n) {
    3.16 -	if ((*_excess)[n] > 0 && _target != n) {
    3.17 +	if (!reached[n]) {
    3.18 +	  _level->markToBottom(n);
    3.19 +	} else if ((*_excess)[n] > 0 && _target != n) {
    3.20  	  _level->activate(n);
    3.21  	}
    3.22        }