5 #include <lemon/list_graph.h>
7 #include <lemon/bpugraph_adaptor.h>
8 #include <lemon/bipartite_matching.h>
10 #include <lemon/graph_utils.h>
12 #include "test_tools.h"
15 using namespace lemon;
17 typedef ListBpUGraph Graph;
18 BPUGRAPH_TYPEDEFS(Graph);
20 int main(int argc, const char *argv[]) {
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));
28 for (int i = 0; i < n; ++i) {
29 Node node = graph.addANode();
30 aNodes.push_back(node);
32 for (int i = 0; i < m; ++i) {
33 Node node = graph.addBNode();
34 bNodes.push_back(node);
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);
43 MaxBipartiteMatching<Graph> bpmatch(graph);
47 Graph::UEdgeMap<bool> mm(graph);
48 Graph::NodeMap<bool> cs(graph);
50 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
52 for (UEdgeIt it(graph); it != INVALID; ++it) {
53 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
56 for (ANodeIt it(graph); it != INVALID; ++it) {
58 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
61 check(num <= 1, "INVALID PRIMAL");
66 MaxBipartiteMatching<Graph> bpmatch(graph);
71 Graph::UEdgeMap<bool> mm(graph);
72 Graph::NodeMap<bool> cs(graph);
74 check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
76 for (UEdgeIt it(graph); it != INVALID; ++it) {
77 check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
80 for (ANodeIt it(graph); it != INVALID; ++it) {
82 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
85 check(num <= 1, "INVALID PRIMAL");
90 MaxBipartiteMatching<Graph> bpmatch(graph);
93 while (bpmatch.simpleAugment());
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");
104 for (ANodeIt it(graph); it != INVALID; ++it) {
106 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
109 check(num <= 1, "INVALID PRIMAL");
114 SwapBpUGraphAdaptor<Graph> swapgraph(graph);
115 MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
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");
128 for (ANodeIt it(graph); it != INVALID; ++it) {
130 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
133 check(num <= 1, "INVALID PRIMAL");