COIN-OR::LEMON - Graph Library

source: lemon-1.0/test/graph_test.cc

Last change on this file was 338:49d9a36b3b84, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Extend test cases for graphs and digraphs (#172)

File size: 10.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-2008
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
25#include "test_tools.h"
26#include "graph_test.h"
27
28using namespace lemon;
29using namespace lemon::concepts;
30
31template <class Graph>
32void checkGraphBuild() {
33  TEMPLATE_GRAPH_TYPEDEFS(Graph);
34
35  Graph G;
36  checkGraphNodeList(G, 0);
37  checkGraphEdgeList(G, 0);
38  checkGraphArcList(G, 0);
39
40  Node
41    n1 = G.addNode(),
42    n2 = G.addNode(),
43    n3 = G.addNode();
44  checkGraphNodeList(G, 3);
45  checkGraphEdgeList(G, 0);
46  checkGraphArcList(G, 0);
47
48  Edge e1 = G.addEdge(n1, n2);
49  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
50        "Wrong edge");
51
52  checkGraphNodeList(G, 3);
53  checkGraphEdgeList(G, 1);
54  checkGraphArcList(G, 2);
55
56  checkGraphIncEdgeArcLists(G, n1, 1);
57  checkGraphIncEdgeArcLists(G, n2, 1);
58  checkGraphIncEdgeArcLists(G, n3, 0);
59
60  checkGraphConEdgeList(G, 1);
61  checkGraphConArcList(G, 2);
62
63  Edge e2 = G.addEdge(n2, n1),
64       e3 = G.addEdge(n2, n3);
65
66  checkGraphNodeList(G, 3);
67  checkGraphEdgeList(G, 3);
68  checkGraphArcList(G, 6);
69
70  checkGraphIncEdgeArcLists(G, n1, 2);
71  checkGraphIncEdgeArcLists(G, n2, 3);
72  checkGraphIncEdgeArcLists(G, n3, 1);
73
74  checkGraphConEdgeList(G, 3);
75  checkGraphConArcList(G, 6);
76
77  checkArcDirections(G);
78
79  checkNodeIds(G);
80  checkArcIds(G);
81  checkEdgeIds(G);
82  checkGraphNodeMap(G);
83  checkGraphArcMap(G);
84  checkGraphEdgeMap(G);
85}
86
87template <class Graph>
88void checkGraphAlter() {
89  TEMPLATE_GRAPH_TYPEDEFS(Graph);
90
91  Graph G;
92  Node n1 = G.addNode(), n2 = G.addNode(),
93       n3 = G.addNode(), n4 = G.addNode();
94  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
95       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
96       e5 = G.addEdge(n4, n3);
97
98  checkGraphNodeList(G, 4);
99  checkGraphEdgeList(G, 5);
100  checkGraphArcList(G, 10);
101
102  // Check changeU() and changeV()
103  if (G.u(e2) == n2) {
104    G.changeU(e2, n3);
105  } else {
106    G.changeV(e2, n3);
107  }
108
109  checkGraphNodeList(G, 4);
110  checkGraphEdgeList(G, 5);
111  checkGraphArcList(G, 10);
112
113  checkGraphIncEdgeArcLists(G, n1, 3);
114  checkGraphIncEdgeArcLists(G, n2, 2);
115  checkGraphIncEdgeArcLists(G, n3, 3);
116  checkGraphIncEdgeArcLists(G, n4, 2);
117
118  checkGraphConEdgeList(G, 5);
119  checkGraphConArcList(G, 10);
120
121  if (G.u(e2) == n1) {
122    G.changeU(e2, n2);
123  } else {
124    G.changeV(e2, n2);
125  }
126
127  checkGraphNodeList(G, 4);
128  checkGraphEdgeList(G, 5);
129  checkGraphArcList(G, 10);
130
131  checkGraphIncEdgeArcLists(G, n1, 2);
132  checkGraphIncEdgeArcLists(G, n2, 3);
133  checkGraphIncEdgeArcLists(G, n3, 3);
134  checkGraphIncEdgeArcLists(G, n4, 2);
135
136  checkGraphConEdgeList(G, 5);
137  checkGraphConArcList(G, 10);
138
139  // Check contract()
140  G.contract(n1, n4, false);
141
142  checkGraphNodeList(G, 3);
143  checkGraphEdgeList(G, 5);
144  checkGraphArcList(G, 10);
145
146  checkGraphIncEdgeArcLists(G, n1, 4);
147  checkGraphIncEdgeArcLists(G, n2, 3);
148  checkGraphIncEdgeArcLists(G, n3, 3);
149
150  checkGraphConEdgeList(G, 5);
151  checkGraphConArcList(G, 10);
152
153  G.contract(n2, n3);
154
155  checkGraphNodeList(G, 2);
156  checkGraphEdgeList(G, 3);
157  checkGraphArcList(G, 6);
158
159  checkGraphIncEdgeArcLists(G, n1, 4);
160  checkGraphIncEdgeArcLists(G, n2, 2);
161
162  checkGraphConEdgeList(G, 3);
163  checkGraphConArcList(G, 6);
164}
165
166template <class Graph>
167void checkGraphErase() {
168  TEMPLATE_GRAPH_TYPEDEFS(Graph);
169
170  Graph G;
171  Node n1 = G.addNode(), n2 = G.addNode(),
172       n3 = G.addNode(), n4 = G.addNode();
173  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
174       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
175       e5 = G.addEdge(n4, n3);
176
177  // Check edge deletion
178  G.erase(e2);
179
180  checkGraphNodeList(G, 4);
181  checkGraphEdgeList(G, 4);
182  checkGraphArcList(G, 8);
183
184  checkGraphIncEdgeArcLists(G, n1, 2);
185  checkGraphIncEdgeArcLists(G, n2, 2);
186  checkGraphIncEdgeArcLists(G, n3, 2);
187  checkGraphIncEdgeArcLists(G, n4, 2);
188
189  checkGraphConEdgeList(G, 4);
190  checkGraphConArcList(G, 8);
191
192  // Check node deletion
193  G.erase(n3);
194
195  checkGraphNodeList(G, 3);
196  checkGraphEdgeList(G, 2);
197  checkGraphArcList(G, 4);
198
199  checkGraphIncEdgeArcLists(G, n1, 2);
200  checkGraphIncEdgeArcLists(G, n2, 1);
201  checkGraphIncEdgeArcLists(G, n4, 1);
202
203  checkGraphConEdgeList(G, 2);
204  checkGraphConArcList(G, 4);
205}
206
207
208template <class Graph>
209void checkGraphSnapshot() {
210  TEMPLATE_GRAPH_TYPEDEFS(Graph);
211
212  Graph G;
213  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
214  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
215       e3 = G.addEdge(n2, n3);
216
217  checkGraphNodeList(G, 3);
218  checkGraphEdgeList(G, 3);
219  checkGraphArcList(G, 6);
220
221  typename Graph::Snapshot snapshot(G);
222
223  Node n = G.addNode();
224  G.addEdge(n3, n);
225  G.addEdge(n, n3);
226  G.addEdge(n3, n2);
227
228  checkGraphNodeList(G, 4);
229  checkGraphEdgeList(G, 6);
230  checkGraphArcList(G, 12);
231
232  snapshot.restore();
233
234  checkGraphNodeList(G, 3);
235  checkGraphEdgeList(G, 3);
236  checkGraphArcList(G, 6);
237
238  checkGraphIncEdgeArcLists(G, n1, 2);
239  checkGraphIncEdgeArcLists(G, n2, 3);
240  checkGraphIncEdgeArcLists(G, n3, 1);
241
242  checkGraphConEdgeList(G, 3);
243  checkGraphConArcList(G, 6);
244
245  checkNodeIds(G);
246  checkEdgeIds(G);
247  checkArcIds(G);
248  checkGraphNodeMap(G);
249  checkGraphEdgeMap(G);
250  checkGraphArcMap(G);
251
252  G.addNode();
253  snapshot.save(G);
254
255  G.addEdge(G.addNode(), G.addNode());
256
257  snapshot.restore();
258
259  checkGraphNodeList(G, 4);
260  checkGraphEdgeList(G, 3);
261  checkGraphArcList(G, 6);
262}
263
264void checkConcepts() {
265  { // Checking graph components
266    checkConcept<BaseGraphComponent, BaseGraphComponent >();
267
268    checkConcept<IDableGraphComponent<>,
269      IDableGraphComponent<> >();
270
271    checkConcept<IterableGraphComponent<>,
272      IterableGraphComponent<> >();
273
274    checkConcept<MappableGraphComponent<>,
275      MappableGraphComponent<> >();
276  }
277  { // Checking skeleton graph
278    checkConcept<Graph, Graph>();
279  }
280  { // Checking ListGraph
281    checkConcept<Graph, ListGraph>();
282    checkConcept<AlterableGraphComponent<>, ListGraph>();
283    checkConcept<ExtendableGraphComponent<>, ListGraph>();
284    checkConcept<ClearableGraphComponent<>, ListGraph>();
285    checkConcept<ErasableGraphComponent<>, ListGraph>();
286  }
287  { // Checking SmartGraph
288    checkConcept<Graph, SmartGraph>();
289    checkConcept<AlterableGraphComponent<>, SmartGraph>();
290    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
291    checkConcept<ClearableGraphComponent<>, SmartGraph>();
292  }
293//  { // Checking FullGraph
294//    checkConcept<Graph, FullGraph>();
295//    checkGraphIterators<FullGraph>();
296//  }
297//  { // Checking GridGraph
298//    checkConcept<Graph, GridGraph>();
299//    checkGraphIterators<GridGraph>();
300//  }
301}
302
303template <typename Graph>
304void checkGraphValidity() {
305  TEMPLATE_GRAPH_TYPEDEFS(Graph);
306  Graph g;
307
308  Node
309    n1 = g.addNode(),
310    n2 = g.addNode(),
311    n3 = g.addNode();
312
313  Edge
314    e1 = g.addEdge(n1, n2),
315    e2 = g.addEdge(n2, n3);
316
317  check(g.valid(n1), "Wrong validity check");
318  check(g.valid(e1), "Wrong validity check");
319  check(g.valid(g.direct(e1, true)), "Wrong validity check");
320
321  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
322  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
323  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
324}
325
326template <typename Graph>
327void checkGraphValidityErase() {
328  TEMPLATE_GRAPH_TYPEDEFS(Graph);
329  Graph g;
330
331  Node
332    n1 = g.addNode(),
333    n2 = g.addNode(),
334    n3 = g.addNode();
335
336  Edge
337    e1 = g.addEdge(n1, n2),
338    e2 = g.addEdge(n2, n3);
339
340  check(g.valid(n1), "Wrong validity check");
341  check(g.valid(e1), "Wrong validity check");
342  check(g.valid(g.direct(e1, true)), "Wrong validity check");
343
344  g.erase(n1);
345
346  check(!g.valid(n1), "Wrong validity check");
347  check(g.valid(n2), "Wrong validity check");
348  check(g.valid(n3), "Wrong validity check");
349  check(!g.valid(e1), "Wrong validity check");
350  check(g.valid(e2), "Wrong validity check");
351
352  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
353  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
354  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
355}
356
357// void checkGridGraph(const GridGraph& g, int w, int h) {
358//   check(g.width() == w, "Wrong width");
359//   check(g.height() == h, "Wrong height");
360
361//   for (int i = 0; i < w; ++i) {
362//     for (int j = 0; j < h; ++j) {
363//       check(g.col(g(i, j)) == i, "Wrong col");
364//       check(g.row(g(i, j)) == j, "Wrong row");
365//     }
366//   }
367
368//   for (int i = 0; i < w; ++i) {
369//     for (int j = 0; j < h - 1; ++j) {
370//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
371//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
372//     }
373//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
374//   }
375
376//   for (int i = 0; i < w; ++i) {
377//     for (int j = 1; j < h; ++j) {
378//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
379//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
380//     }
381//     check(g.up(g(i, 0)) == INVALID, "Wrong up");
382//   }
383
384//   for (int j = 0; j < h; ++j) {
385//     for (int i = 0; i < w - 1; ++i) {
386//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
387//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
388//     }
389//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
390//   }
391
392//   for (int j = 0; j < h; ++j) {
393//     for (int i = 1; i < w; ++i) {
394//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
395//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
396//     }
397//     check(g.left(g(0, j)) == INVALID, "Wrong left");
398//   }
399// }
400
401void checkGraphs() {
402  { // Checking ListGraph
403    checkGraphBuild<ListGraph>();
404    checkGraphAlter<ListGraph>();
405    checkGraphErase<ListGraph>();
406    checkGraphSnapshot<ListGraph>();
407    checkGraphValidityErase<ListGraph>();
408  }
409  { // Checking SmartGraph
410    checkGraphBuild<SmartGraph>();
411    checkGraphSnapshot<SmartGraph>();
412    checkGraphValidity<SmartGraph>();
413  }
414//   { // Checking FullGraph
415//     FullGraph g(5);
416//     checkGraphNodeList(g, 5);
417//     checkGraphEdgeList(g, 10);
418//   }
419//   { // Checking GridGraph
420//     GridGraph g(5, 6);
421//     checkGraphNodeList(g, 30);
422//     checkGraphEdgeList(g, 49);
423//     checkGridGraph(g, 5, 6);
424//   }
425}
426
427int main() {
428  checkConcepts();
429  checkGraphs();
430  return 0;
431}
Note: See TracBrowser for help on using the repository browser.