Changeset 2136:4f64d6b3e9ec in lemon-0.x

Timestamp:

07/14/06 11:37:48 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2850

Message:

Bug fix in MinCostMaxBipartiteMatching?
The augmenting phase have not changed the
unreached nodes' potential which caused invalid
dual solution in some cases

File:

• lemon/bipartite_matching.h (modified) (4 diffs)

lemon/bipartite_matching.h

@@ -1326 +1326 @@
         }
       }
+      Value bdistMax = 0;
 
       while (!_heap->empty()) {
@@ -1339 +1340 @@
             bdist[bnode] = bvalue;
             bpred[bnode] = jt;
+          }
+          if (bvalue > bdistMax) {
+            bdistMax = bvalue;
           }
           if (bnode_matching[bnode] != INVALID) {
@@ -1374 +1378 @@
         if (bpred[it] != INVALID) {
           bnode_potential[it] += bdist[it];
+        } else {
+          bnode_potential[it] += bdistMax;
         }
       }
@@ -1381 +1387 @@
           if (bpred[bnode] != INVALID) {
             anode_potential[it] += bdist[bnode];
+          } else {
+            anode_potential[it] += bdistMax;
           }
         }