test/bipartite_matching_test.cc
author klao
Thu, 13 Apr 2006 17:57:03 +0000
changeset 2046 66d160810c0a
child 2051 08652c1763f6
permissions -rw-r--r--
more explicit :)
deba@2040
     1
#include <cstdlib>
deba@2040
     2
#include <iostream>
deba@2040
     3
#include <sstream>
deba@2040
     4
deba@2040
     5
#include <lemon/list_graph.h>
deba@2040
     6
deba@2040
     7
#include <lemon/bpugraph_adaptor.h>
deba@2040
     8
#include <lemon/bipartite_matching.h>
deba@2040
     9
deba@2040
    10
#include <lemon/graph_utils.h>
deba@2040
    11
deba@2040
    12
#include "test_tools.h"
deba@2040
    13
deba@2040
    14
using namespace std;
deba@2040
    15
using namespace lemon;
deba@2040
    16
deba@2040
    17
typedef ListBpUGraph Graph;
deba@2040
    18
BPUGRAPH_TYPEDEFS(Graph);
deba@2040
    19
deba@2040
    20
int main(int argc, const char *argv[]) {
deba@2040
    21
  Graph graph;
deba@2040
    22
  vector<Node> aNodes;
deba@2040
    23
  vector<Node> bNodes;
deba@2040
    24
  int n = argc > 1 ? atoi(argv[1]) : 100;
deba@2040
    25
  int m = argc > 2 ? atoi(argv[2]) : 100;
deba@2040
    26
  int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
deba@2040
    27
deba@2040
    28
  for (int i = 0; i < n; ++i) {
deba@2040
    29
    Node node = graph.addANode();
deba@2040
    30
    aNodes.push_back(node);
deba@2040
    31
  }
deba@2040
    32
  for (int i = 0; i < m; ++i) {
deba@2040
    33
    Node node = graph.addBNode();
deba@2040
    34
    bNodes.push_back(node);
deba@2040
    35
  }
deba@2040
    36
  for (int i = 0; i < e; ++i) {
deba@2040
    37
    Node aNode = aNodes[urandom(n)];
deba@2040
    38
    Node bNode = bNodes[urandom(m)];
deba@2040
    39
    graph.addEdge(aNode, bNode);
deba@2040
    40
  }
deba@2040
    41
deba@2040
    42
  {
deba@2040
    43
    MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040
    44
deba@2040
    45
    bpmatch.run();
deba@2040
    46
deba@2040
    47
    Graph::UEdgeMap<bool> mm(graph);
deba@2040
    48
    Graph::NodeMap<bool> cs(graph);
deba@2040
    49
    
deba@2040
    50
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040
    51
    
deba@2040
    52
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040
    53
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040
    54
    }
deba@2040
    55
    
deba@2040
    56
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
    57
      int num = 0;
deba@2040
    58
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
    59
        if (mm[jt]) ++num;
deba@2040
    60
    }
deba@2040
    61
      check(num <= 1, "INVALID PRIMAL");
deba@2040
    62
    }
deba@2040
    63
  }
deba@2040
    64
deba@2040
    65
  {
deba@2040
    66
    MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040
    67
deba@2040
    68
    bpmatch.greedyInit();
deba@2040
    69
    bpmatch.start();
deba@2040
    70
deba@2040
    71
    Graph::UEdgeMap<bool> mm(graph);
deba@2040
    72
    Graph::NodeMap<bool> cs(graph);
deba@2040
    73
deba@2040
    74
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040
    75
    
deba@2040
    76
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040
    77
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040
    78
    }
deba@2040
    79
    
deba@2040
    80
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
    81
      int num = 0;
deba@2040
    82
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
    83
        if (mm[jt]) ++num;
deba@2040
    84
    }
deba@2040
    85
      check(num <= 1, "INVALID PRIMAL");
deba@2040
    86
    }
deba@2040
    87
  }
deba@2040
    88
deba@2040
    89
  {
deba@2040
    90
    MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040
    91
deba@2040
    92
    bpmatch.greedyInit();
deba@2040
    93
    while (bpmatch.simpleAugment());
deba@2040
    94
    
deba@2040
    95
    Graph::UEdgeMap<bool> mm(graph);
deba@2040
    96
    Graph::NodeMap<bool> cs(graph);
deba@2040
    97
    
deba@2040
    98
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040
    99
    
deba@2040
   100
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040
   101
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040
   102
    }
deba@2040
   103
    
deba@2040
   104
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
   105
      int num = 0;
deba@2040
   106
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
   107
        if (mm[jt]) ++num;
deba@2040
   108
    }
deba@2040
   109
      check(num <= 1, "INVALID PRIMAL");
deba@2040
   110
    }
deba@2040
   111
  }
deba@2040
   112
deba@2040
   113
  {
deba@2040
   114
    SwapBpUGraphAdaptor<Graph> swapgraph(graph);
deba@2040
   115
    MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
deba@2040
   116
deba@2040
   117
    bpmatch.run();
deba@2040
   118
deba@2040
   119
    Graph::UEdgeMap<bool> mm(graph);
deba@2040
   120
    Graph::NodeMap<bool> cs(graph);
deba@2040
   121
    
deba@2040
   122
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040
   123
    
deba@2040
   124
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040
   125
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040
   126
    }
deba@2040
   127
    
deba@2040
   128
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
   129
      int num = 0;
deba@2040
   130
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
   131
        if (mm[jt]) ++num;
deba@2040
   132
    }
deba@2040
   133
      check(num <= 1, "INVALID PRIMAL");
deba@2040
   134
    }
deba@2040
   135
  }
deba@2040
   136
deba@2040
   137
  return 0;
deba@2040
   138
}