Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/bipartite_matching_test.cc
author deba
Sat, 11 Aug 2007 16:34:41 +0000
changeset 2462 7a096a6bf53a
parent 2391 14a343be7a5a
child 2463 19651a04d056
permissions -rw-r--r--
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 
     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2007

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    18 

    19 #include <cstdlib>

    20 #include <iostream>

    21 #include <sstream>

    22 

    23 #include <lemon/smart_graph.h>

    24 

    25 #include <lemon/bpugraph_adaptor.h>

    26 #include <lemon/bipartite_matching.h>

    27 #include <lemon/pr_bipartite_matching.h>

    28 

    29 #include <lemon/graph_utils.h>

    30 

    31 #include <lemon/maps.h>

    32 

    33 #include "test_tools.h"

    34 

    35 using namespace std;

    36 using namespace lemon;

    37 

    38 typedef SmartBpUGraph Graph;

    39 BPUGRAPH_TYPEDEFS(Graph);

    40 

    41 const int N = 10;

    42 const int M = 10;

    43 const int E = 52;

    44 const int C = 100;

    45 

    46 const int sa[E] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5,

    47                     2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8,

    48                     4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8,

    49                     8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4};

    50 

    51 const int ta[E] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6,

    52                     3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0,

    53                     6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1,

    54                     4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6};

    55 

    56 const int wa[E] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95,

    57                     13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43,

    58                     54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91,

    59                     60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47};

    60 

    61 

    62 int main() {

    63   Graph graph;

    64   vector<Node> aNodes;

    65   vector<Node> bNodes;

    66 

    67   Graph::UEdgeMap<int> weight(graph);

    68 

    69   int max_cardinality;

    70   int max_weight;

    71   int max_cardinality_max_weight;

    72   int min_cost_matching;

    73 

    74   for (int i = 0; i < N; ++i) {

    75     Node node = graph.addANode();

    76     aNodes.push_back(node);

    77   }

    78   for (int i = 0; i < M; ++i) {

    79     Node node = graph.addBNode();

    80     bNodes.push_back(node);

    81   }

    82   for (int i = 0; i < E; ++i) {

    83     Node aNode = aNodes[sa[i]];

    84     Node bNode = bNodes[ta[i]];

    85     UEdge uedge = graph.addEdge(aNode, bNode);

    86     weight[uedge] = wa[i];

    87   }

    88 

    89 

    90   {

    91     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);

   116 

   117     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     }

   135     max_cardinality = bpmatch.matchingSize();

   136   }

   137 

   138   {

   139     Graph::UEdgeMap<bool> mm(graph);

   140 

   141     check(max_cardinality == maxBipartiteMatching(graph, mm),

   142           "WRONG MATCHING");

   143     

   144     for (ANodeIt it(graph); it != INVALID; ++it) {

   145       int num = 0;

   146       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   147         if (mm[jt]) ++num;

   148       }

   149       check(num <= 1, "INVALID PRIMAL");

   150     }

   151   }

   152 

   153   {

   154     MaxBipartiteMatching<Graph> bpmatch(graph);

   155 

   156     bpmatch.greedyInit();

   157     bpmatch.start();

   158 

   159     Graph::UEdgeMap<bool> mm(graph);

   160     Graph::NodeMap<bool> cs(graph);

   161 

   162     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");

   163     

   164     for (UEdgeIt it(graph); it != INVALID; ++it) {

   165       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");

   166     }

   167     

   168     for (ANodeIt it(graph); it != INVALID; ++it) {

   169       int num = 0;

   170       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   171         if (mm[jt]) ++num;

   172     }

   173       check(num <= 1, "INVALID PRIMAL");

   174     }

   175   }

   176 

   177   {

   178     MaxBipartiteMatching<Graph> bpmatch(graph);

   179 

   180     bpmatch.greedyInit();

   181     while (bpmatch.simpleAugment());

   182     

   183     Graph::UEdgeMap<bool> mm(graph);

   184     Graph::NodeMap<bool> cs(graph);

   185     

   186     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");

   187     

   188     for (UEdgeIt it(graph); it != INVALID; ++it) {

   189       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");

   190     }

   191     

   192     for (ANodeIt it(graph); it != INVALID; ++it) {

   193       int num = 0;

   194       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   195         if (mm[jt]) ++num;

   196     }

   197       check(num <= 1, "INVALID PRIMAL");

   198     }

   199   }

   200 

   201   {

   202     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

   203 

   204     bpmatch.init();

   205 

   206     max_weight = 0;

   207     while (bpmatch.augment(true)) {

   208     

   209       Graph::UEdgeMap<bool> mm(graph);

   210       Graph::NodeMap<int> pm(graph);

   211       

   212       bpmatch.matching(mm);

   213       bpmatch.potential(pm);

   214       

   215       for (UEdgeIt it(graph); it != INVALID; ++it) {

   216         if (mm[it]) {

   217           check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,

   218                 "INVALID DUAL");

   219         } else {

   220           check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,

   221                 "INVALID DUAL");

   222         }

   223       }

   224 

   225       for (ANodeIt it(graph); it != INVALID; ++it) {

   226         int num = 0;

   227         for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   228           if (mm[jt]) ++num;

   229         }

   230         check(num <= 1, "INVALID PRIMAL");

   231       }

   232       if (bpmatch.matchingValue() > max_weight) {

   233         max_weight = bpmatch.matchingValue();

   234       }

   235     }

   236   }

   237 

   238   {

   239     Graph::UEdgeMap<bool> mm(graph);

   240 

   241     check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),

   242           "WRONG MATCHING");

   243     

   244     for (ANodeIt it(graph); it != INVALID; ++it) {

   245       int num = 0;

   246       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   247         if (mm[jt]) ++num;

   248       }

   249       check(num <= 1, "INVALID PRIMAL");

   250     }

   251   }

   252 

   253   {

   254     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

   255 

   256     bpmatch.run();

   257     

   258     Graph::UEdgeMap<bool> mm(graph);

   259     Graph::NodeMap<int> pm(graph);

   260 

   261     bpmatch.matching(mm);

   262     bpmatch.potential(pm);

   263     

   264     for (UEdgeIt it(graph); it != INVALID; ++it) {

   265       if (mm[it]) {

   266         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,

   267               "INVALID DUAL");

   268       } else {

   269         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,

   270               "INVALID DUAL");

   271       }

   272     }

   273 

   274     for (ANodeIt it(graph); it != INVALID; ++it) {

   275       int num = 0;

   276       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   277         if (mm[jt]) ++num;

   278     }

   279       check(num <= 1, "INVALID PRIMAL");

   280     }

   281     check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");

   282   }

   283 

   284   {

   285     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

   286 

   287     bpmatch.run(true);

   288     

   289     Graph::UEdgeMap<bool> mm(graph);

   290     Graph::NodeMap<int> pm(graph);

   291 

   292     bpmatch.matching(mm);

   293     bpmatch.potential(pm);

   294     

   295     for (UEdgeIt it(graph); it != INVALID; ++it) {

   296       if (mm[it]) {

   297         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,

   298               "INVALID DUAL");

   299       } else {

   300         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,

   301               "INVALID DUAL");

   302       }

   303     }

   304 

   305     for (ANodeIt it(graph); it != INVALID; ++it) {

   306       int num = 0;

   307       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   308         if (mm[jt]) ++num;

   309     }

   310       check(num <= 1, "INVALID PRIMAL");

   311     }

   312     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");

   313     max_cardinality_max_weight = bpmatch.matchingValue();

   314 

   315   }

   316 

   317   {

   318     Graph::UEdgeMap<bool> mm(graph);

   319 

   320     check(max_cardinality_max_weight == 

   321           maxWeightedMaxBipartiteMatching(graph, weight, mm),

   322           "WRONG MATCHING");

   323     

   324     for (ANodeIt it(graph); it != INVALID; ++it) {

   325       int num = 0;

   326       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   327         if (mm[jt]) ++num;

   328       }

   329       check(num <= 1, "INVALID PRIMAL");

   330     }

   331   }

   332 

   333   Graph::UEdgeMap<int> cost(graph);

   334   cost = subMap(constMap<UEdge>(C), weight);

   335   {

   336 

   337     MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);

   338 

   339     bpmatch.run();

   340     

   341     Graph::UEdgeMap<bool> mm(graph);

   342     Graph::NodeMap<int> pm(graph);

   343 

   344     bpmatch.matching(mm);

   345     bpmatch.potential(pm);

   346     

   347     min_cost_matching = bpmatch.matchingCost();

   348     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");

   349     check(max_cardinality * C - max_cardinality_max_weight 

   350           == bpmatch.matchingCost(), "WRONG SIZE");

   351 

   352     for (UEdgeIt it(graph); it != INVALID; ++it) {

   353       if (mm[it]) {

   354         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,

   355               "INVALID DUAL");

   356       } else {

   357         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,

   358               "INVALID DUAL");

   359       }

   360     }

   361 

   362     for (ANodeIt it(graph); it != INVALID; ++it) {

   363       int num = 0;

   364       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   365         if (mm[jt]) ++num;

   366     }

   367       check(num <= 1, "INVALID PRIMAL");

   368     }

   369 

   370     min_cost_matching = bpmatch.matchingCost();

   371     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");

   372     check(max_cardinality * C - max_cardinality_max_weight 

   373           == bpmatch.matchingCost(), "WRONG SIZE");

   374 

   375   }

   376 

   377   {

   378     Graph::UEdgeMap<bool> mm(graph);

   379 

   380     check(min_cost_matching == 

   381           minCostMaxBipartiteMatching(graph, cost, mm),

   382           "WRONG MATCHING");

   383     

   384     for (ANodeIt it(graph); it != INVALID; ++it) {

   385       int num = 0;

   386       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   387         if (mm[jt]) ++num;

   388       }

   389       check(num <= 1, "INVALID PRIMAL");

   390     }

   391   }

   392 

   393   return 0;

   394 }
lemon-0.x