deba@430
|
1 |
/* -*- C++ -*-
|
deba@430
|
2 |
*
|
deba@430
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
deba@430
|
4 |
*
|
deba@430
|
5 |
* Copyright (C) 2003-2008
|
deba@430
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@430
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@430
|
8 |
*
|
deba@430
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@430
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@430
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@430
|
12 |
*
|
deba@430
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@430
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@430
|
15 |
* purpose.
|
deba@430
|
16 |
*
|
deba@430
|
17 |
*/
|
deba@430
|
18 |
|
deba@430
|
19 |
#include<iostream>
|
deba@430
|
20 |
#include<lemon/concept_check.h>
|
deba@430
|
21 |
|
deba@430
|
22 |
#include<lemon/list_graph.h>
|
deba@430
|
23 |
#include<lemon/smart_graph.h>
|
deba@430
|
24 |
|
deba@430
|
25 |
#include<lemon/concepts/digraph.h>
|
deba@430
|
26 |
#include<lemon/concepts/graph.h>
|
deba@430
|
27 |
|
deba@430
|
28 |
#include<lemon/digraph_adaptor.h>
|
deba@430
|
29 |
#include<lemon/graph_adaptor.h>
|
deba@430
|
30 |
|
deba@430
|
31 |
#include <limits>
|
deba@430
|
32 |
#include <lemon/bfs.h>
|
deba@430
|
33 |
#include <lemon/path.h>
|
deba@430
|
34 |
|
deba@430
|
35 |
#include"test/test_tools.h"
|
deba@430
|
36 |
#include"test/graph_test.h"
|
deba@430
|
37 |
|
deba@430
|
38 |
using namespace lemon;
|
deba@430
|
39 |
|
deba@430
|
40 |
void checkDigraphAdaptor() {
|
deba@430
|
41 |
checkConcept<concepts::Digraph, DigraphAdaptor<concepts::Digraph> >();
|
deba@430
|
42 |
|
deba@430
|
43 |
typedef ListDigraph Digraph;
|
deba@430
|
44 |
typedef DigraphAdaptor<Digraph> Adaptor;
|
deba@430
|
45 |
|
deba@430
|
46 |
Digraph digraph;
|
deba@430
|
47 |
Adaptor adaptor(digraph);
|
deba@430
|
48 |
|
deba@430
|
49 |
Digraph::Node n1 = digraph.addNode();
|
deba@430
|
50 |
Digraph::Node n2 = digraph.addNode();
|
deba@430
|
51 |
Digraph::Node n3 = digraph.addNode();
|
deba@430
|
52 |
|
deba@430
|
53 |
Digraph::Arc a1 = digraph.addArc(n1, n2);
|
deba@430
|
54 |
Digraph::Arc a2 = digraph.addArc(n1, n3);
|
deba@430
|
55 |
Digraph::Arc a3 = digraph.addArc(n2, n3);
|
deba@430
|
56 |
|
deba@430
|
57 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
58 |
checkGraphArcList(adaptor, 3);
|
deba@430
|
59 |
checkGraphConArcList(adaptor, 3);
|
deba@430
|
60 |
|
deba@430
|
61 |
checkGraphOutArcList(adaptor, n1, 2);
|
deba@430
|
62 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
63 |
checkGraphOutArcList(adaptor, n3, 0);
|
deba@430
|
64 |
|
deba@430
|
65 |
checkGraphInArcList(adaptor, n1, 0);
|
deba@430
|
66 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
67 |
checkGraphInArcList(adaptor, n3, 2);
|
deba@430
|
68 |
|
deba@430
|
69 |
checkNodeIds(adaptor);
|
deba@430
|
70 |
checkArcIds(adaptor);
|
deba@430
|
71 |
|
deba@430
|
72 |
checkGraphNodeMap(adaptor);
|
deba@430
|
73 |
checkGraphArcMap(adaptor);
|
deba@430
|
74 |
}
|
deba@430
|
75 |
|
deba@430
|
76 |
void checkRevDigraphAdaptor() {
|
deba@430
|
77 |
checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
|
deba@430
|
78 |
|
deba@430
|
79 |
typedef ListDigraph Digraph;
|
deba@430
|
80 |
typedef RevDigraphAdaptor<Digraph> Adaptor;
|
deba@430
|
81 |
|
deba@430
|
82 |
Digraph digraph;
|
deba@430
|
83 |
Adaptor adaptor(digraph);
|
deba@430
|
84 |
|
deba@430
|
85 |
Digraph::Node n1 = digraph.addNode();
|
deba@430
|
86 |
Digraph::Node n2 = digraph.addNode();
|
deba@430
|
87 |
Digraph::Node n3 = digraph.addNode();
|
deba@430
|
88 |
|
deba@430
|
89 |
Digraph::Arc a1 = digraph.addArc(n1, n2);
|
deba@430
|
90 |
Digraph::Arc a2 = digraph.addArc(n1, n3);
|
deba@430
|
91 |
Digraph::Arc a3 = digraph.addArc(n2, n3);
|
deba@430
|
92 |
|
deba@430
|
93 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
94 |
checkGraphArcList(adaptor, 3);
|
deba@430
|
95 |
checkGraphConArcList(adaptor, 3);
|
deba@430
|
96 |
|
deba@430
|
97 |
checkGraphOutArcList(adaptor, n1, 0);
|
deba@430
|
98 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
99 |
checkGraphOutArcList(adaptor, n3, 2);
|
deba@430
|
100 |
|
deba@430
|
101 |
checkGraphInArcList(adaptor, n1, 2);
|
deba@430
|
102 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
103 |
checkGraphInArcList(adaptor, n3, 0);
|
deba@430
|
104 |
|
deba@430
|
105 |
checkNodeIds(adaptor);
|
deba@430
|
106 |
checkArcIds(adaptor);
|
deba@430
|
107 |
|
deba@430
|
108 |
checkGraphNodeMap(adaptor);
|
deba@430
|
109 |
checkGraphArcMap(adaptor);
|
deba@430
|
110 |
|
deba@430
|
111 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
deba@430
|
112 |
check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
|
deba@430
|
113 |
check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
|
deba@430
|
114 |
}
|
deba@430
|
115 |
}
|
deba@430
|
116 |
|
deba@430
|
117 |
void checkSubDigraphAdaptor() {
|
deba@430
|
118 |
checkConcept<concepts::Digraph,
|
deba@430
|
119 |
SubDigraphAdaptor<concepts::Digraph,
|
deba@430
|
120 |
concepts::Digraph::NodeMap<bool>,
|
deba@430
|
121 |
concepts::Digraph::ArcMap<bool> > >();
|
deba@430
|
122 |
|
deba@430
|
123 |
typedef ListDigraph Digraph;
|
deba@430
|
124 |
typedef Digraph::NodeMap<bool> NodeFilter;
|
deba@430
|
125 |
typedef Digraph::ArcMap<bool> ArcFilter;
|
deba@430
|
126 |
typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor;
|
deba@430
|
127 |
|
deba@430
|
128 |
Digraph digraph;
|
deba@430
|
129 |
NodeFilter node_filter(digraph);
|
deba@430
|
130 |
ArcFilter arc_filter(digraph);
|
deba@430
|
131 |
Adaptor adaptor(digraph, node_filter, arc_filter);
|
deba@430
|
132 |
|
deba@430
|
133 |
Digraph::Node n1 = digraph.addNode();
|
deba@430
|
134 |
Digraph::Node n2 = digraph.addNode();
|
deba@430
|
135 |
Digraph::Node n3 = digraph.addNode();
|
deba@430
|
136 |
|
deba@430
|
137 |
Digraph::Arc a1 = digraph.addArc(n1, n2);
|
deba@430
|
138 |
Digraph::Arc a2 = digraph.addArc(n1, n3);
|
deba@430
|
139 |
Digraph::Arc a3 = digraph.addArc(n2, n3);
|
deba@430
|
140 |
|
deba@430
|
141 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
|
deba@430
|
142 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
|
deba@430
|
143 |
|
deba@430
|
144 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
145 |
checkGraphArcList(adaptor, 3);
|
deba@430
|
146 |
checkGraphConArcList(adaptor, 3);
|
deba@430
|
147 |
|
deba@430
|
148 |
checkGraphOutArcList(adaptor, n1, 2);
|
deba@430
|
149 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
150 |
checkGraphOutArcList(adaptor, n3, 0);
|
deba@430
|
151 |
|
deba@430
|
152 |
checkGraphInArcList(adaptor, n1, 0);
|
deba@430
|
153 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
154 |
checkGraphInArcList(adaptor, n3, 2);
|
deba@430
|
155 |
|
deba@430
|
156 |
checkNodeIds(adaptor);
|
deba@430
|
157 |
checkArcIds(adaptor);
|
deba@430
|
158 |
|
deba@430
|
159 |
checkGraphNodeMap(adaptor);
|
deba@430
|
160 |
checkGraphArcMap(adaptor);
|
deba@430
|
161 |
|
deba@430
|
162 |
arc_filter[a2] = false;
|
deba@430
|
163 |
|
deba@430
|
164 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
165 |
checkGraphArcList(adaptor, 2);
|
deba@430
|
166 |
checkGraphConArcList(adaptor, 2);
|
deba@430
|
167 |
|
deba@430
|
168 |
checkGraphOutArcList(adaptor, n1, 1);
|
deba@430
|
169 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
170 |
checkGraphOutArcList(adaptor, n3, 0);
|
deba@430
|
171 |
|
deba@430
|
172 |
checkGraphInArcList(adaptor, n1, 0);
|
deba@430
|
173 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
174 |
checkGraphInArcList(adaptor, n3, 1);
|
deba@430
|
175 |
|
deba@430
|
176 |
checkNodeIds(adaptor);
|
deba@430
|
177 |
checkArcIds(adaptor);
|
deba@430
|
178 |
|
deba@430
|
179 |
checkGraphNodeMap(adaptor);
|
deba@430
|
180 |
checkGraphArcMap(adaptor);
|
deba@430
|
181 |
|
deba@430
|
182 |
node_filter[n1] = false;
|
deba@430
|
183 |
|
deba@430
|
184 |
checkGraphNodeList(adaptor, 2);
|
deba@430
|
185 |
checkGraphArcList(adaptor, 1);
|
deba@430
|
186 |
checkGraphConArcList(adaptor, 1);
|
deba@430
|
187 |
|
deba@430
|
188 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
189 |
checkGraphOutArcList(adaptor, n3, 0);
|
deba@430
|
190 |
|
deba@430
|
191 |
checkGraphInArcList(adaptor, n2, 0);
|
deba@430
|
192 |
checkGraphInArcList(adaptor, n3, 1);
|
deba@430
|
193 |
|
deba@430
|
194 |
checkNodeIds(adaptor);
|
deba@430
|
195 |
checkArcIds(adaptor);
|
deba@430
|
196 |
|
deba@430
|
197 |
checkGraphNodeMap(adaptor);
|
deba@430
|
198 |
checkGraphArcMap(adaptor);
|
deba@430
|
199 |
|
deba@430
|
200 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
|
deba@430
|
201 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
|
deba@430
|
202 |
|
deba@430
|
203 |
checkGraphNodeList(adaptor, 0);
|
deba@430
|
204 |
checkGraphArcList(adaptor, 0);
|
deba@430
|
205 |
checkGraphConArcList(adaptor, 0);
|
deba@430
|
206 |
|
deba@430
|
207 |
checkNodeIds(adaptor);
|
deba@430
|
208 |
checkArcIds(adaptor);
|
deba@430
|
209 |
|
deba@430
|
210 |
checkGraphNodeMap(adaptor);
|
deba@430
|
211 |
checkGraphArcMap(adaptor);
|
deba@430
|
212 |
}
|
deba@430
|
213 |
|
deba@430
|
214 |
void checkNodeSubDigraphAdaptor() {
|
deba@430
|
215 |
checkConcept<concepts::Digraph,
|
deba@430
|
216 |
NodeSubDigraphAdaptor<concepts::Digraph,
|
deba@430
|
217 |
concepts::Digraph::NodeMap<bool> > >();
|
deba@430
|
218 |
|
deba@430
|
219 |
typedef ListDigraph Digraph;
|
deba@430
|
220 |
typedef Digraph::NodeMap<bool> NodeFilter;
|
deba@430
|
221 |
typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;
|
deba@430
|
222 |
|
deba@430
|
223 |
Digraph digraph;
|
deba@430
|
224 |
NodeFilter node_filter(digraph);
|
deba@430
|
225 |
Adaptor adaptor(digraph, node_filter);
|
deba@430
|
226 |
|
deba@430
|
227 |
Digraph::Node n1 = digraph.addNode();
|
deba@430
|
228 |
Digraph::Node n2 = digraph.addNode();
|
deba@430
|
229 |
Digraph::Node n3 = digraph.addNode();
|
deba@430
|
230 |
|
deba@430
|
231 |
Digraph::Arc a1 = digraph.addArc(n1, n2);
|
deba@430
|
232 |
Digraph::Arc a2 = digraph.addArc(n1, n3);
|
deba@430
|
233 |
Digraph::Arc a3 = digraph.addArc(n2, n3);
|
deba@430
|
234 |
|
deba@430
|
235 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
|
deba@430
|
236 |
|
deba@430
|
237 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
238 |
checkGraphArcList(adaptor, 3);
|
deba@430
|
239 |
checkGraphConArcList(adaptor, 3);
|
deba@430
|
240 |
|
deba@430
|
241 |
checkGraphOutArcList(adaptor, n1, 2);
|
deba@430
|
242 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
243 |
checkGraphOutArcList(adaptor, n3, 0);
|
deba@430
|
244 |
|
deba@430
|
245 |
checkGraphInArcList(adaptor, n1, 0);
|
deba@430
|
246 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
247 |
checkGraphInArcList(adaptor, n3, 2);
|
deba@430
|
248 |
|
deba@430
|
249 |
checkNodeIds(adaptor);
|
deba@430
|
250 |
checkArcIds(adaptor);
|
deba@430
|
251 |
|
deba@430
|
252 |
checkGraphNodeMap(adaptor);
|
deba@430
|
253 |
checkGraphArcMap(adaptor);
|
deba@430
|
254 |
|
deba@430
|
255 |
node_filter[n1] = false;
|
deba@430
|
256 |
|
deba@430
|
257 |
checkGraphNodeList(adaptor, 2);
|
deba@430
|
258 |
checkGraphArcList(adaptor, 1);
|
deba@430
|
259 |
checkGraphConArcList(adaptor, 1);
|
deba@430
|
260 |
|
deba@430
|
261 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
262 |
checkGraphOutArcList(adaptor, n3, 0);
|
deba@430
|
263 |
|
deba@430
|
264 |
checkGraphInArcList(adaptor, n2, 0);
|
deba@430
|
265 |
checkGraphInArcList(adaptor, n3, 1);
|
deba@430
|
266 |
|
deba@430
|
267 |
checkNodeIds(adaptor);
|
deba@430
|
268 |
checkArcIds(adaptor);
|
deba@430
|
269 |
|
deba@430
|
270 |
checkGraphNodeMap(adaptor);
|
deba@430
|
271 |
checkGraphArcMap(adaptor);
|
deba@430
|
272 |
|
deba@430
|
273 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
|
deba@430
|
274 |
|
deba@430
|
275 |
checkGraphNodeList(adaptor, 0);
|
deba@430
|
276 |
checkGraphArcList(adaptor, 0);
|
deba@430
|
277 |
checkGraphConArcList(adaptor, 0);
|
deba@430
|
278 |
|
deba@430
|
279 |
checkNodeIds(adaptor);
|
deba@430
|
280 |
checkArcIds(adaptor);
|
deba@430
|
281 |
|
deba@430
|
282 |
checkGraphNodeMap(adaptor);
|
deba@430
|
283 |
checkGraphArcMap(adaptor);
|
deba@430
|
284 |
}
|
deba@430
|
285 |
|
deba@430
|
286 |
void checkArcSubDigraphAdaptor() {
|
deba@430
|
287 |
checkConcept<concepts::Digraph,
|
deba@430
|
288 |
ArcSubDigraphAdaptor<concepts::Digraph,
|
deba@430
|
289 |
concepts::Digraph::ArcMap<bool> > >();
|
deba@430
|
290 |
|
deba@430
|
291 |
typedef ListDigraph Digraph;
|
deba@430
|
292 |
typedef Digraph::ArcMap<bool> ArcFilter;
|
deba@430
|
293 |
typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;
|
deba@430
|
294 |
|
deba@430
|
295 |
Digraph digraph;
|
deba@430
|
296 |
ArcFilter arc_filter(digraph);
|
deba@430
|
297 |
Adaptor adaptor(digraph, arc_filter);
|
deba@430
|
298 |
|
deba@430
|
299 |
Digraph::Node n1 = digraph.addNode();
|
deba@430
|
300 |
Digraph::Node n2 = digraph.addNode();
|
deba@430
|
301 |
Digraph::Node n3 = digraph.addNode();
|
deba@430
|
302 |
|
deba@430
|
303 |
Digraph::Arc a1 = digraph.addArc(n1, n2);
|
deba@430
|
304 |
Digraph::Arc a2 = digraph.addArc(n1, n3);
|
deba@430
|
305 |
Digraph::Arc a3 = digraph.addArc(n2, n3);
|
deba@430
|
306 |
|
deba@430
|
307 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
|
deba@430
|
308 |
|
deba@430
|
309 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
310 |
checkGraphArcList(adaptor, 3);
|
deba@430
|
311 |
checkGraphConArcList(adaptor, 3);
|
deba@430
|
312 |
|
deba@430
|
313 |
checkGraphOutArcList(adaptor, n1, 2);
|
deba@430
|
314 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
315 |
checkGraphOutArcList(adaptor, n3, 0);
|
deba@430
|
316 |
|
deba@430
|
317 |
checkGraphInArcList(adaptor, n1, 0);
|
deba@430
|
318 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
319 |
checkGraphInArcList(adaptor, n3, 2);
|
deba@430
|
320 |
|
deba@430
|
321 |
checkNodeIds(adaptor);
|
deba@430
|
322 |
checkArcIds(adaptor);
|
deba@430
|
323 |
|
deba@430
|
324 |
checkGraphNodeMap(adaptor);
|
deba@430
|
325 |
checkGraphArcMap(adaptor);
|
deba@430
|
326 |
|
deba@430
|
327 |
arc_filter[a2] = false;
|
deba@430
|
328 |
|
deba@430
|
329 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
330 |
checkGraphArcList(adaptor, 2);
|
deba@430
|
331 |
checkGraphConArcList(adaptor, 2);
|
deba@430
|
332 |
|
deba@430
|
333 |
checkGraphOutArcList(adaptor, n1, 1);
|
deba@430
|
334 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
335 |
checkGraphOutArcList(adaptor, n3, 0);
|
deba@430
|
336 |
|
deba@430
|
337 |
checkGraphInArcList(adaptor, n1, 0);
|
deba@430
|
338 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
339 |
checkGraphInArcList(adaptor, n3, 1);
|
deba@430
|
340 |
|
deba@430
|
341 |
checkNodeIds(adaptor);
|
deba@430
|
342 |
checkArcIds(adaptor);
|
deba@430
|
343 |
|
deba@430
|
344 |
checkGraphNodeMap(adaptor);
|
deba@430
|
345 |
checkGraphArcMap(adaptor);
|
deba@430
|
346 |
|
deba@430
|
347 |
arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
|
deba@430
|
348 |
|
deba@430
|
349 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
350 |
checkGraphArcList(adaptor, 0);
|
deba@430
|
351 |
checkGraphConArcList(adaptor, 0);
|
deba@430
|
352 |
|
deba@430
|
353 |
checkNodeIds(adaptor);
|
deba@430
|
354 |
checkArcIds(adaptor);
|
deba@430
|
355 |
|
deba@430
|
356 |
checkGraphNodeMap(adaptor);
|
deba@430
|
357 |
checkGraphArcMap(adaptor);
|
deba@430
|
358 |
}
|
deba@430
|
359 |
|
deba@430
|
360 |
void checkUndirDigraphAdaptor() {
|
deba@430
|
361 |
checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();
|
deba@430
|
362 |
|
deba@430
|
363 |
typedef ListDigraph Digraph;
|
deba@430
|
364 |
typedef UndirDigraphAdaptor<Digraph> Adaptor;
|
deba@430
|
365 |
|
deba@430
|
366 |
Digraph digraph;
|
deba@430
|
367 |
Adaptor adaptor(digraph);
|
deba@430
|
368 |
|
deba@430
|
369 |
Digraph::Node n1 = digraph.addNode();
|
deba@430
|
370 |
Digraph::Node n2 = digraph.addNode();
|
deba@430
|
371 |
Digraph::Node n3 = digraph.addNode();
|
deba@430
|
372 |
|
deba@430
|
373 |
Digraph::Arc a1 = digraph.addArc(n1, n2);
|
deba@430
|
374 |
Digraph::Arc a2 = digraph.addArc(n1, n3);
|
deba@430
|
375 |
Digraph::Arc a3 = digraph.addArc(n2, n3);
|
deba@430
|
376 |
|
deba@430
|
377 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
378 |
checkGraphArcList(adaptor, 6);
|
deba@430
|
379 |
checkGraphEdgeList(adaptor, 3);
|
deba@430
|
380 |
checkGraphConArcList(adaptor, 6);
|
deba@430
|
381 |
checkGraphConEdgeList(adaptor, 3);
|
deba@430
|
382 |
|
deba@430
|
383 |
checkGraphOutArcList(adaptor, n1, 2);
|
deba@430
|
384 |
checkGraphOutArcList(adaptor, n2, 2);
|
deba@430
|
385 |
checkGraphOutArcList(adaptor, n3, 2);
|
deba@430
|
386 |
|
deba@430
|
387 |
checkGraphInArcList(adaptor, n1, 2);
|
deba@430
|
388 |
checkGraphInArcList(adaptor, n2, 2);
|
deba@430
|
389 |
checkGraphInArcList(adaptor, n3, 2);
|
deba@430
|
390 |
|
deba@430
|
391 |
checkGraphIncEdgeList(adaptor, n1, 2);
|
deba@430
|
392 |
checkGraphIncEdgeList(adaptor, n2, 2);
|
deba@430
|
393 |
checkGraphIncEdgeList(adaptor, n3, 2);
|
deba@430
|
394 |
|
deba@430
|
395 |
checkNodeIds(adaptor);
|
deba@430
|
396 |
checkArcIds(adaptor);
|
deba@430
|
397 |
checkEdgeIds(adaptor);
|
deba@430
|
398 |
|
deba@430
|
399 |
checkGraphNodeMap(adaptor);
|
deba@430
|
400 |
checkGraphArcMap(adaptor);
|
deba@430
|
401 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
402 |
|
deba@430
|
403 |
for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
|
deba@430
|
404 |
check(adaptor.u(e) == digraph.source(e), "Wrong undir");
|
deba@430
|
405 |
check(adaptor.v(e) == digraph.target(e), "Wrong undir");
|
deba@430
|
406 |
}
|
deba@430
|
407 |
|
deba@430
|
408 |
}
|
deba@430
|
409 |
|
deba@430
|
410 |
void checkResDigraphAdaptor() {
|
deba@430
|
411 |
checkConcept<concepts::Digraph,
|
deba@430
|
412 |
ResDigraphAdaptor<concepts::Digraph,
|
deba@430
|
413 |
concepts::Digraph::ArcMap<int>,
|
deba@430
|
414 |
concepts::Digraph::ArcMap<int> > >();
|
deba@430
|
415 |
|
deba@430
|
416 |
typedef ListDigraph Digraph;
|
deba@430
|
417 |
typedef Digraph::ArcMap<int> IntArcMap;
|
deba@430
|
418 |
typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;
|
deba@430
|
419 |
|
deba@430
|
420 |
Digraph digraph;
|
deba@430
|
421 |
IntArcMap capacity(digraph), flow(digraph);
|
deba@430
|
422 |
Adaptor adaptor(digraph, capacity, flow);
|
deba@430
|
423 |
|
deba@430
|
424 |
Digraph::Node n1 = digraph.addNode();
|
deba@430
|
425 |
Digraph::Node n2 = digraph.addNode();
|
deba@430
|
426 |
Digraph::Node n3 = digraph.addNode();
|
deba@430
|
427 |
Digraph::Node n4 = digraph.addNode();
|
deba@430
|
428 |
|
deba@430
|
429 |
Digraph::Arc a1 = digraph.addArc(n1, n2);
|
deba@430
|
430 |
Digraph::Arc a2 = digraph.addArc(n1, n3);
|
deba@430
|
431 |
Digraph::Arc a3 = digraph.addArc(n1, n4);
|
deba@430
|
432 |
Digraph::Arc a4 = digraph.addArc(n2, n3);
|
deba@430
|
433 |
Digraph::Arc a5 = digraph.addArc(n2, n4);
|
deba@430
|
434 |
Digraph::Arc a6 = digraph.addArc(n3, n4);
|
deba@430
|
435 |
|
deba@430
|
436 |
capacity[a1] = 8;
|
deba@430
|
437 |
capacity[a2] = 6;
|
deba@430
|
438 |
capacity[a3] = 4;
|
deba@430
|
439 |
capacity[a4] = 4;
|
deba@430
|
440 |
capacity[a5] = 6;
|
deba@430
|
441 |
capacity[a6] = 10;
|
deba@430
|
442 |
|
deba@430
|
443 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
deba@430
|
444 |
flow[a] = 0;
|
deba@430
|
445 |
}
|
deba@430
|
446 |
|
deba@430
|
447 |
checkGraphNodeList(adaptor, 4);
|
deba@430
|
448 |
checkGraphArcList(adaptor, 6);
|
deba@430
|
449 |
checkGraphConArcList(adaptor, 6);
|
deba@430
|
450 |
|
deba@430
|
451 |
checkGraphOutArcList(adaptor, n1, 3);
|
deba@430
|
452 |
checkGraphOutArcList(adaptor, n2, 2);
|
deba@430
|
453 |
checkGraphOutArcList(adaptor, n3, 1);
|
deba@430
|
454 |
checkGraphOutArcList(adaptor, n4, 0);
|
deba@430
|
455 |
|
deba@430
|
456 |
checkGraphInArcList(adaptor, n1, 0);
|
deba@430
|
457 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
458 |
checkGraphInArcList(adaptor, n3, 2);
|
deba@430
|
459 |
checkGraphInArcList(adaptor, n4, 3);
|
deba@430
|
460 |
|
deba@430
|
461 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
deba@430
|
462 |
flow[a] = capacity[a] / 2;
|
deba@430
|
463 |
}
|
deba@430
|
464 |
|
deba@430
|
465 |
checkGraphNodeList(adaptor, 4);
|
deba@430
|
466 |
checkGraphArcList(adaptor, 12);
|
deba@430
|
467 |
checkGraphConArcList(adaptor, 12);
|
deba@430
|
468 |
|
deba@430
|
469 |
checkGraphOutArcList(adaptor, n1, 3);
|
deba@430
|
470 |
checkGraphOutArcList(adaptor, n2, 3);
|
deba@430
|
471 |
checkGraphOutArcList(adaptor, n3, 3);
|
deba@430
|
472 |
checkGraphOutArcList(adaptor, n4, 3);
|
deba@430
|
473 |
|
deba@430
|
474 |
checkGraphInArcList(adaptor, n1, 3);
|
deba@430
|
475 |
checkGraphInArcList(adaptor, n2, 3);
|
deba@430
|
476 |
checkGraphInArcList(adaptor, n3, 3);
|
deba@430
|
477 |
checkGraphInArcList(adaptor, n4, 3);
|
deba@430
|
478 |
|
deba@430
|
479 |
checkNodeIds(adaptor);
|
deba@430
|
480 |
checkArcIds(adaptor);
|
deba@430
|
481 |
|
deba@430
|
482 |
checkGraphNodeMap(adaptor);
|
deba@430
|
483 |
checkGraphArcMap(adaptor);
|
deba@430
|
484 |
|
deba@430
|
485 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
deba@430
|
486 |
flow[a] = capacity[a];
|
deba@430
|
487 |
}
|
deba@430
|
488 |
|
deba@430
|
489 |
checkGraphNodeList(adaptor, 4);
|
deba@430
|
490 |
checkGraphArcList(adaptor, 6);
|
deba@430
|
491 |
checkGraphConArcList(adaptor, 6);
|
deba@430
|
492 |
|
deba@430
|
493 |
checkGraphOutArcList(adaptor, n1, 0);
|
deba@430
|
494 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
495 |
checkGraphOutArcList(adaptor, n3, 2);
|
deba@430
|
496 |
checkGraphOutArcList(adaptor, n4, 3);
|
deba@430
|
497 |
|
deba@430
|
498 |
checkGraphInArcList(adaptor, n1, 3);
|
deba@430
|
499 |
checkGraphInArcList(adaptor, n2, 2);
|
deba@430
|
500 |
checkGraphInArcList(adaptor, n3, 1);
|
deba@430
|
501 |
checkGraphInArcList(adaptor, n4, 0);
|
deba@430
|
502 |
|
deba@430
|
503 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
deba@430
|
504 |
flow[a] = 0;
|
deba@430
|
505 |
}
|
deba@430
|
506 |
|
deba@430
|
507 |
int flow_value = 0;
|
deba@430
|
508 |
while (true) {
|
deba@430
|
509 |
|
deba@430
|
510 |
Bfs<Adaptor> bfs(adaptor);
|
deba@430
|
511 |
bfs.run(n1, n4);
|
deba@430
|
512 |
|
deba@430
|
513 |
if (!bfs.reached(n4)) break;
|
deba@430
|
514 |
|
deba@430
|
515 |
Path<Adaptor> p = bfs.path(n4);
|
deba@430
|
516 |
|
deba@430
|
517 |
int min = std::numeric_limits<int>::max();
|
deba@430
|
518 |
for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
|
deba@430
|
519 |
if (adaptor.rescap(a) < min) min = adaptor.rescap(a);
|
deba@430
|
520 |
}
|
deba@430
|
521 |
|
deba@430
|
522 |
for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
|
deba@430
|
523 |
adaptor.augment(a, min);
|
deba@430
|
524 |
}
|
deba@430
|
525 |
flow_value += min;
|
deba@430
|
526 |
}
|
deba@430
|
527 |
|
deba@430
|
528 |
check(flow_value == 18, "Wrong flow with res graph adaptor");
|
deba@430
|
529 |
|
deba@430
|
530 |
}
|
deba@430
|
531 |
|
deba@430
|
532 |
void checkSplitDigraphAdaptor() {
|
deba@430
|
533 |
checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();
|
deba@430
|
534 |
|
deba@430
|
535 |
typedef ListDigraph Digraph;
|
deba@430
|
536 |
typedef SplitDigraphAdaptor<Digraph> Adaptor;
|
deba@430
|
537 |
|
deba@430
|
538 |
Digraph digraph;
|
deba@430
|
539 |
Adaptor adaptor(digraph);
|
deba@430
|
540 |
|
deba@430
|
541 |
Digraph::Node n1 = digraph.addNode();
|
deba@430
|
542 |
Digraph::Node n2 = digraph.addNode();
|
deba@430
|
543 |
Digraph::Node n3 = digraph.addNode();
|
deba@430
|
544 |
|
deba@430
|
545 |
Digraph::Arc a1 = digraph.addArc(n1, n2);
|
deba@430
|
546 |
Digraph::Arc a2 = digraph.addArc(n1, n3);
|
deba@430
|
547 |
Digraph::Arc a3 = digraph.addArc(n2, n3);
|
deba@430
|
548 |
|
deba@430
|
549 |
checkGraphNodeList(adaptor, 6);
|
deba@430
|
550 |
checkGraphArcList(adaptor, 6);
|
deba@430
|
551 |
checkGraphConArcList(adaptor, 6);
|
deba@430
|
552 |
|
deba@430
|
553 |
checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
|
deba@430
|
554 |
checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
|
deba@430
|
555 |
checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
|
deba@430
|
556 |
checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
|
deba@430
|
557 |
checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
|
deba@430
|
558 |
checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
|
deba@430
|
559 |
|
deba@430
|
560 |
checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
|
deba@430
|
561 |
checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
|
deba@430
|
562 |
checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
|
deba@430
|
563 |
checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
|
deba@430
|
564 |
checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
|
deba@430
|
565 |
checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
|
deba@430
|
566 |
|
deba@430
|
567 |
checkNodeIds(adaptor);
|
deba@430
|
568 |
checkArcIds(adaptor);
|
deba@430
|
569 |
|
deba@430
|
570 |
checkGraphNodeMap(adaptor);
|
deba@430
|
571 |
checkGraphArcMap(adaptor);
|
deba@430
|
572 |
|
deba@430
|
573 |
for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
|
deba@430
|
574 |
if (adaptor.origArc(a)) {
|
deba@430
|
575 |
Digraph::Arc oa = a;
|
deba@430
|
576 |
check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
|
deba@430
|
577 |
"Wrong split");
|
deba@430
|
578 |
check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
|
deba@430
|
579 |
"Wrong split");
|
deba@430
|
580 |
} else {
|
deba@430
|
581 |
Digraph::Node on = a;
|
deba@430
|
582 |
check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
|
deba@430
|
583 |
check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
|
deba@430
|
584 |
}
|
deba@430
|
585 |
}
|
deba@430
|
586 |
}
|
deba@430
|
587 |
|
deba@430
|
588 |
void checkGraphAdaptor() {
|
deba@430
|
589 |
checkConcept<concepts::Graph, GraphAdaptor<concepts::Graph> >();
|
deba@430
|
590 |
|
deba@430
|
591 |
typedef ListGraph Graph;
|
deba@430
|
592 |
typedef GraphAdaptor<Graph> Adaptor;
|
deba@430
|
593 |
|
deba@430
|
594 |
Graph graph;
|
deba@430
|
595 |
Adaptor adaptor(graph);
|
deba@430
|
596 |
|
deba@430
|
597 |
Graph::Node n1 = graph.addNode();
|
deba@430
|
598 |
Graph::Node n2 = graph.addNode();
|
deba@430
|
599 |
Graph::Node n3 = graph.addNode();
|
deba@430
|
600 |
Graph::Node n4 = graph.addNode();
|
deba@430
|
601 |
|
deba@430
|
602 |
Graph::Edge a1 = graph.addEdge(n1, n2);
|
deba@430
|
603 |
Graph::Edge a2 = graph.addEdge(n1, n3);
|
deba@430
|
604 |
Graph::Edge a3 = graph.addEdge(n2, n3);
|
deba@430
|
605 |
Graph::Edge a4 = graph.addEdge(n3, n4);
|
deba@430
|
606 |
|
deba@430
|
607 |
checkGraphNodeList(adaptor, 4);
|
deba@430
|
608 |
checkGraphArcList(adaptor, 8);
|
deba@430
|
609 |
checkGraphEdgeList(adaptor, 4);
|
deba@430
|
610 |
checkGraphConArcList(adaptor, 8);
|
deba@430
|
611 |
checkGraphConEdgeList(adaptor, 4);
|
deba@430
|
612 |
|
deba@430
|
613 |
checkGraphOutArcList(adaptor, n1, 2);
|
deba@430
|
614 |
checkGraphOutArcList(adaptor, n2, 2);
|
deba@430
|
615 |
checkGraphOutArcList(adaptor, n3, 3);
|
deba@430
|
616 |
checkGraphOutArcList(adaptor, n4, 1);
|
deba@430
|
617 |
|
deba@430
|
618 |
checkGraphInArcList(adaptor, n1, 2);
|
deba@430
|
619 |
checkGraphInArcList(adaptor, n2, 2);
|
deba@430
|
620 |
checkGraphInArcList(adaptor, n3, 3);
|
deba@430
|
621 |
checkGraphInArcList(adaptor, n4, 1);
|
deba@430
|
622 |
|
deba@430
|
623 |
checkGraphIncEdgeList(adaptor, n1, 2);
|
deba@430
|
624 |
checkGraphIncEdgeList(adaptor, n2, 2);
|
deba@430
|
625 |
checkGraphIncEdgeList(adaptor, n3, 3);
|
deba@430
|
626 |
checkGraphIncEdgeList(adaptor, n4, 1);
|
deba@430
|
627 |
|
deba@430
|
628 |
|
deba@430
|
629 |
checkNodeIds(adaptor);
|
deba@430
|
630 |
checkArcIds(adaptor);
|
deba@430
|
631 |
checkEdgeIds(adaptor);
|
deba@430
|
632 |
|
deba@430
|
633 |
checkGraphNodeMap(adaptor);
|
deba@430
|
634 |
checkGraphArcMap(adaptor);
|
deba@430
|
635 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
636 |
}
|
deba@430
|
637 |
|
deba@430
|
638 |
void checkSubGraphAdaptor() {
|
deba@430
|
639 |
checkConcept<concepts::Graph,
|
deba@430
|
640 |
SubGraphAdaptor<concepts::Graph,
|
deba@430
|
641 |
concepts::Graph::NodeMap<bool>,
|
deba@430
|
642 |
concepts::Graph::EdgeMap<bool> > >();
|
deba@430
|
643 |
|
deba@430
|
644 |
typedef ListGraph Graph;
|
deba@430
|
645 |
typedef Graph::NodeMap<bool> NodeFilter;
|
deba@430
|
646 |
typedef Graph::EdgeMap<bool> EdgeFilter;
|
deba@430
|
647 |
typedef SubGraphAdaptor<Graph, NodeFilter, EdgeFilter> Adaptor;
|
deba@430
|
648 |
|
deba@430
|
649 |
Graph graph;
|
deba@430
|
650 |
NodeFilter node_filter(graph);
|
deba@430
|
651 |
EdgeFilter edge_filter(graph);
|
deba@430
|
652 |
Adaptor adaptor(graph, node_filter, edge_filter);
|
deba@430
|
653 |
|
deba@430
|
654 |
Graph::Node n1 = graph.addNode();
|
deba@430
|
655 |
Graph::Node n2 = graph.addNode();
|
deba@430
|
656 |
Graph::Node n3 = graph.addNode();
|
deba@430
|
657 |
Graph::Node n4 = graph.addNode();
|
deba@430
|
658 |
|
deba@430
|
659 |
Graph::Edge e1 = graph.addEdge(n1, n2);
|
deba@430
|
660 |
Graph::Edge e2 = graph.addEdge(n1, n3);
|
deba@430
|
661 |
Graph::Edge e3 = graph.addEdge(n2, n3);
|
deba@430
|
662 |
Graph::Edge e4 = graph.addEdge(n3, n4);
|
deba@430
|
663 |
|
deba@430
|
664 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
|
deba@430
|
665 |
edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
|
deba@430
|
666 |
|
deba@430
|
667 |
checkGraphNodeList(adaptor, 4);
|
deba@430
|
668 |
checkGraphArcList(adaptor, 8);
|
deba@430
|
669 |
checkGraphEdgeList(adaptor, 4);
|
deba@430
|
670 |
checkGraphConArcList(adaptor, 8);
|
deba@430
|
671 |
checkGraphConEdgeList(adaptor, 4);
|
deba@430
|
672 |
|
deba@430
|
673 |
checkGraphOutArcList(adaptor, n1, 2);
|
deba@430
|
674 |
checkGraphOutArcList(adaptor, n2, 2);
|
deba@430
|
675 |
checkGraphOutArcList(adaptor, n3, 3);
|
deba@430
|
676 |
checkGraphOutArcList(adaptor, n4, 1);
|
deba@430
|
677 |
|
deba@430
|
678 |
checkGraphInArcList(adaptor, n1, 2);
|
deba@430
|
679 |
checkGraphInArcList(adaptor, n2, 2);
|
deba@430
|
680 |
checkGraphInArcList(adaptor, n3, 3);
|
deba@430
|
681 |
checkGraphInArcList(adaptor, n4, 1);
|
deba@430
|
682 |
|
deba@430
|
683 |
checkGraphIncEdgeList(adaptor, n1, 2);
|
deba@430
|
684 |
checkGraphIncEdgeList(adaptor, n2, 2);
|
deba@430
|
685 |
checkGraphIncEdgeList(adaptor, n3, 3);
|
deba@430
|
686 |
checkGraphIncEdgeList(adaptor, n4, 1);
|
deba@430
|
687 |
|
deba@430
|
688 |
checkNodeIds(adaptor);
|
deba@430
|
689 |
checkArcIds(adaptor);
|
deba@430
|
690 |
checkEdgeIds(adaptor);
|
deba@430
|
691 |
|
deba@430
|
692 |
checkGraphNodeMap(adaptor);
|
deba@430
|
693 |
checkGraphArcMap(adaptor);
|
deba@430
|
694 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
695 |
|
deba@430
|
696 |
edge_filter[e2] = false;
|
deba@430
|
697 |
|
deba@430
|
698 |
checkGraphNodeList(adaptor, 4);
|
deba@430
|
699 |
checkGraphArcList(adaptor, 6);
|
deba@430
|
700 |
checkGraphEdgeList(adaptor, 3);
|
deba@430
|
701 |
checkGraphConArcList(adaptor, 6);
|
deba@430
|
702 |
checkGraphConEdgeList(adaptor, 3);
|
deba@430
|
703 |
|
deba@430
|
704 |
checkGraphOutArcList(adaptor, n1, 1);
|
deba@430
|
705 |
checkGraphOutArcList(adaptor, n2, 2);
|
deba@430
|
706 |
checkGraphOutArcList(adaptor, n3, 2);
|
deba@430
|
707 |
checkGraphOutArcList(adaptor, n4, 1);
|
deba@430
|
708 |
|
deba@430
|
709 |
checkGraphInArcList(adaptor, n1, 1);
|
deba@430
|
710 |
checkGraphInArcList(adaptor, n2, 2);
|
deba@430
|
711 |
checkGraphInArcList(adaptor, n3, 2);
|
deba@430
|
712 |
checkGraphInArcList(adaptor, n4, 1);
|
deba@430
|
713 |
|
deba@430
|
714 |
checkGraphIncEdgeList(adaptor, n1, 1);
|
deba@430
|
715 |
checkGraphIncEdgeList(adaptor, n2, 2);
|
deba@430
|
716 |
checkGraphIncEdgeList(adaptor, n3, 2);
|
deba@430
|
717 |
checkGraphIncEdgeList(adaptor, n4, 1);
|
deba@430
|
718 |
|
deba@430
|
719 |
checkNodeIds(adaptor);
|
deba@430
|
720 |
checkArcIds(adaptor);
|
deba@430
|
721 |
checkEdgeIds(adaptor);
|
deba@430
|
722 |
|
deba@430
|
723 |
checkGraphNodeMap(adaptor);
|
deba@430
|
724 |
checkGraphArcMap(adaptor);
|
deba@430
|
725 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
726 |
|
deba@430
|
727 |
node_filter[n1] = false;
|
deba@430
|
728 |
|
deba@430
|
729 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
730 |
checkGraphArcList(adaptor, 4);
|
deba@430
|
731 |
checkGraphEdgeList(adaptor, 2);
|
deba@430
|
732 |
checkGraphConArcList(adaptor, 4);
|
deba@430
|
733 |
checkGraphConEdgeList(adaptor, 2);
|
deba@430
|
734 |
|
deba@430
|
735 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
736 |
checkGraphOutArcList(adaptor, n3, 2);
|
deba@430
|
737 |
checkGraphOutArcList(adaptor, n4, 1);
|
deba@430
|
738 |
|
deba@430
|
739 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
740 |
checkGraphInArcList(adaptor, n3, 2);
|
deba@430
|
741 |
checkGraphInArcList(adaptor, n4, 1);
|
deba@430
|
742 |
|
deba@430
|
743 |
checkGraphIncEdgeList(adaptor, n2, 1);
|
deba@430
|
744 |
checkGraphIncEdgeList(adaptor, n3, 2);
|
deba@430
|
745 |
checkGraphIncEdgeList(adaptor, n4, 1);
|
deba@430
|
746 |
|
deba@430
|
747 |
checkNodeIds(adaptor);
|
deba@430
|
748 |
checkArcIds(adaptor);
|
deba@430
|
749 |
checkEdgeIds(adaptor);
|
deba@430
|
750 |
|
deba@430
|
751 |
checkGraphNodeMap(adaptor);
|
deba@430
|
752 |
checkGraphArcMap(adaptor);
|
deba@430
|
753 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
754 |
|
deba@430
|
755 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
|
deba@430
|
756 |
edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
|
deba@430
|
757 |
|
deba@430
|
758 |
checkGraphNodeList(adaptor, 0);
|
deba@430
|
759 |
checkGraphArcList(adaptor, 0);
|
deba@430
|
760 |
checkGraphEdgeList(adaptor, 0);
|
deba@430
|
761 |
checkGraphConArcList(adaptor, 0);
|
deba@430
|
762 |
checkGraphConEdgeList(adaptor, 0);
|
deba@430
|
763 |
|
deba@430
|
764 |
checkNodeIds(adaptor);
|
deba@430
|
765 |
checkArcIds(adaptor);
|
deba@430
|
766 |
checkEdgeIds(adaptor);
|
deba@430
|
767 |
|
deba@430
|
768 |
checkGraphNodeMap(adaptor);
|
deba@430
|
769 |
checkGraphArcMap(adaptor);
|
deba@430
|
770 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
771 |
}
|
deba@430
|
772 |
|
deba@430
|
773 |
void checkNodeSubGraphAdaptor() {
|
deba@430
|
774 |
checkConcept<concepts::Graph,
|
deba@430
|
775 |
NodeSubGraphAdaptor<concepts::Graph,
|
deba@430
|
776 |
concepts::Graph::NodeMap<bool> > >();
|
deba@430
|
777 |
|
deba@430
|
778 |
typedef ListGraph Graph;
|
deba@430
|
779 |
typedef Graph::NodeMap<bool> NodeFilter;
|
deba@430
|
780 |
typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;
|
deba@430
|
781 |
|
deba@430
|
782 |
Graph graph;
|
deba@430
|
783 |
NodeFilter node_filter(graph);
|
deba@430
|
784 |
Adaptor adaptor(graph, node_filter);
|
deba@430
|
785 |
|
deba@430
|
786 |
Graph::Node n1 = graph.addNode();
|
deba@430
|
787 |
Graph::Node n2 = graph.addNode();
|
deba@430
|
788 |
Graph::Node n3 = graph.addNode();
|
deba@430
|
789 |
Graph::Node n4 = graph.addNode();
|
deba@430
|
790 |
|
deba@430
|
791 |
Graph::Edge e1 = graph.addEdge(n1, n2);
|
deba@430
|
792 |
Graph::Edge e2 = graph.addEdge(n1, n3);
|
deba@430
|
793 |
Graph::Edge e3 = graph.addEdge(n2, n3);
|
deba@430
|
794 |
Graph::Edge e4 = graph.addEdge(n3, n4);
|
deba@430
|
795 |
|
deba@430
|
796 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
|
deba@430
|
797 |
|
deba@430
|
798 |
checkGraphNodeList(adaptor, 4);
|
deba@430
|
799 |
checkGraphArcList(adaptor, 8);
|
deba@430
|
800 |
checkGraphEdgeList(adaptor, 4);
|
deba@430
|
801 |
checkGraphConArcList(adaptor, 8);
|
deba@430
|
802 |
checkGraphConEdgeList(adaptor, 4);
|
deba@430
|
803 |
|
deba@430
|
804 |
checkGraphOutArcList(adaptor, n1, 2);
|
deba@430
|
805 |
checkGraphOutArcList(adaptor, n2, 2);
|
deba@430
|
806 |
checkGraphOutArcList(adaptor, n3, 3);
|
deba@430
|
807 |
checkGraphOutArcList(adaptor, n4, 1);
|
deba@430
|
808 |
|
deba@430
|
809 |
checkGraphInArcList(adaptor, n1, 2);
|
deba@430
|
810 |
checkGraphInArcList(adaptor, n2, 2);
|
deba@430
|
811 |
checkGraphInArcList(adaptor, n3, 3);
|
deba@430
|
812 |
checkGraphInArcList(adaptor, n4, 1);
|
deba@430
|
813 |
|
deba@430
|
814 |
checkGraphIncEdgeList(adaptor, n1, 2);
|
deba@430
|
815 |
checkGraphIncEdgeList(adaptor, n2, 2);
|
deba@430
|
816 |
checkGraphIncEdgeList(adaptor, n3, 3);
|
deba@430
|
817 |
checkGraphIncEdgeList(adaptor, n4, 1);
|
deba@430
|
818 |
|
deba@430
|
819 |
checkNodeIds(adaptor);
|
deba@430
|
820 |
checkArcIds(adaptor);
|
deba@430
|
821 |
checkEdgeIds(adaptor);
|
deba@430
|
822 |
|
deba@430
|
823 |
checkGraphNodeMap(adaptor);
|
deba@430
|
824 |
checkGraphArcMap(adaptor);
|
deba@430
|
825 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
826 |
|
deba@430
|
827 |
node_filter[n1] = false;
|
deba@430
|
828 |
|
deba@430
|
829 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
830 |
checkGraphArcList(adaptor, 4);
|
deba@430
|
831 |
checkGraphEdgeList(adaptor, 2);
|
deba@430
|
832 |
checkGraphConArcList(adaptor, 4);
|
deba@430
|
833 |
checkGraphConEdgeList(adaptor, 2);
|
deba@430
|
834 |
|
deba@430
|
835 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
836 |
checkGraphOutArcList(adaptor, n3, 2);
|
deba@430
|
837 |
checkGraphOutArcList(adaptor, n4, 1);
|
deba@430
|
838 |
|
deba@430
|
839 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
840 |
checkGraphInArcList(adaptor, n3, 2);
|
deba@430
|
841 |
checkGraphInArcList(adaptor, n4, 1);
|
deba@430
|
842 |
|
deba@430
|
843 |
checkGraphIncEdgeList(adaptor, n2, 1);
|
deba@430
|
844 |
checkGraphIncEdgeList(adaptor, n3, 2);
|
deba@430
|
845 |
checkGraphIncEdgeList(adaptor, n4, 1);
|
deba@430
|
846 |
|
deba@430
|
847 |
checkNodeIds(adaptor);
|
deba@430
|
848 |
checkArcIds(adaptor);
|
deba@430
|
849 |
checkEdgeIds(adaptor);
|
deba@430
|
850 |
|
deba@430
|
851 |
checkGraphNodeMap(adaptor);
|
deba@430
|
852 |
checkGraphArcMap(adaptor);
|
deba@430
|
853 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
854 |
|
deba@430
|
855 |
node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
|
deba@430
|
856 |
|
deba@430
|
857 |
checkGraphNodeList(adaptor, 0);
|
deba@430
|
858 |
checkGraphArcList(adaptor, 0);
|
deba@430
|
859 |
checkGraphEdgeList(adaptor, 0);
|
deba@430
|
860 |
checkGraphConArcList(adaptor, 0);
|
deba@430
|
861 |
checkGraphConEdgeList(adaptor, 0);
|
deba@430
|
862 |
|
deba@430
|
863 |
checkNodeIds(adaptor);
|
deba@430
|
864 |
checkArcIds(adaptor);
|
deba@430
|
865 |
checkEdgeIds(adaptor);
|
deba@430
|
866 |
|
deba@430
|
867 |
checkGraphNodeMap(adaptor);
|
deba@430
|
868 |
checkGraphArcMap(adaptor);
|
deba@430
|
869 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
870 |
}
|
deba@430
|
871 |
|
deba@430
|
872 |
void checkEdgeSubGraphAdaptor() {
|
deba@430
|
873 |
checkConcept<concepts::Graph,
|
deba@430
|
874 |
EdgeSubGraphAdaptor<concepts::Graph,
|
deba@430
|
875 |
concepts::Graph::EdgeMap<bool> > >();
|
deba@430
|
876 |
|
deba@430
|
877 |
typedef ListGraph Graph;
|
deba@430
|
878 |
typedef Graph::EdgeMap<bool> EdgeFilter;
|
deba@430
|
879 |
typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;
|
deba@430
|
880 |
|
deba@430
|
881 |
Graph graph;
|
deba@430
|
882 |
EdgeFilter edge_filter(graph);
|
deba@430
|
883 |
Adaptor adaptor(graph, edge_filter);
|
deba@430
|
884 |
|
deba@430
|
885 |
Graph::Node n1 = graph.addNode();
|
deba@430
|
886 |
Graph::Node n2 = graph.addNode();
|
deba@430
|
887 |
Graph::Node n3 = graph.addNode();
|
deba@430
|
888 |
Graph::Node n4 = graph.addNode();
|
deba@430
|
889 |
|
deba@430
|
890 |
Graph::Edge e1 = graph.addEdge(n1, n2);
|
deba@430
|
891 |
Graph::Edge e2 = graph.addEdge(n1, n3);
|
deba@430
|
892 |
Graph::Edge e3 = graph.addEdge(n2, n3);
|
deba@430
|
893 |
Graph::Edge e4 = graph.addEdge(n3, n4);
|
deba@430
|
894 |
|
deba@430
|
895 |
edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
|
deba@430
|
896 |
|
deba@430
|
897 |
checkGraphNodeList(adaptor, 4);
|
deba@430
|
898 |
checkGraphArcList(adaptor, 8);
|
deba@430
|
899 |
checkGraphEdgeList(adaptor, 4);
|
deba@430
|
900 |
checkGraphConArcList(adaptor, 8);
|
deba@430
|
901 |
checkGraphConEdgeList(adaptor, 4);
|
deba@430
|
902 |
|
deba@430
|
903 |
checkGraphOutArcList(adaptor, n1, 2);
|
deba@430
|
904 |
checkGraphOutArcList(adaptor, n2, 2);
|
deba@430
|
905 |
checkGraphOutArcList(adaptor, n3, 3);
|
deba@430
|
906 |
checkGraphOutArcList(adaptor, n4, 1);
|
deba@430
|
907 |
|
deba@430
|
908 |
checkGraphInArcList(adaptor, n1, 2);
|
deba@430
|
909 |
checkGraphInArcList(adaptor, n2, 2);
|
deba@430
|
910 |
checkGraphInArcList(adaptor, n3, 3);
|
deba@430
|
911 |
checkGraphInArcList(adaptor, n4, 1);
|
deba@430
|
912 |
|
deba@430
|
913 |
checkGraphIncEdgeList(adaptor, n1, 2);
|
deba@430
|
914 |
checkGraphIncEdgeList(adaptor, n2, 2);
|
deba@430
|
915 |
checkGraphIncEdgeList(adaptor, n3, 3);
|
deba@430
|
916 |
checkGraphIncEdgeList(adaptor, n4, 1);
|
deba@430
|
917 |
|
deba@430
|
918 |
checkNodeIds(adaptor);
|
deba@430
|
919 |
checkArcIds(adaptor);
|
deba@430
|
920 |
checkEdgeIds(adaptor);
|
deba@430
|
921 |
|
deba@430
|
922 |
checkGraphNodeMap(adaptor);
|
deba@430
|
923 |
checkGraphArcMap(adaptor);
|
deba@430
|
924 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
925 |
|
deba@430
|
926 |
edge_filter[e2] = false;
|
deba@430
|
927 |
|
deba@430
|
928 |
checkGraphNodeList(adaptor, 4);
|
deba@430
|
929 |
checkGraphArcList(adaptor, 6);
|
deba@430
|
930 |
checkGraphEdgeList(adaptor, 3);
|
deba@430
|
931 |
checkGraphConArcList(adaptor, 6);
|
deba@430
|
932 |
checkGraphConEdgeList(adaptor, 3);
|
deba@430
|
933 |
|
deba@430
|
934 |
checkGraphOutArcList(adaptor, n1, 1);
|
deba@430
|
935 |
checkGraphOutArcList(adaptor, n2, 2);
|
deba@430
|
936 |
checkGraphOutArcList(adaptor, n3, 2);
|
deba@430
|
937 |
checkGraphOutArcList(adaptor, n4, 1);
|
deba@430
|
938 |
|
deba@430
|
939 |
checkGraphInArcList(adaptor, n1, 1);
|
deba@430
|
940 |
checkGraphInArcList(adaptor, n2, 2);
|
deba@430
|
941 |
checkGraphInArcList(adaptor, n3, 2);
|
deba@430
|
942 |
checkGraphInArcList(adaptor, n4, 1);
|
deba@430
|
943 |
|
deba@430
|
944 |
checkGraphIncEdgeList(adaptor, n1, 1);
|
deba@430
|
945 |
checkGraphIncEdgeList(adaptor, n2, 2);
|
deba@430
|
946 |
checkGraphIncEdgeList(adaptor, n3, 2);
|
deba@430
|
947 |
checkGraphIncEdgeList(adaptor, n4, 1);
|
deba@430
|
948 |
|
deba@430
|
949 |
checkNodeIds(adaptor);
|
deba@430
|
950 |
checkArcIds(adaptor);
|
deba@430
|
951 |
checkEdgeIds(adaptor);
|
deba@430
|
952 |
|
deba@430
|
953 |
checkGraphNodeMap(adaptor);
|
deba@430
|
954 |
checkGraphArcMap(adaptor);
|
deba@430
|
955 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
956 |
|
deba@430
|
957 |
edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
|
deba@430
|
958 |
|
deba@430
|
959 |
checkGraphNodeList(adaptor, 4);
|
deba@430
|
960 |
checkGraphArcList(adaptor, 0);
|
deba@430
|
961 |
checkGraphEdgeList(adaptor, 0);
|
deba@430
|
962 |
checkGraphConArcList(adaptor, 0);
|
deba@430
|
963 |
checkGraphConEdgeList(adaptor, 0);
|
deba@430
|
964 |
|
deba@430
|
965 |
checkNodeIds(adaptor);
|
deba@430
|
966 |
checkArcIds(adaptor);
|
deba@430
|
967 |
checkEdgeIds(adaptor);
|
deba@430
|
968 |
|
deba@430
|
969 |
checkGraphNodeMap(adaptor);
|
deba@430
|
970 |
checkGraphArcMap(adaptor);
|
deba@430
|
971 |
checkGraphEdgeMap(adaptor);
|
deba@430
|
972 |
}
|
deba@430
|
973 |
|
deba@430
|
974 |
void checkDirGraphAdaptor() {
|
deba@430
|
975 |
checkConcept<concepts::Digraph,
|
deba@430
|
976 |
DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
|
deba@430
|
977 |
|
deba@430
|
978 |
typedef ListGraph Graph;
|
deba@430
|
979 |
typedef ListGraph::EdgeMap<bool> DirMap;
|
deba@430
|
980 |
typedef DirGraphAdaptor<Graph> Adaptor;
|
deba@430
|
981 |
|
deba@430
|
982 |
Graph graph;
|
deba@430
|
983 |
DirMap dir(graph, true);
|
deba@430
|
984 |
Adaptor adaptor(graph, dir);
|
deba@430
|
985 |
|
deba@430
|
986 |
Graph::Node n1 = graph.addNode();
|
deba@430
|
987 |
Graph::Node n2 = graph.addNode();
|
deba@430
|
988 |
Graph::Node n3 = graph.addNode();
|
deba@430
|
989 |
|
deba@430
|
990 |
Graph::Edge e1 = graph.addEdge(n1, n2);
|
deba@430
|
991 |
Graph::Edge e2 = graph.addEdge(n1, n3);
|
deba@430
|
992 |
Graph::Edge e3 = graph.addEdge(n2, n3);
|
deba@430
|
993 |
|
deba@430
|
994 |
checkGraphNodeList(adaptor, 3);
|
deba@430
|
995 |
checkGraphArcList(adaptor, 3);
|
deba@430
|
996 |
checkGraphConArcList(adaptor, 3);
|
deba@430
|
997 |
|
deba@430
|
998 |
{
|
deba@430
|
999 |
dir[e1] = true;
|
deba@430
|
1000 |
Adaptor::Node u = adaptor.source(e1);
|
deba@430
|
1001 |
Adaptor::Node v = adaptor.target(e1);
|
deba@430
|
1002 |
|
deba@430
|
1003 |
dir[e1] = false;
|
deba@430
|
1004 |
check (u == adaptor.target(e1), "Wrong dir");
|
deba@430
|
1005 |
check (v == adaptor.source(e1), "Wrong dir");
|
deba@430
|
1006 |
|
deba@430
|
1007 |
check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
|
deba@430
|
1008 |
dir[e1] = n1 == u;
|
deba@430
|
1009 |
}
|
deba@430
|
1010 |
|
deba@430
|
1011 |
{
|
deba@430
|
1012 |
dir[e2] = true;
|
deba@430
|
1013 |
Adaptor::Node u = adaptor.source(e2);
|
deba@430
|
1014 |
Adaptor::Node v = adaptor.target(e2);
|
deba@430
|
1015 |
|
deba@430
|
1016 |
dir[e2] = false;
|
deba@430
|
1017 |
check (u == adaptor.target(e2), "Wrong dir");
|
deba@430
|
1018 |
check (v == adaptor.source(e2), "Wrong dir");
|
deba@430
|
1019 |
|
deba@430
|
1020 |
check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
|
deba@430
|
1021 |
dir[e2] = n3 == u;
|
deba@430
|
1022 |
}
|
deba@430
|
1023 |
|
deba@430
|
1024 |
{
|
deba@430
|
1025 |
dir[e3] = true;
|
deba@430
|
1026 |
Adaptor::Node u = adaptor.source(e3);
|
deba@430
|
1027 |
Adaptor::Node v = adaptor.target(e3);
|
deba@430
|
1028 |
|
deba@430
|
1029 |
dir[e3] = false;
|
deba@430
|
1030 |
check (u == adaptor.target(e3), "Wrong dir");
|
deba@430
|
1031 |
check (v == adaptor.source(e3), "Wrong dir");
|
deba@430
|
1032 |
|
deba@430
|
1033 |
check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
|
deba@430
|
1034 |
dir[e3] = n2 == u;
|
deba@430
|
1035 |
}
|
deba@430
|
1036 |
|
deba@430
|
1037 |
checkGraphOutArcList(adaptor, n1, 1);
|
deba@430
|
1038 |
checkGraphOutArcList(adaptor, n2, 1);
|
deba@430
|
1039 |
checkGraphOutArcList(adaptor, n3, 1);
|
deba@430
|
1040 |
|
deba@430
|
1041 |
checkGraphInArcList(adaptor, n1, 1);
|
deba@430
|
1042 |
checkGraphInArcList(adaptor, n2, 1);
|
deba@430
|
1043 |
checkGraphInArcList(adaptor, n3, 1);
|
deba@430
|
1044 |
|
deba@430
|
1045 |
checkNodeIds(adaptor);
|
deba@430
|
1046 |
checkArcIds(adaptor);
|
deba@430
|
1047 |
|
deba@430
|
1048 |
checkGraphNodeMap(adaptor);
|
deba@430
|
1049 |
checkGraphArcMap(adaptor);
|
deba@430
|
1050 |
|
deba@430
|
1051 |
}
|
deba@430
|
1052 |
|
deba@430
|
1053 |
|
deba@430
|
1054 |
int main(int, const char **) {
|
deba@430
|
1055 |
|
deba@430
|
1056 |
checkDigraphAdaptor();
|
deba@430
|
1057 |
checkRevDigraphAdaptor();
|
deba@430
|
1058 |
checkSubDigraphAdaptor();
|
deba@430
|
1059 |
checkNodeSubDigraphAdaptor();
|
deba@430
|
1060 |
checkArcSubDigraphAdaptor();
|
deba@430
|
1061 |
checkUndirDigraphAdaptor();
|
deba@430
|
1062 |
checkResDigraphAdaptor();
|
deba@430
|
1063 |
checkSplitDigraphAdaptor();
|
deba@430
|
1064 |
|
deba@430
|
1065 |
checkGraphAdaptor();
|
deba@430
|
1066 |
checkSubGraphAdaptor();
|
deba@430
|
1067 |
checkNodeSubGraphAdaptor();
|
deba@430
|
1068 |
checkEdgeSubGraphAdaptor();
|
deba@430
|
1069 |
checkDirGraphAdaptor();
|
deba@430
|
1070 |
|
deba@430
|
1071 |
return 0;
|
deba@430
|
1072 |
}
|