COIN-OR::LEMON - Graph Library

Changeset 2518:4c0a23bd70b5 in lemon-0.x


Ignore:
Timestamp:
11/21/07 14:34:38 (17 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3394
Message:

Bugfix in min cut computation

Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/elevator.h

    r2512 r2518  
    5151  class Elevator
    5252  {
    53   private:
     53  public:
    5454
    5555    typedef Item Key;
    5656    typedef int Value;
     57
     58  private:
    5759
    5860    typedef typename std::vector<Item>::iterator Vit;
     
    377379      _level[i]=new_level;
    378380      if(new_level>_highest_active) _highest_active=new_level;
     381    }
     382
     383    ///Mark the node as it did not reach the max level
     384   
     385    ///Mark the node as it did not reach the max level. It sets the
     386    ///level of the node to a low value, which is not connected to the
     387    ///real levels of elevator. The node should be lifted previously
     388    ///to the top level.
     389    void markToBottom(Item i) {
     390      _level[i] = - _max_level;
    379391    }
    380392   
     
    492504  template <class Graph, class Item>
    493505  class LinkedElevator {
    494   private:
     506  public:
    495507
    496508    typedef Item Key;
    497509    typedef int Value;
     510
     511  private:
    498512
    499513    typedef typename ItemSetTraits<Graph,Item>::
     
    883897    }
    884898   
     899    ///Mark the node as it did not reach the max level
     900   
     901    ///Mark the node as it did not reach the max level. It sets the
     902    ///level of the node to a low value, which is not connected to the
     903    ///real levels of elevator. The node should be lifted previously
     904    ///to the top level.
     905    void markToBottom(Item i) {
     906      _level[i] = - _max_level;
     907    }
     908
    885909    ///Lift all nodes on and above a level to the top (and deactivate them).
    886910
  • lemon/goldberg_tarjan.h

    r2514 r2518  
    396396      _node_num = countNodes(_graph);
    397397
    398       _max_tree_size = (double(_node_num) * double(_node_num)) /
    399         double(countEdges(_graph));
     398      _max_tree_size = int((double(_node_num) * double(_node_num)) /
     399                           double(countEdges(_graph)));
    400400
    401401      if (!_flow) {
     
    828828
    829829      for (NodeIt n(_graph); n != INVALID; ++n) {
    830         if ((*_excess)[n] > 0 && _target != n) {
     830        if (!reached[n]) {
     831          _level->markToBottom(n);
     832        } else if ((*_excess)[n] > 0 && _target != n) {
    831833          _level->activate(n);
    832834        }
  • lemon/preflow.h

    r2514 r2518  
    712712      _phase = false;
    713713
    714       typename Graph::template NodeMap<bool> reached(_graph, false);
     714      typename Graph::template NodeMap<bool> reached(_graph);
    715715      for (NodeIt n(_graph); n != INVALID; ++n) {
    716716        reached.set(n, (*_level)[n] < _level->maxLevel());
     
    752752
    753753      for (NodeIt n(_graph); n != INVALID; ++n) {
    754         if ((*_excess)[n] > 0 && _target != n) {
     754        if (!reached[n]) {
     755          _level->markToBottom(n);
     756        } else if ((*_excess)[n] > 0 && _target != n) {
    755757          _level->activate(n);
    756758        }
Note: See TracChangeset for help on using the changeset viewer.