COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
08/11/07 18:34:41 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3300
Message:

Common interface for bipartite matchings
Some useful query function for push-relabel based matching

The naming should be rethink for these classes
for example: pr-ap prefix for push-relabel and augmenting path
algorithms

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/bipartite_matching_test.cc

    r2391 r2462  
    2525#include <lemon/bpugraph_adaptor.h>
    2626#include <lemon/bipartite_matching.h>
     27#include <lemon/pr_bipartite_matching.h>
    2728
    2829#include <lemon/graph_utils.h>
     
    8990  {
    9091    MaxBipartiteMatching<Graph> bpmatch(graph);
     92
     93    bpmatch.run();
     94
     95    Graph::UEdgeMap<bool> mm(graph);
     96    Graph::NodeMap<bool> cs(graph);
     97   
     98    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
     99   
     100    for (UEdgeIt it(graph); it != INVALID; ++it) {
     101      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
     102    }
     103   
     104    for (ANodeIt it(graph); it != INVALID; ++it) {
     105      int num = 0;
     106      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     107        if (mm[jt]) ++num;
     108      }
     109      check(num <= 1, "INVALID PRIMAL");
     110    }
     111    max_cardinality = bpmatch.matchingSize();
     112  }
     113
     114  {
     115    PrBipartiteMatching<Graph> bpmatch(graph);
    91116
    92117    bpmatch.run();
Note: See TracChangeset for help on using the changeset viewer.