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

    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>

    28 #include <lemon/graph_utils.h>

    30 #include <lemon/maps.h>

    32 #include "test_tools.h"

    34 using namespace std;

    35 using namespace lemon;

    37 typedef SmartBpUGraph Graph;

    38 BPUGRAPH_TYPEDEFS(Graph);

    40 const int N = 10;

    41 const int M = 10;

    42 const int E = 52;

    43 const int C = 100;

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

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

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

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

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

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

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

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

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

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

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

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

    61 int main() {

    62   Graph graph;

    63   vector<Node> aNodes;

    64   vector<Node> bNodes;

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

    68   int max_cardinality;

    69   int max_weight;

    70   int max_cardinality_max_weight;

    71   int min_cost_matching;

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

    74     Node node = graph.addANode();

    75     aNodes.push_back(node);

    76   }

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

    78     Node node = graph.addBNode();

    79     bNodes.push_back(node);

    80   }

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

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

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

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

    85     weight[uedge] = wa[i];

    86   }

    89   {

    90     MaxBipartiteMatching<Graph> bpmatch(graph);

    92     bpmatch.run();

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

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

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

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

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

   101     }

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

   104       int num = 0;

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

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

   107       }

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

   109     }

   110     max_cardinality = bpmatch.matchingSize();

   111   }

   113   {

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

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

   117           "WRONG MATCHING");

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

   120       int num = 0;

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

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

   123       }

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

   125     }

   126   }

   128   {

   129     MaxBipartiteMatching<Graph> bpmatch(graph);

   131     bpmatch.greedyInit();

   132     bpmatch.start();

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

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

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

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

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

   141     }

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

   144       int num = 0;

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

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

   147     }

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

   149     }

   150   }

   152   {

   153     MaxBipartiteMatching<Graph> bpmatch(graph);

   155     bpmatch.greedyInit();

   156     while (bpmatch.simpleAugment());

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

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

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

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

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

   165     }

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

   168       int num = 0;

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

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

   171     }

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

   173     }

   174   }

   176   {

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

   179     bpmatch.init();

   181     max_weight = 0;

   182     while (bpmatch.augment(true)) {

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

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

   187       bpmatch.matching(mm);

   188       bpmatch.potential(pm);

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

   191         if (mm[it]) {

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

   193                 "INVALID DUAL");

   194         } else {

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

   196                 "INVALID DUAL");

   197         }

   198       }

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

   201         int num = 0;

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

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

   204         }

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

   206       }

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

   208         max_weight = bpmatch.matchingValue();

   209       }

   210     }

   211   }

   213   {

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

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

   217           "WRONG MATCHING");

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

   220       int num = 0;

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

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

   223       }

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

   225     }

   226   }

   228   {

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

   231     bpmatch.run();

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

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

   236     bpmatch.matching(mm);

   237     bpmatch.potential(pm);

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

   240       if (mm[it]) {

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

   242               "INVALID DUAL");

   243       } else {

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

   245               "INVALID DUAL");

   246       }

   247     }

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

   250       int num = 0;

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

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

   253     }

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

   255     }

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

   257   }

   259   {

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

   262     bpmatch.run(true);

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

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

   267     bpmatch.matching(mm);

   268     bpmatch.potential(pm);

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

   271       if (mm[it]) {

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

   273               "INVALID DUAL");

   274       } else {

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

   276               "INVALID DUAL");

   277       }

   278     }

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

   281       int num = 0;

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

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

   284     }

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

   286     }

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

   288     max_cardinality_max_weight = bpmatch.matchingValue();

   290   }

   292   {

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

   295     check(max_cardinality_max_weight ==

   296           maxWeightedMaxBipartiteMatching(graph, weight, mm),

   297           "WRONG MATCHING");

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

   300       int num = 0;

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

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

   303       }

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

   305     }

   306   }

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

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

   310   {

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

   314     bpmatch.run();

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

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

   319     bpmatch.matching(mm);

   320     bpmatch.potential(pm);

   322     min_cost_matching = bpmatch.matchingCost();

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

   324     check(max_cardinality * C - max_cardinality_max_weight

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

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

   328       if (mm[it]) {

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

   330               "INVALID DUAL");

   331       } else {

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

   333               "INVALID DUAL");

   334       }

   335     }

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

   338       int num = 0;

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

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

   341     }

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

   343     }

   345     min_cost_matching = bpmatch.matchingCost();

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

   347     check(max_cardinality * C - max_cardinality_max_weight

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

   350   }

   352   {

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

   355     check(min_cost_matching ==

   356           minCostMaxBipartiteMatching(graph, cost, mm),

   357           "WRONG MATCHING");

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

   360       int num = 0;

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

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

   363       }

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

   365     }

   366   }

   368   return 0;

   369 }

author	deba
	Fri, 11 May 2007 16:02:53 +0000
changeset 2443	14abfa02bf42
parent 2386	81b47fc5c444
child 2462	7a096a6bf53a
permissions	-rw-r--r--