COIN-OR::LEMON - Graph Library

source: lemon-main/test/graph_test.cc @ 998:7fdaa05a69a1

Last change on this file since 998:7fdaa05a69a1 was 998:7fdaa05a69a1, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge #449 to branches >=1.2

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