COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
04/14/06 20:07:33 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2694
Message:

MaxWeightedBipartiteMatching?
MinCostMaxBipartiteMatching?

Both algorithms are based on successive shortest
path algorithm with dijkstra shortest path
finding

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/bipartite_matching_test.cc

    r2040 r2051  
    99
    1010#include <lemon/graph_utils.h>
     11
     12#include <lemon/maps.h>
    1113
    1214#include "test_tools.h"
     
    2527  int m = argc > 2 ? atoi(argv[2]) : 100;
    2628  int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
     29  int c = argc > 4 ? atoi(argv[4]) : 100;
     30
     31  Graph::UEdgeMap<int> weight(graph);
     32
     33  int max_cardinality;
     34  int max_weight;
     35  int max_cardinality_max_weight;
    2736
    2837  for (int i = 0; i < n; ++i) {
     
    3746    Node aNode = aNodes[urandom(n)];
    3847    Node bNode = bNodes[urandom(m)];
    39     graph.addEdge(aNode, bNode);
     48    UEdge uedge = graph.addEdge(aNode, bNode);
     49    weight[uedge] = urandom(c);
    4050  }
    4151
     
    5868      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    5969        if (mm[jt]) ++num;
    60     }
    61       check(num <= 1, "INVALID PRIMAL");
    62     }
     70      }
     71      check(num <= 1, "INVALID PRIMAL");
     72    }
     73    max_cardinality = bpmatch.matchingSize();
    6374  }
    6475
     
    112123
    113124  {
    114     SwapBpUGraphAdaptor<Graph> swapgraph(graph);
    115     MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
     125    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
     126
     127    bpmatch.init();
     128
     129    max_weight = 0;
     130    while (bpmatch.augment(true)) {
     131   
     132      Graph::UEdgeMap<bool> mm(graph);
     133      Graph::NodeMap<int> pm(graph);
     134     
     135      bpmatch.matching(mm);
     136      bpmatch.potential(pm);
     137     
     138      for (UEdgeIt it(graph); it != INVALID; ++it) {
     139        if (mm[it]) {
     140          check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
     141                "INVALID DUAL");
     142        } else {
     143          check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
     144                "INVALID DUAL");
     145        }
     146      }
     147
     148      for (ANodeIt it(graph); it != INVALID; ++it) {
     149        int num = 0;
     150        for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     151          if (mm[jt]) ++num;
     152        }
     153        check(num <= 1, "INVALID PRIMAL");
     154      }
     155      if (bpmatch.matchingValue() > max_weight) {
     156        max_weight = bpmatch.matchingValue();
     157      }
     158    }
     159  }
     160
     161  {
     162    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
    116163
    117164    bpmatch.run();
    118 
    119     Graph::UEdgeMap<bool> mm(graph);
    120     Graph::NodeMap<bool> cs(graph);
    121    
    122     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    123    
    124     for (UEdgeIt it(graph); it != INVALID; ++it) {
    125       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
    126     }
    127    
    128     for (ANodeIt it(graph); it != INVALID; ++it) {
    129       int num = 0;
    130       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    131         if (mm[jt]) ++num;
    132     }
    133       check(num <= 1, "INVALID PRIMAL");
    134     }
     165   
     166    Graph::UEdgeMap<bool> mm(graph);
     167    Graph::NodeMap<int> pm(graph);
     168
     169    bpmatch.matching(mm);
     170    bpmatch.potential(pm);
     171   
     172    for (UEdgeIt it(graph); it != INVALID; ++it) {
     173      if (mm[it]) {
     174        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
     175              "INVALID DUAL");
     176      } else {
     177        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
     178              "INVALID DUAL");
     179      }
     180    }
     181
     182    for (ANodeIt it(graph); it != INVALID; ++it) {
     183      int num = 0;
     184      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     185        if (mm[jt]) ++num;
     186    }
     187      check(num <= 1, "INVALID PRIMAL");
     188    }
     189    check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
     190  }
     191
     192  {
     193    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
     194
     195    bpmatch.run(true);
     196   
     197    Graph::UEdgeMap<bool> mm(graph);
     198    Graph::NodeMap<int> pm(graph);
     199
     200    bpmatch.matching(mm);
     201    bpmatch.potential(pm);
     202   
     203    for (UEdgeIt it(graph); it != INVALID; ++it) {
     204      if (mm[it]) {
     205        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
     206              "INVALID DUAL");
     207      } else {
     208        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
     209              "INVALID DUAL");
     210      }
     211    }
     212
     213    for (ANodeIt it(graph); it != INVALID; ++it) {
     214      int num = 0;
     215      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     216        if (mm[jt]) ++num;
     217    }
     218      check(num <= 1, "INVALID PRIMAL");
     219    }
     220    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
     221    max_cardinality_max_weight = bpmatch.matchingValue();
     222
     223  }
     224
     225  {
     226    Graph::UEdgeMap<int> cost(graph);
     227
     228    cost = subMap(constMap<UEdge>(c), weight);
     229
     230    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
     231
     232    bpmatch.run();
     233   
     234    Graph::UEdgeMap<bool> mm(graph);
     235    Graph::NodeMap<int> pm(graph);
     236
     237    bpmatch.matching(mm);
     238    bpmatch.potential(pm);
     239   
     240    for (UEdgeIt it(graph); it != INVALID; ++it) {
     241      if (mm[it]) {
     242        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
     243              "INVALID DUAL");
     244      } else {
     245        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
     246              "INVALID DUAL");
     247      }
     248    }
     249
     250    for (ANodeIt it(graph); it != INVALID; ++it) {
     251      int num = 0;
     252      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
     253        if (mm[jt]) ++num;
     254    }
     255      check(num <= 1, "INVALID PRIMAL");
     256    }
     257
     258    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
     259    check(max_cardinality * c - max_cardinality_max_weight
     260          == bpmatch.matchingCost(), "WRONG SIZE");
     261
    135262  }
    136263
Note: See TracChangeset for help on using the changeset viewer.