COIN-OR::LEMON - Graph Library

Changeset 2136:4f64d6b3e9ec in lemon-0.x


Ignore:
Timestamp:
07/14/06 11:37:48 (13 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:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bipartite_matching.h

    r2058 r2136  
    13261326        }
    13271327      }
     1328      Value bdistMax = 0;
    13281329
    13291330      while (!_heap->empty()) {
     
    13391340            bdist[bnode] = bvalue;
    13401341            bpred[bnode] = jt;
     1342          }
     1343          if (bvalue > bdistMax) {
     1344            bdistMax = bvalue;
    13411345          }
    13421346          if (bnode_matching[bnode] != INVALID) {
     
    13741378        if (bpred[it] != INVALID) {
    13751379          bnode_potential[it] += bdist[it];
     1380        } else {
     1381          bnode_potential[it] += bdistMax;
    13761382        }
    13771383      }
     
    13811387          if (bpred[bnode] != INVALID) {
    13821388            anode_potential[it] += bdist[bnode];
     1389          } else {
     1390            anode_potential[it] += bdistMax;
    13831391          }
    13841392        }
Note: See TracChangeset for help on using the changeset viewer.