equal
deleted
inserted
replaced
22 |
22 |
23 #include <lemon/smart_graph.h> |
23 #include <lemon/smart_graph.h> |
24 |
24 |
25 #include <lemon/bpugraph_adaptor.h> |
25 #include <lemon/bpugraph_adaptor.h> |
26 #include <lemon/bipartite_matching.h> |
26 #include <lemon/bipartite_matching.h> |
|
27 #include <lemon/pr_bipartite_matching.h> |
27 |
28 |
28 #include <lemon/graph_utils.h> |
29 #include <lemon/graph_utils.h> |
29 |
30 |
30 #include <lemon/maps.h> |
31 #include <lemon/maps.h> |
31 |
32 |
86 } |
87 } |
87 |
88 |
88 |
89 |
89 { |
90 { |
90 MaxBipartiteMatching<Graph> bpmatch(graph); |
91 MaxBipartiteMatching<Graph> bpmatch(graph); |
|
92 |
|
93 bpmatch.run(); |
|
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 max_cardinality = bpmatch.matchingSize(); |
|
112 } |
|
113 |
|
114 { |
|
115 PrBipartiteMatching<Graph> bpmatch(graph); |
91 |
116 |
92 bpmatch.run(); |
117 bpmatch.run(); |
93 |
118 |
94 Graph::UEdgeMap<bool> mm(graph); |
119 Graph::UEdgeMap<bool> mm(graph); |
95 Graph::NodeMap<bool> cs(graph); |
120 Graph::NodeMap<bool> cs(graph); |