|
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 |
|
14 using namespace std; |
|
15 using namespace lemon; |
|
16 |
|
17 typedef ListBpUGraph Graph; |
|
18 BPUGRAPH_TYPEDEFS(Graph); |
|
19 |
|
20 int 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 } |