COIN-OR::LEMON - Graph Library

source: lemon/test/graph_test.cc @ 784:9d6c3e8b2421

Last change on this file since 784:9d6c3e8b2421 was 784:9d6c3e8b2421, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Add a resize() function to HypercubeGraph? (#311)
just like the similar functions in other static graph structures,
and extend the test files to check these functions.

File size: 14.6 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-2009
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
263  checkGraphNodeList(G, 4);
264  checkGraphEdgeList(G, 3);
265  checkGraphArcList(G, 6);
266}
267
268void checkFullGraph(int num) {
269  typedef FullGraph Graph;
270  GRAPH_TYPEDEFS(Graph);
271
272  Graph G(num);
273  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
274        "Wrong size");
275
276  G.resize(num);
277  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
278        "Wrong size");
279
280  checkGraphNodeList(G, num);
281  checkGraphEdgeList(G, num * (num - 1) / 2);
282
283  for (NodeIt n(G); n != INVALID; ++n) {
284    checkGraphOutArcList(G, n, num - 1);
285    checkGraphInArcList(G, n, num - 1);
286    checkGraphIncEdgeList(G, n, num - 1);
287  }
288
289  checkGraphConArcList(G, num * (num - 1));
290  checkGraphConEdgeList(G, num * (num - 1) / 2);
291
292  checkArcDirections(G);
293
294  checkNodeIds(G);
295  checkArcIds(G);
296  checkEdgeIds(G);
297  checkGraphNodeMap(G);
298  checkGraphArcMap(G);
299  checkGraphEdgeMap(G);
300
301
302  for (int i = 0; i < G.nodeNum(); ++i) {
303    check(G.index(G(i)) == i, "Wrong index");
304  }
305
306  for (NodeIt u(G); u != INVALID; ++u) {
307    for (NodeIt v(G); v != INVALID; ++v) {
308      Edge e = G.edge(u, v);
309      Arc a = G.arc(u, v);
310      if (u == v) {
311        check(e == INVALID, "Wrong edge lookup");
312        check(a == INVALID, "Wrong arc lookup");
313      } else {
314        check((G.u(e) == u && G.v(e) == v) ||
315              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
316        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
317      }
318    }
319  }
320}
321
322void checkConcepts() {
323  { // Checking graph components
324    checkConcept<BaseGraphComponent, BaseGraphComponent >();
325
326    checkConcept<IDableGraphComponent<>,
327      IDableGraphComponent<> >();
328
329    checkConcept<IterableGraphComponent<>,
330      IterableGraphComponent<> >();
331
332    checkConcept<MappableGraphComponent<>,
333      MappableGraphComponent<> >();
334  }
335  { // Checking skeleton graph
336    checkConcept<Graph, Graph>();
337  }
338  { // Checking ListGraph
339    checkConcept<Graph, ListGraph>();
340    checkConcept<AlterableGraphComponent<>, ListGraph>();
341    checkConcept<ExtendableGraphComponent<>, ListGraph>();
342    checkConcept<ClearableGraphComponent<>, ListGraph>();
343    checkConcept<ErasableGraphComponent<>, ListGraph>();
344  }
345  { // Checking SmartGraph
346    checkConcept<Graph, SmartGraph>();
347    checkConcept<AlterableGraphComponent<>, SmartGraph>();
348    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
349    checkConcept<ClearableGraphComponent<>, SmartGraph>();
350  }
351  { // Checking FullGraph
352    checkConcept<Graph, FullGraph>();
353  }
354  { // Checking GridGraph
355    checkConcept<Graph, GridGraph>();
356  }
357  { // Checking HypercubeGraph
358    checkConcept<Graph, HypercubeGraph>();
359  }
360}
361
362template <typename Graph>
363void checkGraphValidity() {
364  TEMPLATE_GRAPH_TYPEDEFS(Graph);
365  Graph g;
366
367  Node
368    n1 = g.addNode(),
369    n2 = g.addNode(),
370    n3 = g.addNode();
371
372  Edge
373    e1 = g.addEdge(n1, n2),
374    e2 = g.addEdge(n2, n3);
375
376  check(g.valid(n1), "Wrong validity check");
377  check(g.valid(e1), "Wrong validity check");
378  check(g.valid(g.direct(e1, true)), "Wrong validity check");
379
380  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
381  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
382  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
383}
384
385template <typename Graph>
386void checkGraphValidityErase() {
387  TEMPLATE_GRAPH_TYPEDEFS(Graph);
388  Graph g;
389
390  Node
391    n1 = g.addNode(),
392    n2 = g.addNode(),
393    n3 = g.addNode();
394
395  Edge
396    e1 = g.addEdge(n1, n2),
397    e2 = g.addEdge(n2, n3);
398
399  check(g.valid(n1), "Wrong validity check");
400  check(g.valid(e1), "Wrong validity check");
401  check(g.valid(g.direct(e1, true)), "Wrong validity check");
402
403  g.erase(n1);
404
405  check(!g.valid(n1), "Wrong validity check");
406  check(g.valid(n2), "Wrong validity check");
407  check(g.valid(n3), "Wrong validity check");
408  check(!g.valid(e1), "Wrong validity check");
409  check(g.valid(e2), "Wrong validity check");
410
411  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
412  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
413  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
414}
415
416void checkGridGraph(int width, int height) {
417  typedef GridGraph Graph;
418  GRAPH_TYPEDEFS(Graph);
419  Graph G(width, height);
420
421  check(G.width() == width, "Wrong column number");
422  check(G.height() == height, "Wrong row number");
423
424  G.resize(width, height);
425  check(G.width() == width, "Wrong column number");
426  check(G.height() == height, "Wrong row number");
427
428  for (int i = 0; i < width; ++i) {
429    for (int j = 0; j < height; ++j) {
430      check(G.col(G(i, j)) == i, "Wrong column");
431      check(G.row(G(i, j)) == j, "Wrong row");
432      check(G.pos(G(i, j)).x == i, "Wrong column");
433      check(G.pos(G(i, j)).y == j, "Wrong row");
434    }
435  }
436
437  for (int j = 0; j < height; ++j) {
438    for (int i = 0; i < width - 1; ++i) {
439      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
440      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
441    }
442    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
443  }
444
445  for (int j = 0; j < height; ++j) {
446    for (int i = 1; i < width; ++i) {
447      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
448      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
449    }
450    check(G.left(G(0, j)) == INVALID, "Wrong left");
451  }
452
453  for (int i = 0; i < width; ++i) {
454    for (int j = 0; j < height - 1; ++j) {
455      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
456      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
457    }
458    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
459  }
460
461  for (int i = 0; i < width; ++i) {
462    for (int j = 1; j < height; ++j) {
463      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
464      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
465    }
466    check(G.down(G(i, 0)) == INVALID, "Wrong down");
467  }
468
469  checkGraphNodeList(G, width * height);
470  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
471  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
472
473  for (NodeIt n(G); n != INVALID; ++n) {
474    int nb = 4;
475    if (G.col(n) == 0) --nb;
476    if (G.col(n) == width - 1) --nb;
477    if (G.row(n) == 0) --nb;
478    if (G.row(n) == height - 1) --nb;
479
480    checkGraphOutArcList(G, n, nb);
481    checkGraphInArcList(G, n, nb);
482    checkGraphIncEdgeList(G, n, nb);
483  }
484
485  checkArcDirections(G);
486
487  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
488  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
489
490  checkNodeIds(G);
491  checkArcIds(G);
492  checkEdgeIds(G);
493  checkGraphNodeMap(G);
494  checkGraphArcMap(G);
495  checkGraphEdgeMap(G);
496
497}
498
499void checkHypercubeGraph(int dim) {
500  GRAPH_TYPEDEFS(HypercubeGraph);
501
502  HypercubeGraph G(dim);
503  check(G.dimension() == dim, "Wrong dimension");
504
505  G.resize(dim);
506  check(G.dimension() == dim, "Wrong dimension");
507 
508  checkGraphNodeList(G, 1 << dim);
509  checkGraphEdgeList(G, dim * (1 << (dim-1)));
510  checkGraphArcList(G, dim * (1 << dim));
511
512  Node n = G.nodeFromId(dim);
513
514  for (NodeIt n(G); n != INVALID; ++n) {
515    checkGraphIncEdgeList(G, n, dim);
516    for (IncEdgeIt e(G, n); e != INVALID; ++e) {
517      check( (G.u(e) == n &&
518              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
519             (G.v(e) == n &&
520              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
521             "Wrong edge or wrong dimension");
522    }
523
524    checkGraphOutArcList(G, n, dim);
525    for (OutArcIt a(G, n); a != INVALID; ++a) {
526      check(G.source(a) == n &&
527            G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
528            "Wrong arc or wrong dimension");
529    }
530
531    checkGraphInArcList(G, n, dim);
532    for (InArcIt a(G, n); a != INVALID; ++a) {
533      check(G.target(a) == n &&
534            G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
535            "Wrong arc or wrong dimension");
536    }
537  }
538
539  checkGraphConArcList(G, (1 << dim) * dim);
540  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
541
542  checkArcDirections(G);
543
544  checkNodeIds(G);
545  checkArcIds(G);
546  checkEdgeIds(G);
547  checkGraphNodeMap(G);
548  checkGraphArcMap(G);
549  checkGraphEdgeMap(G);
550}
551
552void checkGraphs() {
553  { // Checking ListGraph
554    checkGraphBuild<ListGraph>();
555    checkGraphAlter<ListGraph>();
556    checkGraphErase<ListGraph>();
557    checkGraphSnapshot<ListGraph>();
558    checkGraphValidityErase<ListGraph>();
559  }
560  { // Checking SmartGraph
561    checkGraphBuild<SmartGraph>();
562    checkGraphSnapshot<SmartGraph>();
563    checkGraphValidity<SmartGraph>();
564  }
565  { // Checking FullGraph
566    checkFullGraph(7);
567    checkFullGraph(8);
568  }
569  { // Checking GridGraph
570    checkGridGraph(5, 8);
571    checkGridGraph(8, 5);
572    checkGridGraph(5, 5);
573    checkGridGraph(0, 0);
574    checkGridGraph(1, 1);
575  }
576  { // Checking HypercubeGraph
577    checkHypercubeGraph(1);
578    checkHypercubeGraph(2);
579    checkHypercubeGraph(3);
580    checkHypercubeGraph(4);
581  }
582}
583
584int main() {
585  checkConcepts();
586  checkGraphs();
587  return 0;
588}
Note: See TracBrowser for help on using the repository browser.