1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
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
19 #include <lemon/concepts/graph.h>
20 #include <lemon/list_graph.h>
21 #include <lemon/smart_graph.h>
22 #include <lemon/full_graph.h>
23 #include <lemon/grid_graph.h>
24 #include <lemon/hypercube_graph.h>
26 #include "test_tools.h"
27 #include "graph_test.h"
29 using namespace lemon;
30 using namespace lemon::concepts;
32 template <class Graph>
33 void checkGraphBuild() {
34 TEMPLATE_GRAPH_TYPEDEFS(Graph);
37 checkGraphNodeList(G, 0);
38 checkGraphEdgeList(G, 0);
39 checkGraphArcList(G, 0);
48 checkGraphNodeList(G, 3);
49 checkGraphEdgeList(G, 0);
50 checkGraphArcList(G, 0);
52 Edge e1 = G.addEdge(n1, n2);
53 check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
56 checkGraphNodeList(G, 3);
57 checkGraphEdgeList(G, 1);
58 checkGraphArcList(G, 2);
60 checkGraphIncEdgeArcLists(G, n1, 1);
61 checkGraphIncEdgeArcLists(G, n2, 1);
62 checkGraphIncEdgeArcLists(G, n3, 0);
64 checkGraphConEdgeList(G, 1);
65 checkGraphConArcList(G, 2);
67 Edge e2 = G.addEdge(n2, n1),
68 e3 = G.addEdge(n2, n3);
70 checkGraphNodeList(G, 3);
71 checkGraphEdgeList(G, 3);
72 checkGraphArcList(G, 6);
74 checkGraphIncEdgeArcLists(G, n1, 2);
75 checkGraphIncEdgeArcLists(G, n2, 3);
76 checkGraphIncEdgeArcLists(G, n3, 1);
78 checkGraphConEdgeList(G, 3);
79 checkGraphConArcList(G, 6);
81 checkArcDirections(G);
91 template <class Graph>
92 void checkGraphAlter() {
93 TEMPLATE_GRAPH_TYPEDEFS(Graph);
96 Node n1 = G.addNode(), n2 = G.addNode(),
97 n3 = G.addNode(), n4 = G.addNode();
98 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
99 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
100 e5 = G.addEdge(n4, n3);
102 checkGraphNodeList(G, 4);
103 checkGraphEdgeList(G, 5);
104 checkGraphArcList(G, 10);
106 // Check changeU() and changeV()
113 checkGraphNodeList(G, 4);
114 checkGraphEdgeList(G, 5);
115 checkGraphArcList(G, 10);
117 checkGraphIncEdgeArcLists(G, n1, 3);
118 checkGraphIncEdgeArcLists(G, n2, 2);
119 checkGraphIncEdgeArcLists(G, n3, 3);
120 checkGraphIncEdgeArcLists(G, n4, 2);
122 checkGraphConEdgeList(G, 5);
123 checkGraphConArcList(G, 10);
131 checkGraphNodeList(G, 4);
132 checkGraphEdgeList(G, 5);
133 checkGraphArcList(G, 10);
135 checkGraphIncEdgeArcLists(G, n1, 2);
136 checkGraphIncEdgeArcLists(G, n2, 3);
137 checkGraphIncEdgeArcLists(G, n3, 3);
138 checkGraphIncEdgeArcLists(G, n4, 2);
140 checkGraphConEdgeList(G, 5);
141 checkGraphConArcList(G, 10);
144 G.contract(n1, n4, false);
146 checkGraphNodeList(G, 3);
147 checkGraphEdgeList(G, 5);
148 checkGraphArcList(G, 10);
150 checkGraphIncEdgeArcLists(G, n1, 4);
151 checkGraphIncEdgeArcLists(G, n2, 3);
152 checkGraphIncEdgeArcLists(G, n3, 3);
154 checkGraphConEdgeList(G, 5);
155 checkGraphConArcList(G, 10);
159 checkGraphNodeList(G, 2);
160 checkGraphEdgeList(G, 3);
161 checkGraphArcList(G, 6);
163 checkGraphIncEdgeArcLists(G, n1, 4);
164 checkGraphIncEdgeArcLists(G, n2, 2);
166 checkGraphConEdgeList(G, 3);
167 checkGraphConArcList(G, 6);
170 template <class Graph>
171 void checkGraphErase() {
172 TEMPLATE_GRAPH_TYPEDEFS(Graph);
175 Node n1 = G.addNode(), n2 = G.addNode(),
176 n3 = G.addNode(), n4 = G.addNode();
177 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
178 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
179 e5 = G.addEdge(n4, n3);
181 // Check edge deletion
184 checkGraphNodeList(G, 4);
185 checkGraphEdgeList(G, 4);
186 checkGraphArcList(G, 8);
188 checkGraphIncEdgeArcLists(G, n1, 2);
189 checkGraphIncEdgeArcLists(G, n2, 2);
190 checkGraphIncEdgeArcLists(G, n3, 2);
191 checkGraphIncEdgeArcLists(G, n4, 2);
193 checkGraphConEdgeList(G, 4);
194 checkGraphConArcList(G, 8);
196 // Check node deletion
199 checkGraphNodeList(G, 3);
200 checkGraphEdgeList(G, 2);
201 checkGraphArcList(G, 4);
203 checkGraphIncEdgeArcLists(G, n1, 2);
204 checkGraphIncEdgeArcLists(G, n2, 1);
205 checkGraphIncEdgeArcLists(G, n4, 1);
207 checkGraphConEdgeList(G, 2);
208 checkGraphConArcList(G, 4);
212 template <class Graph>
213 void checkGraphSnapshot() {
214 TEMPLATE_GRAPH_TYPEDEFS(Graph);
217 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
218 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
219 e3 = G.addEdge(n2, n3);
221 checkGraphNodeList(G, 3);
222 checkGraphEdgeList(G, 3);
223 checkGraphArcList(G, 6);
225 typename Graph::Snapshot snapshot(G);
227 Node n = G.addNode();
232 checkGraphNodeList(G, 4);
233 checkGraphEdgeList(G, 6);
234 checkGraphArcList(G, 12);
238 checkGraphNodeList(G, 3);
239 checkGraphEdgeList(G, 3);
240 checkGraphArcList(G, 6);
242 checkGraphIncEdgeArcLists(G, n1, 2);
243 checkGraphIncEdgeArcLists(G, n2, 3);
244 checkGraphIncEdgeArcLists(G, n3, 1);
246 checkGraphConEdgeList(G, 3);
247 checkGraphConArcList(G, 6);
252 checkGraphNodeMap(G);
253 checkGraphEdgeMap(G);
259 G.addEdge(G.addNode(), G.addNode());
263 checkGraphNodeList(G, 4);
264 checkGraphEdgeList(G, 3);
265 checkGraphArcList(G, 6);
268 void checkFullGraph(int num) {
269 typedef FullGraph Graph;
270 GRAPH_TYPEDEFS(Graph);
273 checkGraphNodeList(G, num);
274 checkGraphEdgeList(G, num * (num - 1) / 2);
276 for (NodeIt n(G); n != INVALID; ++n) {
277 checkGraphOutArcList(G, n, num - 1);
278 checkGraphInArcList(G, n, num - 1);
279 checkGraphIncEdgeList(G, n, num - 1);
282 checkGraphConArcList(G, num * (num - 1));
283 checkGraphConEdgeList(G, num * (num - 1) / 2);
285 checkArcDirections(G);
290 checkGraphNodeMap(G);
292 checkGraphEdgeMap(G);
295 for (int i = 0; i < G.nodeNum(); ++i) {
296 check(G.index(G(i)) == i, "Wrong index");
299 for (NodeIt u(G); u != INVALID; ++u) {
300 for (NodeIt v(G); v != INVALID; ++v) {
301 Edge e = G.edge(u, v);
304 check(e == INVALID, "Wrong edge lookup");
305 check(a == INVALID, "Wrong arc lookup");
307 check((G.u(e) == u && G.v(e) == v) ||
308 (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
309 check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
315 void checkConcepts() {
316 { // Checking graph components
317 checkConcept<BaseGraphComponent, BaseGraphComponent >();
319 checkConcept<IDableGraphComponent<>,
320 IDableGraphComponent<> >();
322 checkConcept<IterableGraphComponent<>,
323 IterableGraphComponent<> >();
325 checkConcept<MappableGraphComponent<>,
326 MappableGraphComponent<> >();
328 { // Checking skeleton graph
329 checkConcept<Graph, Graph>();
331 { // Checking ListGraph
332 checkConcept<Graph, ListGraph>();
333 checkConcept<AlterableGraphComponent<>, ListGraph>();
334 checkConcept<ExtendableGraphComponent<>, ListGraph>();
335 checkConcept<ClearableGraphComponent<>, ListGraph>();
336 checkConcept<ErasableGraphComponent<>, ListGraph>();
338 { // Checking SmartGraph
339 checkConcept<Graph, SmartGraph>();
340 checkConcept<AlterableGraphComponent<>, SmartGraph>();
341 checkConcept<ExtendableGraphComponent<>, SmartGraph>();
342 checkConcept<ClearableGraphComponent<>, SmartGraph>();
344 { // Checking FullGraph
345 checkConcept<Graph, FullGraph>();
347 { // Checking GridGraph
348 checkConcept<Graph, GridGraph>();
350 { // Checking HypercubeGraph
351 checkConcept<Graph, HypercubeGraph>();
355 template <typename Graph>
356 void checkGraphValidity() {
357 TEMPLATE_GRAPH_TYPEDEFS(Graph);
366 e1 = g.addEdge(n1, n2),
367 e2 = g.addEdge(n2, n3);
369 check(g.valid(n1), "Wrong validity check");
370 check(g.valid(e1), "Wrong validity check");
371 check(g.valid(g.direct(e1, true)), "Wrong validity check");
373 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
374 check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
375 check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
378 template <typename Graph>
379 void checkGraphValidityErase() {
380 TEMPLATE_GRAPH_TYPEDEFS(Graph);
389 e1 = g.addEdge(n1, n2),
390 e2 = g.addEdge(n2, n3);
392 check(g.valid(n1), "Wrong validity check");
393 check(g.valid(e1), "Wrong validity check");
394 check(g.valid(g.direct(e1, true)), "Wrong validity check");
398 check(!g.valid(n1), "Wrong validity check");
399 check(g.valid(n2), "Wrong validity check");
400 check(g.valid(n3), "Wrong validity check");
401 check(!g.valid(e1), "Wrong validity check");
402 check(g.valid(e2), "Wrong validity check");
404 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
405 check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
406 check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
409 void checkGridGraph(int width, int height) {
410 typedef GridGraph Graph;
411 GRAPH_TYPEDEFS(Graph);
412 Graph G(width, height);
414 check(G.width() == width, "Wrong column number");
415 check(G.height() == height, "Wrong row number");
417 for (int i = 0; i < width; ++i) {
418 for (int j = 0; j < height; ++j) {
419 check(G.col(G(i, j)) == i, "Wrong column");
420 check(G.row(G(i, j)) == j, "Wrong row");
421 check(G.pos(G(i, j)).x == i, "Wrong column");
422 check(G.pos(G(i, j)).y == j, "Wrong row");
426 for (int j = 0; j < height; ++j) {
427 for (int i = 0; i < width - 1; ++i) {
428 check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
429 check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
431 check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
434 for (int j = 0; j < height; ++j) {
435 for (int i = 1; i < width; ++i) {
436 check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
437 check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
439 check(G.left(G(0, j)) == INVALID, "Wrong left");
442 for (int i = 0; i < width; ++i) {
443 for (int j = 0; j < height - 1; ++j) {
444 check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
445 check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
447 check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
450 for (int i = 0; i < width; ++i) {
451 for (int j = 1; j < height; ++j) {
452 check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
453 check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
455 check(G.down(G(i, 0)) == INVALID, "Wrong down");
458 checkGraphNodeList(G, width * height);
459 checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
460 checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
462 for (NodeIt n(G); n != INVALID; ++n) {
464 if (G.col(n) == 0) --nb;
465 if (G.col(n) == width - 1) --nb;
466 if (G.row(n) == 0) --nb;
467 if (G.row(n) == height - 1) --nb;
469 checkGraphOutArcList(G, n, nb);
470 checkGraphInArcList(G, n, nb);
471 checkGraphIncEdgeList(G, n, nb);
474 checkArcDirections(G);
476 checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
477 checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
482 checkGraphNodeMap(G);
484 checkGraphEdgeMap(G);
488 void checkHypercubeGraph(int dim) {
489 GRAPH_TYPEDEFS(HypercubeGraph);
491 HypercubeGraph G(dim);
492 checkGraphNodeList(G, 1 << dim);
493 checkGraphEdgeList(G, dim * (1 << (dim-1)));
494 checkGraphArcList(G, dim * (1 << dim));
496 Node n = G.nodeFromId(dim);
498 for (NodeIt n(G); n != INVALID; ++n) {
499 checkGraphIncEdgeList(G, n, dim);
500 for (IncEdgeIt e(G, n); e != INVALID; ++e) {
501 check( (G.u(e) == n &&
502 G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
504 G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
505 "Wrong edge or wrong dimension");
508 checkGraphOutArcList(G, n, dim);
509 for (OutArcIt a(G, n); a != INVALID; ++a) {
510 check(G.source(a) == n &&
511 G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
512 "Wrong arc or wrong dimension");
515 checkGraphInArcList(G, n, dim);
516 for (InArcIt a(G, n); a != INVALID; ++a) {
517 check(G.target(a) == n &&
518 G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
519 "Wrong arc or wrong dimension");
523 checkGraphConArcList(G, (1 << dim) * dim);
524 checkGraphConEdgeList(G, dim * (1 << (dim-1)));
526 checkArcDirections(G);
531 checkGraphNodeMap(G);
533 checkGraphEdgeMap(G);
537 { // Checking ListGraph
538 checkGraphBuild<ListGraph>();
539 checkGraphAlter<ListGraph>();
540 checkGraphErase<ListGraph>();
541 checkGraphSnapshot<ListGraph>();
542 checkGraphValidityErase<ListGraph>();
544 { // Checking SmartGraph
545 checkGraphBuild<SmartGraph>();
546 checkGraphSnapshot<SmartGraph>();
547 checkGraphValidity<SmartGraph>();
549 { // Checking FullGraph
553 { // Checking GridGraph
554 checkGridGraph(5, 8);
555 checkGridGraph(8, 5);
556 checkGridGraph(5, 5);
557 checkGridGraph(0, 0);
558 checkGridGraph(1, 1);
560 { // Checking HypercubeGraph
561 checkHypercubeGraph(1);
562 checkHypercubeGraph(2);
563 checkHypercubeGraph(3);
564 checkHypercubeGraph(4);