lemon-0.x: test/bipartite_matching

     1 /* -*- C++ -*-

     2  *

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

     4  *

     5  * Copyright (C) 2003-2008

     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  */

    19 #include <cstdlib>

    20 #include <iostream>

    21 #include <sstream>

    23 #include <lemon/smart_graph.h>

    25 #include <lemon/bpugraph_adaptor.h>

    26 #include <lemon/bipartite_matching.h>

    27 #include <lemon/pr_bipartite_matching.h>

    29 #include <lemon/graph_utils.h>

    31 #include <lemon/maps.h>

    33 #include "test_tools.h"

    35 using namespace std;

    36 using namespace lemon;

    38 typedef SmartBpUGraph Graph;

    39 BPUGRAPH_TYPEDEFS(Graph);

    41 const int NN = 10;

    42 const int MM = 10;

    43 const int EE = 52;

    44 const int CC = 100;

    46 const int sa[EE] = { 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};

    51 const int ta[EE] = { 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};

    56 const int wa[EE] = { 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};

    62 int main() {

    63   Graph graph;

    64   vector<Node> aNodes;

    65   vector<Node> bNodes;

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

    69   int max_cardinality;

    70   int max_weight;

    71   int max_cardinality_max_weight;

    72   int min_cost_matching;

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

    75     Node node = graph.addANode();

    76     aNodes.push_back(node);

    77   }

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

    79     Node node = graph.addBNode();

    80     bNodes.push_back(node);

    81   }

    82   for (int i = 0; i < EE; ++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   }

    90   {

    91     MaxBipartiteMatching<Graph> bpmatch(graph);

    93     bpmatch.run();

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

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

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

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

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

   102     }

   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   }

   114   {

   115     PrBipartiteMatching<Graph> bpmatch(graph);

   117     bpmatch.run();

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

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

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

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

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

   126     }

   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   }

   138   {

   139     Graph::ANodeMap<UEdge> mm(graph);

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

   142           "WRONG MATCHING");

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

   145       int num = 0;

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

   148         if (mm[graph.aNode(jt)] == jt) ++num;

   149       }

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

   151     }

   152   }

   154   {

   155     Graph::ANodeMap<UEdge> mm(graph);

   157     check(max_cardinality == prBipartiteMatching(graph, mm),

   158           "WRONG MATCHING");

   160     for (BNodeIt it(graph); it != INVALID; ++it) {

   161       int num = 0;

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

   164         if (mm[graph.aNode(jt)] == jt) ++num;

   165       }

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

   167     }

   168   }

   170   {

   171     MaxBipartiteMatching<Graph> bpmatch(graph);

   173     bpmatch.greedyInit();

   174     bpmatch.start();

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

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

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

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

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

   183     }

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

   186       int num = 0;

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

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

   189     }

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

   191     }

   192   }

   194   {

   195     MaxBipartiteMatching<Graph> bpmatch(graph);

   197     bpmatch.greedyInit();

   198     while (bpmatch.simpleAugment());

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

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

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

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

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

   207     }

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

   210       int num = 0;

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

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

   213     }

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

   215     }

   216   }

   218   {

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

   221     bpmatch.init();

   223     max_weight = 0;

   224     while (bpmatch.augment(true)) {

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

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

   229       bpmatch.matching(mm);

   230       bpmatch.potential(pm);

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

   233         if (mm[it]) {

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

   235                 "INVALID DUAL");

   236         } else {

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

   238                 "INVALID DUAL");

   239         }

   240       }

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

   243         int num = 0;

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

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

   246         }

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

   248       }

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

   250         max_weight = bpmatch.matchingValue();

   251       }

   252     }

   253   }

   255   {

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

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

   259           "WRONG MATCHING");

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

   262       int num = 0;

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

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

   265       }

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

   267     }

   268   }

   270   {

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

   273     bpmatch.run();

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

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

   278     bpmatch.matching(mm);

   279     bpmatch.potential(pm);

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

   282       if (mm[it]) {

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

   284               "INVALID DUAL");

   285       } else {

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

   287               "INVALID DUAL");

   288       }

   289     }

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

   292       int num = 0;

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

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

   295     }

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

   297     }

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

   299   }

   301   {

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

   304     bpmatch.run(true);

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

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

   309     bpmatch.matching(mm);

   310     bpmatch.potential(pm);

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

   313       if (mm[it]) {

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

   315               "INVALID DUAL");

   316       } else {

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

   318               "INVALID DUAL");

   319       }

   320     }

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

   323       int num = 0;

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

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

   326     }

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

   328     }

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

   330     max_cardinality_max_weight = bpmatch.matchingValue();

   332   }

   334   {

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

   337     check(max_cardinality_max_weight ==

   338           maxWeightedMaxBipartiteMatching(graph, weight, mm),

   339           "WRONG MATCHING");

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

   342       int num = 0;

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

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

   345       }

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

   347     }

   348   }

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

   351   cost = subMap(constMap<UEdge>(CC), weight);

   352   {

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

   356     bpmatch.run();

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

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

   361     bpmatch.matching(mm);

   362     bpmatch.potential(pm);

   364     min_cost_matching = bpmatch.matchingCost();

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

   366     check(max_cardinality * CC - max_cardinality_max_weight

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

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

   370       if (mm[it]) {

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

   372               "INVALID DUAL");

   373       } else {

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

   375               "INVALID DUAL");

   376       }

   377     }

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

   380       int num = 0;

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

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

   383     }

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

   385     }

   387     min_cost_matching = bpmatch.matchingCost();

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

   389     check(max_cardinality * CC - max_cardinality_max_weight

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

   392   }

   394   {

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

   397     check(min_cost_matching ==

   398           minCostMaxBipartiteMatching(graph, cost, mm),

   399           "WRONG MATCHING");

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

   402       int num = 0;

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

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

   405       }

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

   407     }

   408   }

   410   return 0;

   411 }

author	deba
	Fri, 23 May 2008 10:55:41 +0000
changeset 2610	52cf8f8f25b4
parent 2553	bfced05fa852
child 2618	6aa6fcaeaea5
permissions	-rw-r--r--