1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
22 #include <lemon/concepts/digraph.h>
23 #include <lemon/concepts/graph.h>
24 #include <lemon/concept_check.h>
26 #include <lemon/list_graph.h>
28 #include <lemon/edge_set.h>
30 #include "graph_test.h"
31 #include "test_tools.h"
33 using namespace lemon;
35 void checkSmartArcSet() {
36 checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();
38 typedef ListDigraph Digraph;
39 typedef SmartArcSet<Digraph> ArcSet;
43 n1 = digraph.addNode(),
44 n2 = digraph.addNode();
46 Digraph::Arc ga1 = digraph.addArc(n1, n2);
48 ArcSet arc_set(digraph);
50 Digraph::Arc ga2 = digraph.addArc(n2, n1);
52 checkGraphNodeList(arc_set, 2);
53 checkGraphArcList(arc_set, 0);
56 n3 = digraph.addNode();
57 checkGraphNodeList(arc_set, 3);
58 checkGraphArcList(arc_set, 0);
60 ArcSet::Arc a1 = arc_set.addArc(n1, n2);
61 check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
62 checkGraphNodeList(arc_set, 3);
63 checkGraphArcList(arc_set, 1);
65 checkGraphOutArcList(arc_set, n1, 1);
66 checkGraphOutArcList(arc_set, n2, 0);
67 checkGraphOutArcList(arc_set, n3, 0);
69 checkGraphInArcList(arc_set, n1, 0);
70 checkGraphInArcList(arc_set, n2, 1);
71 checkGraphInArcList(arc_set, n3, 0);
73 checkGraphConArcList(arc_set, 1);
75 ArcSet::Arc a2 = arc_set.addArc(n2, n1),
76 a3 = arc_set.addArc(n2, n3),
77 a4 = arc_set.addArc(n2, n3);
78 checkGraphNodeList(arc_set, 3);
79 checkGraphArcList(arc_set, 4);
81 checkGraphOutArcList(arc_set, n1, 1);
82 checkGraphOutArcList(arc_set, n2, 3);
83 checkGraphOutArcList(arc_set, n3, 0);
85 checkGraphInArcList(arc_set, n1, 1);
86 checkGraphInArcList(arc_set, n2, 1);
87 checkGraphInArcList(arc_set, n3, 2);
89 checkGraphConArcList(arc_set, 4);
91 checkNodeIds(arc_set);
93 checkGraphNodeMap(arc_set);
94 checkGraphArcMap(arc_set);
96 check(arc_set.valid(), "Wrong validity");
98 check(!arc_set.valid(), "Wrong validity");
101 void checkListArcSet() {
102 checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();
104 typedef ListDigraph Digraph;
105 typedef ListArcSet<Digraph> ArcSet;
109 n1 = digraph.addNode(),
110 n2 = digraph.addNode();
112 Digraph::Arc ga1 = digraph.addArc(n1, n2);
114 ArcSet arc_set(digraph);
116 Digraph::Arc ga2 = digraph.addArc(n2, n1);
118 checkGraphNodeList(arc_set, 2);
119 checkGraphArcList(arc_set, 0);
122 n3 = digraph.addNode();
123 checkGraphNodeList(arc_set, 3);
124 checkGraphArcList(arc_set, 0);
126 ArcSet::Arc a1 = arc_set.addArc(n1, n2);
127 check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
128 checkGraphNodeList(arc_set, 3);
129 checkGraphArcList(arc_set, 1);
131 checkGraphOutArcList(arc_set, n1, 1);
132 checkGraphOutArcList(arc_set, n2, 0);
133 checkGraphOutArcList(arc_set, n3, 0);
135 checkGraphInArcList(arc_set, n1, 0);
136 checkGraphInArcList(arc_set, n2, 1);
137 checkGraphInArcList(arc_set, n3, 0);
139 checkGraphConArcList(arc_set, 1);
141 ArcSet::Arc a2 = arc_set.addArc(n2, n1),
142 a3 = arc_set.addArc(n2, n3),
143 a4 = arc_set.addArc(n2, n3);
144 checkGraphNodeList(arc_set, 3);
145 checkGraphArcList(arc_set, 4);
147 checkGraphOutArcList(arc_set, n1, 1);
148 checkGraphOutArcList(arc_set, n2, 3);
149 checkGraphOutArcList(arc_set, n3, 0);
151 checkGraphInArcList(arc_set, n1, 1);
152 checkGraphInArcList(arc_set, n2, 1);
153 checkGraphInArcList(arc_set, n3, 2);
155 checkGraphConArcList(arc_set, 4);
157 checkNodeIds(arc_set);
158 checkArcIds(arc_set);
159 checkGraphNodeMap(arc_set);
160 checkGraphArcMap(arc_set);
164 checkGraphNodeList(arc_set, 2);
165 checkGraphArcList(arc_set, 2);
167 checkGraphOutArcList(arc_set, n2, 2);
168 checkGraphOutArcList(arc_set, n3, 0);
170 checkGraphInArcList(arc_set, n2, 0);
171 checkGraphInArcList(arc_set, n3, 2);
173 checkNodeIds(arc_set);
174 checkArcIds(arc_set);
175 checkGraphNodeMap(arc_set);
176 checkGraphArcMap(arc_set);
178 checkGraphConArcList(arc_set, 2);
181 void checkSmartEdgeSet() {
182 checkConcept<concepts::Digraph, SmartEdgeSet<ListDigraph> >();
184 typedef ListDigraph Digraph;
185 typedef SmartEdgeSet<Digraph> EdgeSet;
189 n1 = digraph.addNode(),
190 n2 = digraph.addNode();
192 Digraph::Arc ga1 = digraph.addArc(n1, n2);
194 EdgeSet edge_set(digraph);
196 Digraph::Arc ga2 = digraph.addArc(n2, n1);
198 checkGraphNodeList(edge_set, 2);
199 checkGraphArcList(edge_set, 0);
200 checkGraphEdgeList(edge_set, 0);
203 n3 = digraph.addNode();
204 checkGraphNodeList(edge_set, 3);
205 checkGraphArcList(edge_set, 0);
206 checkGraphEdgeList(edge_set, 0);
208 EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
209 check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
210 (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
211 checkGraphNodeList(edge_set, 3);
212 checkGraphArcList(edge_set, 2);
213 checkGraphEdgeList(edge_set, 1);
215 checkGraphOutArcList(edge_set, n1, 1);
216 checkGraphOutArcList(edge_set, n2, 1);
217 checkGraphOutArcList(edge_set, n3, 0);
219 checkGraphInArcList(edge_set, n1, 1);
220 checkGraphInArcList(edge_set, n2, 1);
221 checkGraphInArcList(edge_set, n3, 0);
223 checkGraphIncEdgeList(edge_set, n1, 1);
224 checkGraphIncEdgeList(edge_set, n2, 1);
225 checkGraphIncEdgeList(edge_set, n3, 0);
227 checkGraphConEdgeList(edge_set, 1);
228 checkGraphConArcList(edge_set, 2);
230 EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
231 e3 = edge_set.addEdge(n2, n3),
232 e4 = edge_set.addEdge(n2, n3);
233 checkGraphNodeList(edge_set, 3);
234 checkGraphEdgeList(edge_set, 4);
236 checkGraphOutArcList(edge_set, n1, 2);
237 checkGraphOutArcList(edge_set, n2, 4);
238 checkGraphOutArcList(edge_set, n3, 2);
240 checkGraphInArcList(edge_set, n1, 2);
241 checkGraphInArcList(edge_set, n2, 4);
242 checkGraphInArcList(edge_set, n3, 2);
244 checkGraphIncEdgeList(edge_set, n1, 2);
245 checkGraphIncEdgeList(edge_set, n2, 4);
246 checkGraphIncEdgeList(edge_set, n3, 2);
248 checkGraphConEdgeList(edge_set, 4);
249 checkGraphConArcList(edge_set, 8);
251 checkArcDirections(edge_set);
253 checkNodeIds(edge_set);
254 checkArcIds(edge_set);
255 checkEdgeIds(edge_set);
256 checkGraphNodeMap(edge_set);
257 checkGraphArcMap(edge_set);
258 checkGraphEdgeMap(edge_set);
260 check(edge_set.valid(), "Wrong validity");
262 check(!edge_set.valid(), "Wrong validity");
265 void checkListEdgeSet() {
266 checkConcept<concepts::Digraph, ListEdgeSet<ListDigraph> >();
268 typedef ListDigraph Digraph;
269 typedef ListEdgeSet<Digraph> EdgeSet;
273 n1 = digraph.addNode(),
274 n2 = digraph.addNode();
276 Digraph::Arc ga1 = digraph.addArc(n1, n2);
278 EdgeSet edge_set(digraph);
280 Digraph::Arc ga2 = digraph.addArc(n2, n1);
282 checkGraphNodeList(edge_set, 2);
283 checkGraphArcList(edge_set, 0);
284 checkGraphEdgeList(edge_set, 0);
287 n3 = digraph.addNode();
288 checkGraphNodeList(edge_set, 3);
289 checkGraphArcList(edge_set, 0);
290 checkGraphEdgeList(edge_set, 0);
292 EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
293 check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
294 (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
295 checkGraphNodeList(edge_set, 3);
296 checkGraphArcList(edge_set, 2);
297 checkGraphEdgeList(edge_set, 1);
299 checkGraphOutArcList(edge_set, n1, 1);
300 checkGraphOutArcList(edge_set, n2, 1);
301 checkGraphOutArcList(edge_set, n3, 0);
303 checkGraphInArcList(edge_set, n1, 1);
304 checkGraphInArcList(edge_set, n2, 1);
305 checkGraphInArcList(edge_set, n3, 0);
307 checkGraphIncEdgeList(edge_set, n1, 1);
308 checkGraphIncEdgeList(edge_set, n2, 1);
309 checkGraphIncEdgeList(edge_set, n3, 0);
311 checkGraphConEdgeList(edge_set, 1);
312 checkGraphConArcList(edge_set, 2);
314 EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
315 e3 = edge_set.addEdge(n2, n3),
316 e4 = edge_set.addEdge(n2, n3);
317 checkGraphNodeList(edge_set, 3);
318 checkGraphEdgeList(edge_set, 4);
320 checkGraphOutArcList(edge_set, n1, 2);
321 checkGraphOutArcList(edge_set, n2, 4);
322 checkGraphOutArcList(edge_set, n3, 2);
324 checkGraphInArcList(edge_set, n1, 2);
325 checkGraphInArcList(edge_set, n2, 4);
326 checkGraphInArcList(edge_set, n3, 2);
328 checkGraphIncEdgeList(edge_set, n1, 2);
329 checkGraphIncEdgeList(edge_set, n2, 4);
330 checkGraphIncEdgeList(edge_set, n3, 2);
332 checkGraphConEdgeList(edge_set, 4);
333 checkGraphConArcList(edge_set, 8);
335 checkArcDirections(edge_set);
337 checkNodeIds(edge_set);
338 checkArcIds(edge_set);
339 checkEdgeIds(edge_set);
340 checkGraphNodeMap(edge_set);
341 checkGraphArcMap(edge_set);
342 checkGraphEdgeMap(edge_set);
346 checkGraphNodeList(edge_set, 2);
347 checkGraphArcList(edge_set, 4);
348 checkGraphEdgeList(edge_set, 2);
350 checkGraphOutArcList(edge_set, n2, 2);
351 checkGraphOutArcList(edge_set, n3, 2);
353 checkGraphInArcList(edge_set, n2, 2);
354 checkGraphInArcList(edge_set, n3, 2);
356 checkGraphIncEdgeList(edge_set, n2, 2);
357 checkGraphIncEdgeList(edge_set, n3, 2);
359 checkNodeIds(edge_set);
360 checkArcIds(edge_set);
361 checkEdgeIds(edge_set);
362 checkGraphNodeMap(edge_set);
363 checkGraphArcMap(edge_set);
364 checkGraphEdgeMap(edge_set);
366 checkGraphConEdgeList(edge_set, 2);
367 checkGraphConArcList(edge_set, 4);