# HG changeset patch
# User deba
# Date 1152869868 0
# Node ID 4f64d6b3e9ecc5e50633539222f3e9fec5f0e352
# Parent  15355b98fb841c549288b4a2bfac4e6836fc5530
Bug fix in MinCostMaxBipartiteMatching
The augmenting phase have not changed the
unreached nodes' potential which caused invalid
dual solution in some cases

diff -r 15355b98fb84 -r 4f64d6b3e9ec lemon/bipartite_matching.h
--- a/lemon/bipartite_matching.h	Wed Jul 12 11:40:52 2006 +0000
+++ b/lemon/bipartite_matching.h	Fri Jul 14 09:37:48 2006 +0000
@@ -1325,6 +1325,7 @@
           _heap->push(it, 0);
         }
       }
+      Value bdistMax = 0;
 
       while (!_heap->empty()) {
         Node anode = _heap->top();
@@ -1339,6 +1340,9 @@
             bdist[bnode] = bvalue;
             bpred[bnode] = jt;
           }
+          if (bvalue > bdistMax) {
+            bdistMax = bvalue;
+          }
           if (bnode_matching[bnode] != INVALID) {
             Node newanode = graph->aNode(bnode_matching[bnode]);
             switch (_heap->state(newanode)) {
@@ -1373,6 +1377,8 @@
       for (BNodeIt it(*graph); it != INVALID; ++it) {
         if (bpred[it] != INVALID) {
           bnode_potential[it] += bdist[it];
+        } else {
+          bnode_potential[it] += bdistMax;
         }
       }
       for (ANodeIt it(*graph); it != INVALID; ++it) {
@@ -1380,6 +1386,8 @@
           Node bnode = graph->bNode(anode_matching[it]);
           if (bpred[bnode] != INVALID) {
             anode_potential[it] += bdist[bnode];
+          } else {
+            anode_potential[it] += bdistMax;
           }
         }
       }