COIN-OR::LEMON - Graph Library

source: lemon/test/graph_test.cc @ 1172:c18ed26f016c

Last change on this file since 1172:c18ed26f016c was 1157:761fe0846f49, checked in by Alpar Juttner <alpar@…>, 12 years ago

Fix clang compilation warnings and errors (#449)

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