Changeset 2518:4c0a23bd70b5 in lemon-0.x

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:

• elevator.h (modified) (4 diffs)
• goldberg_tarjan.h (modified) (2 diffs)
• preflow.h (modified) (2 diffs)

lemon/elevator.h

@@ -51 +51 @@
   class Elevator 
   {
-  private:
+  public:
 
     typedef Item Key;
     typedef int Value;
+
+  private:
 
     typedef typename std::vector<Item>::iterator Vit;
@@ -377 +379 @@
       _level[i]=new_level;
       if(new_level>_highest_active) _highest_active=new_level;
+    }
+
+    ///Mark the node as it did not reach the max level
+    
+    ///Mark the node as it did not reach the max level. It sets the
+    ///level of the node to a low value, which is not connected to the
+    ///real levels of elevator. The node should be lifted previously
+    ///to the top level.
+    void markToBottom(Item i) {
+      _level[i] = - _max_level;
     }
     
@@ -492 +504 @@
   template <class Graph, class Item>
   class LinkedElevator {
-  private:
+  public:
 
     typedef Item Key;
     typedef int Value;
+
+  private:
 
     typedef typename ItemSetTraits<Graph,Item>::
@@ -883 +897 @@
     }
     
+    ///Mark the node as it did not reach the max level
+    
+    ///Mark the node as it did not reach the max level. It sets the
+    ///level of the node to a low value, which is not connected to the
+    ///real levels of elevator. The node should be lifted previously
+    ///to the top level.
+    void markToBottom(Item i) {
+      _level[i] = - _max_level;
+    }
+
     ///Lift all nodes on and above a level to the top (and deactivate them).
 

lemon/goldberg_tarjan.h

@@ -396 +396 @@
       _node_num = countNodes(_graph);
 
-      _max_tree_size = (double(_node_num) * double(_node_num)) / 
-        double(countEdges(_graph));
+      _max_tree_size = int((double(_node_num) * double(_node_num)) / 
+                           double(countEdges(_graph)));
 
       if (!_flow) {
@@ -828 +828 @@
 
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        if ((*_excess)[n] > 0 && _target != n) {
+        if (!reached[n]) {
+          _level->markToBottom(n);
+        } else if ((*_excess)[n] > 0 && _target != n) {
           _level->activate(n);
         }

lemon/preflow.h

@@ -712 +712 @@
       _phase = false;
 
-      typename Graph::template NodeMap<bool> reached(_graph, false);
+      typename Graph::template NodeMap<bool> reached(_graph);
       for (NodeIt n(_graph); n != INVALID; ++n) {
         reached.set(n, (*_level)[n] < _level->maxLevel());
@@ -752 +752 @@
 
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        if ((*_excess)[n] > 0 && _target != n) {
+        if (!reached[n]) {
+          _level->markToBottom(n);
+        } else if ((*_excess)[n] > 0 && _target != n) {
           _level->activate(n);
         }