COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/bipartite_matching_test.cc @ 2040:c7bd55c0d820

Last change on this file since 2040:c7bd55c0d820 was 2040:c7bd55c0d820, checked in by Balazs Dezso, 13 years ago

Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
Test for it

Some BpUgraph? improvments

File size: 3.3 KB
Line 
1#include <cstdlib>
2#include <iostream>
3#include <sstream>
4
5#include <lemon/list_graph.h>
6
7#include <lemon/bpugraph_adaptor.h>
8#include <lemon/bipartite_matching.h>
9
10#include <lemon/graph_utils.h>
11
12#include "test_tools.h"
13
14using namespace std;
15using namespace lemon;
16
17typedef ListBpUGraph Graph;
18BPUGRAPH_TYPEDEFS(Graph);
19
20int main(int argc, const char *argv[]) {
21  Graph graph;
22  vector<Node> aNodes;
23  vector<Node> bNodes;
24  int n = argc > 1 ? atoi(argv[1]) : 100;
25  int m = argc > 2 ? atoi(argv[2]) : 100;
26  int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
27
28  for (int i = 0; i < n; ++i) {
29    Node node = graph.addANode();
30    aNodes.push_back(node);
31  }
32  for (int i = 0; i < m; ++i) {
33    Node node = graph.addBNode();
34    bNodes.push_back(node);
35  }
36  for (int i = 0; i < e; ++i) {
37    Node aNode = aNodes[urandom(n)];
38    Node bNode = bNodes[urandom(m)];
39    graph.addEdge(aNode, bNode);
40  }
41
42  {
43    MaxBipartiteMatching<Graph> bpmatch(graph);
44
45    bpmatch.run();
46
47    Graph::UEdgeMap<bool> mm(graph);
48    Graph::NodeMap<bool> cs(graph);
49   
50    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
51   
52    for (UEdgeIt it(graph); it != INVALID; ++it) {
53      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
54    }
55   
56    for (ANodeIt it(graph); it != INVALID; ++it) {
57      int num = 0;
58      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
59        if (mm[jt]) ++num;
60    }
61      check(num <= 1, "INVALID PRIMAL");
62    }
63  }
64
65  {
66    MaxBipartiteMatching<Graph> bpmatch(graph);
67
68    bpmatch.greedyInit();
69    bpmatch.start();
70
71    Graph::UEdgeMap<bool> mm(graph);
72    Graph::NodeMap<bool> cs(graph);
73
74    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
75   
76    for (UEdgeIt it(graph); it != INVALID; ++it) {
77      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
78    }
79   
80    for (ANodeIt it(graph); it != INVALID; ++it) {
81      int num = 0;
82      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
83        if (mm[jt]) ++num;
84    }
85      check(num <= 1, "INVALID PRIMAL");
86    }
87  }
88
89  {
90    MaxBipartiteMatching<Graph> bpmatch(graph);
91
92    bpmatch.greedyInit();
93    while (bpmatch.simpleAugment());
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  }
112
113  {
114    SwapBpUGraphAdaptor<Graph> swapgraph(graph);
115    MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
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  }
136
137  return 0;
138}
Note: See TracBrowser for help on using the repository browser.