COIN-OR::LEMON - Graph Library

source: lemon/test/graph_test.cc @ 956:141f9c0db4a3

Last change on this file since 956:141f9c0db4a3 was 956:141f9c0db4a3, checked in by Alpar Juttner <alpar@…>, 15 years ago

Unify the sources (#339)

File size: 14.7 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
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>
25
26#include "test_tools.h"
27#include "graph_test.h"
28
29using namespace lemon;
30using namespace lemon::concepts;
31
32template <class Graph>
33void checkGraphBuild() {
34  TEMPLATE_GRAPH_TYPEDEFS(Graph);
35
36  Graph G;
37  checkGraphNodeList(G, 0);
38  checkGraphEdgeList(G, 0);
39  checkGraphArcList(G, 0);
40
41  G.reserveNode(3);
42  G.reserveEdge(3);
43
44  Node
45    n1 = G.addNode(),
46    n2 = G.addNode(),
47    n3 = G.addNode();
48  checkGraphNodeList(G, 3);
49  checkGraphEdgeList(G, 0);
50  checkGraphArcList(G, 0);
51
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),
54        "Wrong edge");
55
56  checkGraphNodeList(G, 3);
57  checkGraphEdgeList(G, 1);
58  checkGraphArcList(G, 2);
59
60  checkGraphIncEdgeArcLists(G, n1, 1);
61  checkGraphIncEdgeArcLists(G, n2, 1);
62  checkGraphIncEdgeArcLists(G, n3, 0);
63
64  checkGraphConEdgeList(G, 1);
65  checkGraphConArcList(G, 2);
66
67  Edge e2 = G.addEdge(n2, n1),
68       e3 = G.addEdge(n2, n3);
69
70  checkGraphNodeList(G, 3);
71  checkGraphEdgeList(G, 3);
72  checkGraphArcList(G, 6);
73
74  checkGraphIncEdgeArcLists(G, n1, 2);
75  checkGraphIncEdgeArcLists(G, n2, 3);
76  checkGraphIncEdgeArcLists(G, n3, 1);
77
78  checkGraphConEdgeList(G, 3);
79  checkGraphConArcList(G, 6);
80
81  checkArcDirections(G);
82
83  checkNodeIds(G);
84  checkArcIds(G);
85  checkEdgeIds(G);
86  checkGraphNodeMap(G);
87  checkGraphArcMap(G);
88  checkGraphEdgeMap(G);
89}
90
91template <class Graph>
92void checkGraphAlter() {
93  TEMPLATE_GRAPH_TYPEDEFS(Graph);
94
95  Graph G;
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);
101
102  checkGraphNodeList(G, 4);
103  checkGraphEdgeList(G, 5);
104  checkGraphArcList(G, 10);
105
106  // Check changeU() and changeV()
107  if (G.u(e2) == n2) {
108    G.changeU(e2, n3);
109  } else {
110    G.changeV(e2, n3);
111  }
112
113  checkGraphNodeList(G, 4);
114  checkGraphEdgeList(G, 5);
115  checkGraphArcList(G, 10);
116
117  checkGraphIncEdgeArcLists(G, n1, 3);
118  checkGraphIncEdgeArcLists(G, n2, 2);
119  checkGraphIncEdgeArcLists(G, n3, 3);
120  checkGraphIncEdgeArcLists(G, n4, 2);
121
122  checkGraphConEdgeList(G, 5);
123  checkGraphConArcList(G, 10);
124
125  if (G.u(e2) == n1) {
126    G.changeU(e2, n2);
127  } else {
128    G.changeV(e2, n2);
129  }
130
131  checkGraphNodeList(G, 4);
132  checkGraphEdgeList(G, 5);
133  checkGraphArcList(G, 10);
134
135  checkGraphIncEdgeArcLists(G, n1, 2);
136  checkGraphIncEdgeArcLists(G, n2, 3);
137  checkGraphIncEdgeArcLists(G, n3, 3);
138  checkGraphIncEdgeArcLists(G, n4, 2);
139
140  checkGraphConEdgeList(G, 5);
141  checkGraphConArcList(G, 10);
142
143  // Check contract()
144  G.contract(n1, n4, false);
145
146  checkGraphNodeList(G, 3);
147  checkGraphEdgeList(G, 5);
148  checkGraphArcList(G, 10);
149
150  checkGraphIncEdgeArcLists(G, n1, 4);
151  checkGraphIncEdgeArcLists(G, n2, 3);
152  checkGraphIncEdgeArcLists(G, n3, 3);
153
154  checkGraphConEdgeList(G, 5);
155  checkGraphConArcList(G, 10);
156
157  G.contract(n2, n3);
158
159  checkGraphNodeList(G, 2);
160  checkGraphEdgeList(G, 3);
161  checkGraphArcList(G, 6);
162
163  checkGraphIncEdgeArcLists(G, n1, 4);
164  checkGraphIncEdgeArcLists(G, n2, 2);
165
166  checkGraphConEdgeList(G, 3);
167  checkGraphConArcList(G, 6);
168}
169
170template <class Graph>
171void checkGraphErase() {
172  TEMPLATE_GRAPH_TYPEDEFS(Graph);
173
174  Graph G;
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);
180
181  // Check edge deletion
182  G.erase(e2);
183
184  checkGraphNodeList(G, 4);
185  checkGraphEdgeList(G, 4);
186  checkGraphArcList(G, 8);
187
188  checkGraphIncEdgeArcLists(G, n1, 2);
189  checkGraphIncEdgeArcLists(G, n2, 2);
190  checkGraphIncEdgeArcLists(G, n3, 2);
191  checkGraphIncEdgeArcLists(G, n4, 2);
192
193  checkGraphConEdgeList(G, 4);
194  checkGraphConArcList(G, 8);
195
196  // Check node deletion
197  G.erase(n3);
198
199  checkGraphNodeList(G, 3);
200  checkGraphEdgeList(G, 2);
201  checkGraphArcList(G, 4);
202
203  checkGraphIncEdgeArcLists(G, n1, 2);
204  checkGraphIncEdgeArcLists(G, n2, 1);
205  checkGraphIncEdgeArcLists(G, n4, 1);
206
207  checkGraphConEdgeList(G, 2);
208  checkGraphConArcList(G, 4);
209}
210
211
212template <class Graph>
213void checkGraphSnapshot() {
214  TEMPLATE_GRAPH_TYPEDEFS(Graph);
215
216  Graph G;
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);
220
221  checkGraphNodeList(G, 3);
222  checkGraphEdgeList(G, 3);
223  checkGraphArcList(G, 6);
224
225  typename Graph::Snapshot snapshot(G);
226
227  Node n = G.addNode();
228  G.addEdge(n3, n);
229  G.addEdge(n, n3);
230  G.addEdge(n3, n2);
231
232  checkGraphNodeList(G, 4);
233  checkGraphEdgeList(G, 6);
234  checkGraphArcList(G, 12);
235
236  snapshot.restore();
237
238  checkGraphNodeList(G, 3);
239  checkGraphEdgeList(G, 3);
240  checkGraphArcList(G, 6);
241
242  checkGraphIncEdgeArcLists(G, n1, 2);
243  checkGraphIncEdgeArcLists(G, n2, 3);
244  checkGraphIncEdgeArcLists(G, n3, 1);
245
246  checkGraphConEdgeList(G, 3);
247  checkGraphConArcList(G, 6);
248
249  checkNodeIds(G);
250  checkEdgeIds(G);
251  checkArcIds(G);
252  checkGraphNodeMap(G);
253  checkGraphEdgeMap(G);
254  checkGraphArcMap(G);
255
256  G.addNode();
257  snapshot.save(G);
258
259  G.addEdge(G.addNode(), G.addNode());
260
261  snapshot.restore();
262  snapshot.save(G);
263
264  checkGraphNodeList(G, 4);
265  checkGraphEdgeList(G, 3);
266  checkGraphArcList(G, 6);
267
268  G.addEdge(G.addNode(), G.addNode());
269
270  snapshot.restore();
271
272  checkGraphNodeList(G, 4);
273  checkGraphEdgeList(G, 3);
274  checkGraphArcList(G, 6);
275}
276
277void checkFullGraph(int num) {
278  typedef FullGraph Graph;
279  GRAPH_TYPEDEFS(Graph);
280
281  Graph G(num);
282  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
283        "Wrong size");
284
285  G.resize(num);
286  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
287        "Wrong size");
288
289  checkGraphNodeList(G, num);
290  checkGraphEdgeList(G, num * (num - 1) / 2);
291
292  for (NodeIt n(G); n != INVALID; ++n) {
293    checkGraphOutArcList(G, n, num - 1);
294    checkGraphInArcList(G, n, num - 1);
295    checkGraphIncEdgeList(G, n, num - 1);
296  }
297
298  checkGraphConArcList(G, num * (num - 1));
299  checkGraphConEdgeList(G, num * (num - 1) / 2);
300
301  checkArcDirections(G);
302
303  checkNodeIds(G);
304  checkArcIds(G);
305  checkEdgeIds(G);
306  checkGraphNodeMap(G);
307  checkGraphArcMap(G);
308  checkGraphEdgeMap(G);
309
310
311  for (int i = 0; i < G.nodeNum(); ++i) {
312    check(G.index(G(i)) == i, "Wrong index");
313  }
314
315  for (NodeIt u(G); u != INVALID; ++u) {
316    for (NodeIt v(G); v != INVALID; ++v) {
317      Edge e = G.edge(u, v);
318      Arc a = G.arc(u, v);
319      if (u == v) {
320        check(e == INVALID, "Wrong edge lookup");
321        check(a == INVALID, "Wrong arc lookup");
322      } else {
323        check((G.u(e) == u && G.v(e) == v) ||
324              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
325        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
326      }
327    }
328  }
329}
330
331void checkConcepts() {
332  { // Checking graph components
333    checkConcept<BaseGraphComponent, BaseGraphComponent >();
334
335    checkConcept<IDableGraphComponent<>,
336      IDableGraphComponent<> >();
337
338    checkConcept<IterableGraphComponent<>,
339      IterableGraphComponent<> >();
340
341    checkConcept<MappableGraphComponent<>,
342      MappableGraphComponent<> >();
343  }
344  { // Checking skeleton graph
345    checkConcept<Graph, Graph>();
346  }
347  { // Checking ListGraph
348    checkConcept<Graph, ListGraph>();
349    checkConcept<AlterableGraphComponent<>, ListGraph>();
350    checkConcept<ExtendableGraphComponent<>, ListGraph>();
351    checkConcept<ClearableGraphComponent<>, ListGraph>();
352    checkConcept<ErasableGraphComponent<>, ListGraph>();
353  }
354  { // Checking SmartGraph
355    checkConcept<Graph, SmartGraph>();
356    checkConcept<AlterableGraphComponent<>, SmartGraph>();
357    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
358    checkConcept<ClearableGraphComponent<>, SmartGraph>();
359  }
360  { // Checking FullGraph
361    checkConcept<Graph, FullGraph>();
362  }
363  { // Checking GridGraph
364    checkConcept<Graph, GridGraph>();
365  }
366  { // Checking HypercubeGraph
367    checkConcept<Graph, HypercubeGraph>();
368  }
369}
370
371template <typename Graph>
372void checkGraphValidity() {
373  TEMPLATE_GRAPH_TYPEDEFS(Graph);
374  Graph g;
375
376  Node
377    n1 = g.addNode(),
378    n2 = g.addNode(),
379    n3 = g.addNode();
380
381  Edge
382    e1 = g.addEdge(n1, n2),
383    e2 = g.addEdge(n2, n3);
384
385  check(g.valid(n1), "Wrong validity check");
386  check(g.valid(e1), "Wrong validity check");
387  check(g.valid(g.direct(e1, true)), "Wrong validity check");
388
389  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
390  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
391  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
392}
393
394template <typename Graph>
395void checkGraphValidityErase() {
396  TEMPLATE_GRAPH_TYPEDEFS(Graph);
397  Graph g;
398
399  Node
400    n1 = g.addNode(),
401    n2 = g.addNode(),
402    n3 = g.addNode();
403
404  Edge
405    e1 = g.addEdge(n1, n2),
406    e2 = g.addEdge(n2, n3);
407
408  check(g.valid(n1), "Wrong validity check");
409  check(g.valid(e1), "Wrong validity check");
410  check(g.valid(g.direct(e1, true)), "Wrong validity check");
411
412  g.erase(n1);
413
414  check(!g.valid(n1), "Wrong validity check");
415  check(g.valid(n2), "Wrong validity check");
416  check(g.valid(n3), "Wrong validity check");
417  check(!g.valid(e1), "Wrong validity check");
418  check(g.valid(e2), "Wrong validity check");
419
420  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
421  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
422  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
423}
424
425void checkGridGraph(int width, int height) {
426  typedef GridGraph Graph;
427  GRAPH_TYPEDEFS(Graph);
428  Graph G(width, height);
429
430  check(G.width() == width, "Wrong column number");
431  check(G.height() == height, "Wrong row number");
432
433  G.resize(width, height);
434  check(G.width() == width, "Wrong column number");
435  check(G.height() == height, "Wrong row number");
436
437  for (int i = 0; i < width; ++i) {
438    for (int j = 0; j < height; ++j) {
439      check(G.col(G(i, j)) == i, "Wrong column");
440      check(G.row(G(i, j)) == j, "Wrong row");
441      check(G.pos(G(i, j)).x == i, "Wrong column");
442      check(G.pos(G(i, j)).y == j, "Wrong row");
443    }
444  }
445
446  for (int j = 0; j < height; ++j) {
447    for (int i = 0; i < width - 1; ++i) {
448      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
449      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
450    }
451    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
452  }
453
454  for (int j = 0; j < height; ++j) {
455    for (int i = 1; i < width; ++i) {
456      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
457      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
458    }
459    check(G.left(G(0, j)) == INVALID, "Wrong left");
460  }
461
462  for (int i = 0; i < width; ++i) {
463    for (int j = 0; j < height - 1; ++j) {
464      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
465      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
466    }
467    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
468  }
469
470  for (int i = 0; i < width; ++i) {
471    for (int j = 1; j < height; ++j) {
472      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
473      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
474    }
475    check(G.down(G(i, 0)) == INVALID, "Wrong down");
476  }
477
478  checkGraphNodeList(G, width * height);
479  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
480  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
481
482  for (NodeIt n(G); n != INVALID; ++n) {
483    int nb = 4;
484    if (G.col(n) == 0) --nb;
485    if (G.col(n) == width - 1) --nb;
486    if (G.row(n) == 0) --nb;
487    if (G.row(n) == height - 1) --nb;
488
489    checkGraphOutArcList(G, n, nb);
490    checkGraphInArcList(G, n, nb);
491    checkGraphIncEdgeList(G, n, nb);
492  }
493
494  checkArcDirections(G);
495
496  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
497  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
498
499  checkNodeIds(G);
500  checkArcIds(G);
501  checkEdgeIds(G);
502  checkGraphNodeMap(G);
503  checkGraphArcMap(G);
504  checkGraphEdgeMap(G);
505
506}
507
508void checkHypercubeGraph(int dim) {
509  GRAPH_TYPEDEFS(HypercubeGraph);
510
511  HypercubeGraph G(dim);
512  check(G.dimension() == dim, "Wrong dimension");
513
514  G.resize(dim);
515  check(G.dimension() == dim, "Wrong dimension");
516
517  checkGraphNodeList(G, 1 << dim);
518  checkGraphEdgeList(G, dim * (1 << (dim-1)));
519  checkGraphArcList(G, dim * (1 << dim));
520
521  Node n = G.nodeFromId(dim);
522
523  for (NodeIt n(G); n != INVALID; ++n) {
524    checkGraphIncEdgeList(G, n, dim);
525    for (IncEdgeIt e(G, n); e != INVALID; ++e) {
526      check( (G.u(e) == n &&
527              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
528             (G.v(e) == n &&
529              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
530             "Wrong edge or wrong dimension");
531    }
532
533    checkGraphOutArcList(G, n, dim);
534    for (OutArcIt a(G, n); a != INVALID; ++a) {
535      check(G.source(a) == n &&
536            G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
537            "Wrong arc or wrong dimension");
538    }
539
540    checkGraphInArcList(G, n, dim);
541    for (InArcIt a(G, n); a != INVALID; ++a) {
542      check(G.target(a) == n &&
543            G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
544            "Wrong arc or wrong dimension");
545    }
546  }
547
548  checkGraphConArcList(G, (1 << dim) * dim);
549  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
550
551  checkArcDirections(G);
552
553  checkNodeIds(G);
554  checkArcIds(G);
555  checkEdgeIds(G);
556  checkGraphNodeMap(G);
557  checkGraphArcMap(G);
558  checkGraphEdgeMap(G);
559}
560
561void checkGraphs() {
562  { // Checking ListGraph
563    checkGraphBuild<ListGraph>();
564    checkGraphAlter<ListGraph>();
565    checkGraphErase<ListGraph>();
566    checkGraphSnapshot<ListGraph>();
567    checkGraphValidityErase<ListGraph>();
568  }
569  { // Checking SmartGraph
570    checkGraphBuild<SmartGraph>();
571    checkGraphSnapshot<SmartGraph>();
572    checkGraphValidity<SmartGraph>();
573  }
574  { // Checking FullGraph
575    checkFullGraph(7);
576    checkFullGraph(8);
577  }
578  { // Checking GridGraph
579    checkGridGraph(5, 8);
580    checkGridGraph(8, 5);
581    checkGridGraph(5, 5);
582    checkGridGraph(0, 0);
583    checkGridGraph(1, 1);
584  }
585  { // Checking HypercubeGraph
586    checkHypercubeGraph(1);
587    checkHypercubeGraph(2);
588    checkHypercubeGraph(3);
589    checkHypercubeGraph(4);
590  }
591}
592
593int main() {
594  checkConcepts();
595  checkGraphs();
596  return 0;
597}
Note: See TracBrowser for help on using the repository browser.