COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/graph_test.cc @ 737:9d6c3e8b2421

Last change on this file since 737:9d6c3e8b2421 was 737:9d6c3e8b2421, checked in by Peter Kovacs <kpeter@…>, 10 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
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[57]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[57]4 *
[440]5 * Copyright (C) 2003-2009
[57]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>
[109]21#include <lemon/smart_graph.h>
[353]22#include <lemon/full_graph.h>
[334]23#include <lemon/grid_graph.h>
[365]24#include <lemon/hypercube_graph.h>
[57]25
26#include "test_tools.h"
[171]27#include "graph_test.h"
[57]28
29using namespace lemon;
30using namespace lemon::concepts;
31
[228]32template <class Graph>
[374]33void checkGraphBuild() {
[228]34  TEMPLATE_GRAPH_TYPEDEFS(Graph);
35
36  Graph G;
37  checkGraphNodeList(G, 0);
38  checkGraphEdgeList(G, 0);
[374]39  checkGraphArcList(G, 0);
[228]40
[736]41  G.reserveNode(3);
42  G.reserveEdge(3);
43
[228]44  Node
45    n1 = G.addNode(),
46    n2 = G.addNode(),
47    n3 = G.addNode();
48  checkGraphNodeList(G, 3);
49  checkGraphEdgeList(G, 0);
[374]50  checkGraphArcList(G, 0);
[228]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");
[374]55
[228]56  checkGraphNodeList(G, 3);
[374]57  checkGraphEdgeList(G, 1);
[228]58  checkGraphArcList(G, 2);
59
[374]60  checkGraphIncEdgeArcLists(G, n1, 1);
61  checkGraphIncEdgeArcLists(G, n2, 1);
62  checkGraphIncEdgeArcLists(G, n3, 0);
[228]63
[374]64  checkGraphConEdgeList(G, 1);
65  checkGraphConArcList(G, 2);
[228]66
[374]67  Edge e2 = G.addEdge(n2, n1),
68       e3 = G.addEdge(n2, n3);
[228]69
[374]70  checkGraphNodeList(G, 3);
71  checkGraphEdgeList(G, 3);
72  checkGraphArcList(G, 6);
[228]73
[374]74  checkGraphIncEdgeArcLists(G, n1, 2);
75  checkGraphIncEdgeArcLists(G, n2, 3);
76  checkGraphIncEdgeArcLists(G, n3, 1);
[228]77
[374]78  checkGraphConEdgeList(G, 3);
[228]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
[374]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
[353]268void checkFullGraph(int num) {
269  typedef FullGraph Graph;
270  GRAPH_TYPEDEFS(Graph);
271
272  Graph G(num);
[737]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
[353]280  checkGraphNodeList(G, num);
281  checkGraphEdgeList(G, num * (num - 1) / 2);
282
283  for (NodeIt n(G); n != INVALID; ++n) {
[365]284    checkGraphOutArcList(G, n, num - 1);
285    checkGraphInArcList(G, n, num - 1);
286    checkGraphIncEdgeList(G, n, num - 1);
[353]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
[365]301
[353]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
[228]322void checkConcepts() {
[171]323  { // Checking graph components
[57]324    checkConcept<BaseGraphComponent, BaseGraphComponent >();
325
[209]326    checkConcept<IDableGraphComponent<>,
[57]327      IDableGraphComponent<> >();
328
[209]329    checkConcept<IterableGraphComponent<>,
[57]330      IterableGraphComponent<> >();
331
[209]332    checkConcept<MappableGraphComponent<>,
[57]333      MappableGraphComponent<> >();
334  }
[171]335  { // Checking skeleton graph
336    checkConcept<Graph, Graph>();
[57]337  }
[171]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  }
[353]351  { // Checking FullGraph
352    checkConcept<Graph, FullGraph>();
353  }
[334]354  { // Checking GridGraph
355    checkConcept<Graph, GridGraph>();
356  }
[365]357  { // Checking HypercubeGraph
358    checkConcept<Graph, HypercubeGraph>();
359  }
[57]360}
361
362template <typename Graph>
[228]363void checkGraphValidity() {
[149]364  TEMPLATE_GRAPH_TYPEDEFS(Graph);
[57]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
[171]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");
[57]383}
384
[149]385template <typename Graph>
[228]386void checkGraphValidityErase() {
[149]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
[171]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");
[149]402
403  g.erase(n1);
404
[171]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");
[149]410
[171]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");
[149]414}
415
[335]416void checkGridGraph(int width, int height) {
417  typedef GridGraph Graph;
418  GRAPH_TYPEDEFS(Graph);
419  Graph G(width, height);
[57]420
[336]421  check(G.width() == width, "Wrong column number");
422  check(G.height() == height, "Wrong row number");
[209]423
[737]424  G.resize(width, height);
425  check(G.width() == width, "Wrong column number");
426  check(G.height() == height, "Wrong row number");
427
[335]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");
[334]434    }
435  }
[57]436
[335]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");
[334]441    }
[335]442    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
[334]443  }
[57]444
[335]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");
[334]449    }
[335]450    check(G.left(G(0, j)) == INVALID, "Wrong left");
[334]451  }
[57]452
[335]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");
[334]457    }
[335]458    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
[334]459  }
[228]460
[335]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");
[334]465    }
[335]466    check(G.down(G(i, 0)) == INVALID, "Wrong down");
[334]467  }
468
[335]469  checkGraphNodeList(G, width * height);
470  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
471  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
[334]472
[335]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;
[334]479
[335]480    checkGraphOutArcList(G, n, nb);
481    checkGraphInArcList(G, n, nb);
482    checkGraphIncEdgeList(G, n, nb);
483  }
[334]484
[335]485  checkArcDirections(G);
[334]486
[335]487  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
488  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
[334]489
[335]490  checkNodeIds(G);
491  checkArcIds(G);
492  checkEdgeIds(G);
493  checkGraphNodeMap(G);
494  checkGraphArcMap(G);
495  checkGraphEdgeMap(G);
[334]496
497}
[228]498
[365]499void checkHypercubeGraph(int dim) {
500  GRAPH_TYPEDEFS(HypercubeGraph);
501
502  HypercubeGraph G(dim);
[737]503  check(G.dimension() == dim, "Wrong dimension");
504
505  G.resize(dim);
506  check(G.dimension() == dim, "Wrong dimension");
507 
[365]508  checkGraphNodeList(G, 1 << dim);
[372]509  checkGraphEdgeList(G, dim * (1 << (dim-1)));
[365]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 &&
[372]518              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
[365]519             (G.v(e) == n &&
[372]520              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
[365]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 &&
[372]527            G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
[365]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 &&
[372]534            G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
[365]535            "Wrong arc or wrong dimension");
536    }
537  }
538
539  checkGraphConArcList(G, (1 << dim) * dim);
[372]540  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
[365]541
542  checkArcDirections(G);
543
544  checkNodeIds(G);
545  checkArcIds(G);
546  checkEdgeIds(G);
547  checkGraphNodeMap(G);
548  checkGraphArcMap(G);
549  checkGraphEdgeMap(G);
550}
[57]551
[228]552void checkGraphs() {
[171]553  { // Checking ListGraph
[374]554    checkGraphBuild<ListGraph>();
555    checkGraphAlter<ListGraph>();
556    checkGraphErase<ListGraph>();
557    checkGraphSnapshot<ListGraph>();
[228]558    checkGraphValidityErase<ListGraph>();
[171]559  }
560  { // Checking SmartGraph
[374]561    checkGraphBuild<SmartGraph>();
562    checkGraphSnapshot<SmartGraph>();
[228]563    checkGraphValidity<SmartGraph>();
[171]564  }
[365]565  { // Checking FullGraph
[353]566    checkFullGraph(7);
567    checkFullGraph(8);
568  }
[334]569  { // Checking GridGraph
[335]570    checkGridGraph(5, 8);
571    checkGridGraph(8, 5);
572    checkGridGraph(5, 5);
573    checkGridGraph(0, 0);
574    checkGridGraph(1, 1);
[334]575  }
[365]576  { // Checking HypercubeGraph
577    checkHypercubeGraph(1);
578    checkHypercubeGraph(2);
579    checkHypercubeGraph(3);
580    checkHypercubeGraph(4);
581  }
[171]582}
583
[57]584int main() {
[228]585  checkConcepts();
586  checkGraphs();
[57]587  return 0;
588}
Note: See TracBrowser for help on using the repository browser.