COIN-OR::LEMON - Graph Library

source: lemon/test/graph_test.cc @ 783:2e20aad15754

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

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

File size: 14.1 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 *
[463]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>
[365]22#include <lemon/full_graph.h>
[346]23#include <lemon/grid_graph.h>
[377]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>
[387]33void checkGraphBuild() {
[228]34  TEMPLATE_GRAPH_TYPEDEFS(Graph);
35
36  Graph G;
37  checkGraphNodeList(G, 0);
38  checkGraphEdgeList(G, 0);
[387]39  checkGraphArcList(G, 0);
[228]40
[783]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);
[387]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");
[387]55
[228]56  checkGraphNodeList(G, 3);
[387]57  checkGraphEdgeList(G, 1);
[228]58  checkGraphArcList(G, 2);
59
[387]60  checkGraphIncEdgeArcLists(G, n1, 1);
61  checkGraphIncEdgeArcLists(G, n2, 1);
62  checkGraphIncEdgeArcLists(G, n3, 0);
[228]63
[387]64  checkGraphConEdgeList(G, 1);
65  checkGraphConArcList(G, 2);
[228]66
[387]67  Edge e2 = G.addEdge(n2, n1),
68       e3 = G.addEdge(n2, n3);
[228]69
[387]70  checkGraphNodeList(G, 3);
71  checkGraphEdgeList(G, 3);
72  checkGraphArcList(G, 6);
[228]73
[387]74  checkGraphIncEdgeArcLists(G, n1, 2);
75  checkGraphIncEdgeArcLists(G, n2, 3);
76  checkGraphIncEdgeArcLists(G, n3, 1);
[228]77
[387]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
[387]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
[365]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) {
[377]277    checkGraphOutArcList(G, n, num - 1);
278    checkGraphInArcList(G, n, num - 1);
279    checkGraphIncEdgeList(G, n, num - 1);
[365]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
[377]294
[365]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
[228]315void checkConcepts() {
[171]316  { // Checking graph components
[57]317    checkConcept<BaseGraphComponent, BaseGraphComponent >();
318
[209]319    checkConcept<IDableGraphComponent<>,
[57]320      IDableGraphComponent<> >();
321
[209]322    checkConcept<IterableGraphComponent<>,
[57]323      IterableGraphComponent<> >();
324
[209]325    checkConcept<MappableGraphComponent<>,
[57]326      MappableGraphComponent<> >();
327  }
[171]328  { // Checking skeleton graph
329    checkConcept<Graph, Graph>();
[57]330  }
[171]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  }
[365]344  { // Checking FullGraph
345    checkConcept<Graph, FullGraph>();
346  }
[346]347  { // Checking GridGraph
348    checkConcept<Graph, GridGraph>();
349  }
[377]350  { // Checking HypercubeGraph
351    checkConcept<Graph, HypercubeGraph>();
352  }
[57]353}
354
355template <typename Graph>
[228]356void checkGraphValidity() {
[149]357  TEMPLATE_GRAPH_TYPEDEFS(Graph);
[57]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
[171]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");
[57]376}
377
[149]378template <typename Graph>
[228]379void checkGraphValidityErase() {
[149]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
[171]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");
[149]395
396  g.erase(n1);
397
[171]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");
[149]403
[171]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");
[149]407}
408
[347]409void checkGridGraph(int width, int height) {
410  typedef GridGraph Graph;
411  GRAPH_TYPEDEFS(Graph);
412  Graph G(width, height);
[57]413
[348]414  check(G.width() == width, "Wrong column number");
415  check(G.height() == height, "Wrong row number");
[209]416
[347]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");
[346]423    }
424  }
[57]425
[347]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");
[346]430    }
[347]431    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
[346]432  }
[57]433
[347]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");
[346]438    }
[347]439    check(G.left(G(0, j)) == INVALID, "Wrong left");
[346]440  }
[57]441
[347]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");
[346]446    }
[347]447    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
[346]448  }
[228]449
[347]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");
[346]454    }
[347]455    check(G.down(G(i, 0)) == INVALID, "Wrong down");
[346]456  }
457
[347]458  checkGraphNodeList(G, width * height);
459  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
460  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
[346]461
[347]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;
[346]468
[347]469    checkGraphOutArcList(G, n, nb);
470    checkGraphInArcList(G, n, nb);
471    checkGraphIncEdgeList(G, n, nb);
472  }
[346]473
[347]474  checkArcDirections(G);
[346]475
[347]476  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
477  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
[346]478
[347]479  checkNodeIds(G);
480  checkArcIds(G);
481  checkEdgeIds(G);
482  checkGraphNodeMap(G);
483  checkGraphArcMap(G);
484  checkGraphEdgeMap(G);
[346]485
486}
[228]487
[377]488void checkHypercubeGraph(int dim) {
489  GRAPH_TYPEDEFS(HypercubeGraph);
490
491  HypercubeGraph G(dim);
492  checkGraphNodeList(G, 1 << dim);
[385]493  checkGraphEdgeList(G, dim * (1 << (dim-1)));
[377]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 &&
[385]502              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
[377]503             (G.v(e) == n &&
[385]504              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
[377]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 &&
[385]511            G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
[377]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 &&
[385]518            G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
[377]519            "Wrong arc or wrong dimension");
520    }
521  }
522
523  checkGraphConArcList(G, (1 << dim) * dim);
[385]524  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
[377]525
526  checkArcDirections(G);
527
528  checkNodeIds(G);
529  checkArcIds(G);
530  checkEdgeIds(G);
531  checkGraphNodeMap(G);
532  checkGraphArcMap(G);
533  checkGraphEdgeMap(G);
534}
[57]535
[228]536void checkGraphs() {
[171]537  { // Checking ListGraph
[387]538    checkGraphBuild<ListGraph>();
539    checkGraphAlter<ListGraph>();
540    checkGraphErase<ListGraph>();
541    checkGraphSnapshot<ListGraph>();
[228]542    checkGraphValidityErase<ListGraph>();
[171]543  }
544  { // Checking SmartGraph
[387]545    checkGraphBuild<SmartGraph>();
546    checkGraphSnapshot<SmartGraph>();
[228]547    checkGraphValidity<SmartGraph>();
[171]548  }
[377]549  { // Checking FullGraph
[365]550    checkFullGraph(7);
551    checkFullGraph(8);
552  }
[346]553  { // Checking GridGraph
[347]554    checkGridGraph(5, 8);
555    checkGridGraph(8, 5);
556    checkGridGraph(5, 5);
557    checkGridGraph(0, 0);
558    checkGridGraph(1, 1);
[346]559  }
[377]560  { // Checking HypercubeGraph
561    checkHypercubeGraph(1);
562    checkHypercubeGraph(2);
563    checkHypercubeGraph(3);
564    checkHypercubeGraph(4);
565  }
[171]566}
567
[57]568int main() {
[228]569  checkConcepts();
570  checkGraphs();
[57]571  return 0;
572}
Note: See TracBrowser for help on using the repository browser.