18 |
18 |
19 #include <iostream> |
19 #include <iostream> |
20 #include <sstream> |
20 #include <sstream> |
21 #include <vector> |
21 #include <vector> |
22 #include <queue> |
22 #include <queue> |
23 #include <lemon/math.h> |
|
24 #include <cstdlib> |
23 #include <cstdlib> |
25 |
24 |
26 #include <lemon/max_matching.h> |
25 #include <lemon/max_matching.h> |
27 #include <lemon/smart_graph.h> |
26 #include <lemon/smart_graph.h> |
|
27 #include <lemon/concepts/graph.h> |
|
28 #include <lemon/concepts/maps.h> |
28 #include <lemon/lgf_reader.h> |
29 #include <lemon/lgf_reader.h> |
|
30 #include <lemon/math.h> |
29 |
31 |
30 #include "test_tools.h" |
32 #include "test_tools.h" |
31 |
33 |
32 using namespace std; |
34 using namespace std; |
33 using namespace lemon; |
35 using namespace lemon; |
108 "7 2 4 981\n" |
110 "7 2 4 981\n" |
109 "7 6 5 250\n" |
111 "7 6 5 250\n" |
110 "5 2 6 539\n", |
112 "5 2 6 539\n", |
111 }; |
113 }; |
112 |
114 |
|
115 void checkMaxMatchingCompile() |
|
116 { |
|
117 typedef concepts::Graph Graph; |
|
118 typedef Graph::Node Node; |
|
119 typedef Graph::Edge Edge; |
|
120 typedef Graph::EdgeMap<bool> MatMap; |
|
121 |
|
122 Graph g; |
|
123 Node n; |
|
124 Edge e; |
|
125 MatMap mat(g); |
|
126 |
|
127 MaxMatching<Graph> mat_test(g); |
|
128 const MaxMatching<Graph>& |
|
129 const_mat_test = mat_test; |
|
130 |
|
131 mat_test.init(); |
|
132 mat_test.greedyInit(); |
|
133 mat_test.matchingInit(mat); |
|
134 mat_test.startSparse(); |
|
135 mat_test.startDense(); |
|
136 mat_test.run(); |
|
137 |
|
138 const_mat_test.matchingSize(); |
|
139 const_mat_test.matching(e); |
|
140 const_mat_test.matching(n); |
|
141 const_mat_test.mate(n); |
|
142 |
|
143 MaxMatching<Graph>::Status stat = |
|
144 const_mat_test.decomposition(n); |
|
145 const_mat_test.barrier(n); |
|
146 |
|
147 ignore_unused_variable_warning(stat); |
|
148 } |
|
149 |
|
150 void checkMaxWeightedMatchingCompile() |
|
151 { |
|
152 typedef concepts::Graph Graph; |
|
153 typedef Graph::Node Node; |
|
154 typedef Graph::Edge Edge; |
|
155 typedef Graph::EdgeMap<int> WeightMap; |
|
156 |
|
157 Graph g; |
|
158 Node n; |
|
159 Edge e; |
|
160 WeightMap w(g); |
|
161 |
|
162 MaxWeightedMatching<Graph> mat_test(g, w); |
|
163 const MaxWeightedMatching<Graph>& |
|
164 const_mat_test = mat_test; |
|
165 |
|
166 mat_test.init(); |
|
167 mat_test.start(); |
|
168 mat_test.run(); |
|
169 |
|
170 const_mat_test.matchingValue(); |
|
171 const_mat_test.matchingSize(); |
|
172 const_mat_test.matching(e); |
|
173 const_mat_test.matching(n); |
|
174 const_mat_test.mate(n); |
|
175 |
|
176 int k = 0; |
|
177 const_mat_test.dualValue(); |
|
178 const_mat_test.nodeValue(n); |
|
179 const_mat_test.blossomNum(); |
|
180 const_mat_test.blossomSize(k); |
|
181 const_mat_test.blossomValue(k); |
|
182 } |
|
183 |
|
184 void checkMaxWeightedPerfectMatchingCompile() |
|
185 { |
|
186 typedef concepts::Graph Graph; |
|
187 typedef Graph::Node Node; |
|
188 typedef Graph::Edge Edge; |
|
189 typedef Graph::EdgeMap<int> WeightMap; |
|
190 |
|
191 Graph g; |
|
192 Node n; |
|
193 Edge e; |
|
194 WeightMap w(g); |
|
195 |
|
196 MaxWeightedPerfectMatching<Graph> mat_test(g, w); |
|
197 const MaxWeightedPerfectMatching<Graph>& |
|
198 const_mat_test = mat_test; |
|
199 |
|
200 mat_test.init(); |
|
201 mat_test.start(); |
|
202 mat_test.run(); |
|
203 |
|
204 const_mat_test.matchingValue(); |
|
205 const_mat_test.matching(e); |
|
206 const_mat_test.matching(n); |
|
207 const_mat_test.mate(n); |
|
208 |
|
209 int k = 0; |
|
210 const_mat_test.dualValue(); |
|
211 const_mat_test.nodeValue(n); |
|
212 const_mat_test.blossomNum(); |
|
213 const_mat_test.blossomSize(k); |
|
214 const_mat_test.blossomValue(k); |
|
215 } |
|
216 |
113 void checkMatching(const SmartGraph& graph, |
217 void checkMatching(const SmartGraph& graph, |
114 const MaxMatching<SmartGraph>& mm) { |
218 const MaxMatching<SmartGraph>& mm) { |
115 int num = 0; |
219 int num = 0; |
116 |
220 |
117 IntNodeMap comp_index(graph); |
221 IntNodeMap comp_index(graph); |