COIN-OR::LEMON - Graph Library

source: lemon-main/test/graph_test.cc @ 736:2e20aad15754

Last change on this file since 736:2e20aad15754 was 736:2e20aad15754, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Add reserve functions to ListGraph? and SmartGraph? (#311)
ListDigraph? and SmartDigraph? already have such functions.

File size: 14.1 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  checkGraphNodeList(G, num);
274  checkGraphEdgeList(G, num * (num - 1) / 2);
275
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);
280  }
281
282  checkGraphConArcList(G, num * (num - 1));
283  checkGraphConEdgeList(G, num * (num - 1) / 2);
284
285  checkArcDirections(G);
286
287  checkNodeIds(G);
288  checkArcIds(G);
289  checkEdgeIds(G);
290  checkGraphNodeMap(G);
291  checkGraphArcMap(G);
292  checkGraphEdgeMap(G);
293
294
295  for (int i = 0; i < G.nodeNum(); ++i) {
296    check(G.index(G(i)) == i, "Wrong index");
297  }
298
299  for (NodeIt u(G); u != INVALID; ++u) {
300    for (NodeIt v(G); v != INVALID; ++v) {
301      Edge e = G.edge(u, v);
302      Arc a = G.arc(u, v);
303      if (u == v) {
304        check(e == INVALID, "Wrong edge lookup");
305        check(a == INVALID, "Wrong arc lookup");
306      } else {
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");
310      }
311    }
312  }
313}
314
315void checkConcepts() {
316  { // Checking graph components
317    checkConcept<BaseGraphComponent, BaseGraphComponent >();
318
319    checkConcept<IDableGraphComponent<>,
320      IDableGraphComponent<> >();
321
322    checkConcept<IterableGraphComponent<>,
323      IterableGraphComponent<> >();
324
325    checkConcept<MappableGraphComponent<>,
326      MappableGraphComponent<> >();
327  }
328  { // Checking skeleton graph
329    checkConcept<Graph, Graph>();
330  }
331  { // Checking ListGraph
332    checkConcept<Graph, ListGraph>();
333    checkConcept<AlterableGraphComponent<>, ListGraph>();
334    checkConcept<ExtendableGraphComponent<>, ListGraph>();
335    checkConcept<ClearableGraphComponent<>, ListGraph>();
336    checkConcept<ErasableGraphComponent<>, ListGraph>();
337  }
338  { // Checking SmartGraph
339    checkConcept<Graph, SmartGraph>();
340    checkConcept<AlterableGraphComponent<>, SmartGraph>();
341    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
342    checkConcept<ClearableGraphComponent<>, SmartGraph>();
343  }
344  { // Checking FullGraph
345    checkConcept<Graph, FullGraph>();
346  }
347  { // Checking GridGraph
348    checkConcept<Graph, GridGraph>();
349  }
350  { // Checking HypercubeGraph
351    checkConcept<Graph, HypercubeGraph>();
352  }
353}
354
355template <typename Graph>
356void checkGraphValidity() {
357  TEMPLATE_GRAPH_TYPEDEFS(Graph);
358  Graph g;
359
360  Node
361    n1 = g.addNode(),
362    n2 = g.addNode(),
363    n3 = g.addNode();
364
365  Edge
366    e1 = g.addEdge(n1, n2),
367    e2 = g.addEdge(n2, n3);
368
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");
372
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");
376}
377
378template <typename Graph>
379void checkGraphValidityErase() {
380  TEMPLATE_GRAPH_TYPEDEFS(Graph);
381  Graph g;
382
383  Node
384    n1 = g.addNode(),
385    n2 = g.addNode(),
386    n3 = g.addNode();
387
388  Edge
389    e1 = g.addEdge(n1, n2),
390    e2 = g.addEdge(n2, n3);
391
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");
395
396  g.erase(n1);
397
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");
403
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");
407}
408
409void checkGridGraph(int width, int height) {
410  typedef GridGraph Graph;
411  GRAPH_TYPEDEFS(Graph);
412  Graph G(width, height);
413
414  check(G.width() == width, "Wrong column number");
415  check(G.height() == height, "Wrong row number");
416
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");
423    }
424  }
425
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");
430    }
431    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
432  }
433
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");
438    }
439    check(G.left(G(0, j)) == INVALID, "Wrong left");
440  }
441
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");
446    }
447    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
448  }
449
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");
454    }
455    check(G.down(G(i, 0)) == INVALID, "Wrong down");
456  }
457
458  checkGraphNodeList(G, width * height);
459  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
460  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
461
462  for (NodeIt n(G); n != INVALID; ++n) {
463    int nb = 4;
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;
468
469    checkGraphOutArcList(G, n, nb);
470    checkGraphInArcList(G, n, nb);
471    checkGraphIncEdgeList(G, n, nb);
472  }
473
474  checkArcDirections(G);
475
476  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
477  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
478
479  checkNodeIds(G);
480  checkArcIds(G);
481  checkEdgeIds(G);
482  checkGraphNodeMap(G);
483  checkGraphArcMap(G);
484  checkGraphEdgeMap(G);
485
486}
487
488void checkHypercubeGraph(int dim) {
489  GRAPH_TYPEDEFS(HypercubeGraph);
490
491  HypercubeGraph G(dim);
492  checkGraphNodeList(G, 1 << dim);
493  checkGraphEdgeList(G, dim * (1 << (dim-1)));
494  checkGraphArcList(G, dim * (1 << dim));
495
496  Node n = G.nodeFromId(dim);
497
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)))) ||
503             (G.v(e) == n &&
504              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
505             "Wrong edge or wrong dimension");
506    }
507
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");
513    }
514
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");
520    }
521  }
522
523  checkGraphConArcList(G, (1 << dim) * dim);
524  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
525
526  checkArcDirections(G);
527
528  checkNodeIds(G);
529  checkArcIds(G);
530  checkEdgeIds(G);
531  checkGraphNodeMap(G);
532  checkGraphArcMap(G);
533  checkGraphEdgeMap(G);
534}
535
536void checkGraphs() {
537  { // Checking ListGraph
538    checkGraphBuild<ListGraph>();
539    checkGraphAlter<ListGraph>();
540    checkGraphErase<ListGraph>();
541    checkGraphSnapshot<ListGraph>();
542    checkGraphValidityErase<ListGraph>();
543  }
544  { // Checking SmartGraph
545    checkGraphBuild<SmartGraph>();
546    checkGraphSnapshot<SmartGraph>();
547    checkGraphValidity<SmartGraph>();
548  }
549  { // Checking FullGraph
550    checkFullGraph(7);
551    checkFullGraph(8);
552  }
553  { // Checking GridGraph
554    checkGridGraph(5, 8);
555    checkGridGraph(8, 5);
556    checkGridGraph(5, 5);
557    checkGridGraph(0, 0);
558    checkGridGraph(1, 1);
559  }
560  { // Checking HypercubeGraph
561    checkHypercubeGraph(1);
562    checkHypercubeGraph(2);
563    checkHypercubeGraph(3);
564    checkHypercubeGraph(4);
565  }
566}
567
568int main() {
569  checkConcepts();
570  checkGraphs();
571  return 0;
572}
Note: See TracBrowser for help on using the repository browser.