COIN-OR::LEMON - Graph Library

source: lemon-1.0/test/digraph_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: 9.4 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/digraph.h>
20#include <lemon/list_graph.h>
21#include <lemon/smart_graph.h>
22//#include <lemon/full_graph.h>
23//#include <lemon/hypercube_graph.h>
24
25#include "test_tools.h"
26#include "graph_test.h"
27
28using namespace lemon;
29using namespace lemon::concepts;
30
31template <class Digraph>
32void checkDigraphBuild() {
33  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
34  Digraph G;
35
36  checkGraphNodeList(G, 0);
37  checkGraphArcList(G, 0);
38
39  Node
40    n1 = G.addNode(),
41    n2 = G.addNode(),
42    n3 = G.addNode();
43  checkGraphNodeList(G, 3);
44  checkGraphArcList(G, 0);
45
46  Arc a1 = G.addArc(n1, n2);
47  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
48  checkGraphNodeList(G, 3);
49  checkGraphArcList(G, 1);
50
51  checkGraphOutArcList(G, n1, 1);
52  checkGraphOutArcList(G, n2, 0);
53  checkGraphOutArcList(G, n3, 0);
54
55  checkGraphInArcList(G, n1, 0);
56  checkGraphInArcList(G, n2, 1);
57  checkGraphInArcList(G, n3, 0);
58
59  checkGraphConArcList(G, 1);
60
61  Arc a2 = G.addArc(n2, n1),
62      a3 = G.addArc(n2, n3),
63      a4 = G.addArc(n2, n3);
64
65  checkGraphNodeList(G, 3);
66  checkGraphArcList(G, 4);
67
68  checkGraphOutArcList(G, n1, 1);
69  checkGraphOutArcList(G, n2, 3);
70  checkGraphOutArcList(G, n3, 0);
71
72  checkGraphInArcList(G, n1, 1);
73  checkGraphInArcList(G, n2, 1);
74  checkGraphInArcList(G, n3, 2);
75
76  checkGraphConArcList(G, 4);
77
78  checkNodeIds(G);
79  checkArcIds(G);
80  checkGraphNodeMap(G);
81  checkGraphArcMap(G);
82}
83
84template <class Digraph>
85void checkDigraphSplit() {
86  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
87
88  Digraph G;
89  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
90  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
91      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
92
93  Node n4 = G.split(n2);
94
95  check(G.target(OutArcIt(G, n2)) == n4 &&
96        G.source(InArcIt(G, n4)) == n2,
97        "Wrong split.");
98
99  checkGraphNodeList(G, 4);
100  checkGraphArcList(G, 5);
101
102  checkGraphOutArcList(G, n1, 1);
103  checkGraphOutArcList(G, n2, 1);
104  checkGraphOutArcList(G, n3, 0);
105  checkGraphOutArcList(G, n4, 3);
106
107  checkGraphInArcList(G, n1, 1);
108  checkGraphInArcList(G, n2, 1);
109  checkGraphInArcList(G, n3, 2);
110  checkGraphInArcList(G, n4, 1);
111
112  checkGraphConArcList(G, 5);
113}
114
115template <class Digraph>
116void checkDigraphAlter() {
117  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
118
119  Digraph G;
120  Node n1 = G.addNode(), n2 = G.addNode(),
121       n3 = G.addNode(), n4 = G.addNode();
122  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
123      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
124      a5 = G.addArc(n2, n4);
125
126  checkGraphNodeList(G, 4);
127  checkGraphArcList(G, 5);
128
129  // Check changeSource() and changeTarget()
130  G.changeTarget(a4, n1);
131
132  checkGraphNodeList(G, 4);
133  checkGraphArcList(G, 5);
134
135  checkGraphOutArcList(G, n1, 1);
136  checkGraphOutArcList(G, n2, 1);
137  checkGraphOutArcList(G, n3, 0);
138  checkGraphOutArcList(G, n4, 3);
139
140  checkGraphInArcList(G, n1, 2);
141  checkGraphInArcList(G, n2, 1);
142  checkGraphInArcList(G, n3, 1);
143  checkGraphInArcList(G, n4, 1);
144
145  checkGraphConArcList(G, 5);
146
147  G.changeSource(a4, n3);
148
149  checkGraphNodeList(G, 4);
150  checkGraphArcList(G, 5);
151
152  checkGraphOutArcList(G, n1, 1);
153  checkGraphOutArcList(G, n2, 1);
154  checkGraphOutArcList(G, n3, 1);
155  checkGraphOutArcList(G, n4, 2);
156
157  checkGraphInArcList(G, n1, 2);
158  checkGraphInArcList(G, n2, 1);
159  checkGraphInArcList(G, n3, 1);
160  checkGraphInArcList(G, n4, 1);
161
162  checkGraphConArcList(G, 5);
163
164  // Check contract()
165  G.contract(n2, n4, false);
166
167  checkGraphNodeList(G, 3);
168  checkGraphArcList(G, 5);
169
170  checkGraphOutArcList(G, n1, 1);
171  checkGraphOutArcList(G, n2, 3);
172  checkGraphOutArcList(G, n3, 1);
173
174  checkGraphInArcList(G, n1, 2);
175  checkGraphInArcList(G, n2, 2);
176  checkGraphInArcList(G, n3, 1);
177
178  checkGraphConArcList(G, 5);
179
180  G.contract(n2, n1);
181
182  checkGraphNodeList(G, 2);
183  checkGraphArcList(G, 3);
184
185  checkGraphOutArcList(G, n2, 2);
186  checkGraphOutArcList(G, n3, 1);
187
188  checkGraphInArcList(G, n2, 2);
189  checkGraphInArcList(G, n3, 1);
190
191  checkGraphConArcList(G, 3);
192}
193
194template <class Digraph>
195void checkDigraphErase() {
196  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
197
198  Digraph G;
199  Node n1 = G.addNode(), n2 = G.addNode(),
200       n3 = G.addNode(), n4 = G.addNode();
201  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
202      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
203      a5 = G.addArc(n2, n4);
204
205  // Check arc deletion
206  G.erase(a1);
207
208  checkGraphNodeList(G, 4);
209  checkGraphArcList(G, 4);
210
211  checkGraphOutArcList(G, n1, 0);
212  checkGraphOutArcList(G, n2, 1);
213  checkGraphOutArcList(G, n3, 1);
214  checkGraphOutArcList(G, n4, 2);
215
216  checkGraphInArcList(G, n1, 2);
217  checkGraphInArcList(G, n2, 0);
218  checkGraphInArcList(G, n3, 1);
219  checkGraphInArcList(G, n4, 1);
220
221  checkGraphConArcList(G, 4);
222
223  // Check node deletion
224  G.erase(n4);
225
226  checkGraphNodeList(G, 3);
227  checkGraphArcList(G, 1);
228
229  checkGraphOutArcList(G, n1, 0);
230  checkGraphOutArcList(G, n2, 0);
231  checkGraphOutArcList(G, n3, 1);
232  checkGraphOutArcList(G, n4, 0);
233
234  checkGraphInArcList(G, n1, 1);
235  checkGraphInArcList(G, n2, 0);
236  checkGraphInArcList(G, n3, 0);
237  checkGraphInArcList(G, n4, 0);
238
239  checkGraphConArcList(G, 1);
240}
241
242
243template <class Digraph>
244void checkDigraphSnapshot() {
245  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
246
247  Digraph G;
248  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
249  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
250      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
251
252  typename Digraph::Snapshot snapshot(G);
253
254  Node n = G.addNode();
255  G.addArc(n3, n);
256  G.addArc(n, n3);
257
258  checkGraphNodeList(G, 4);
259  checkGraphArcList(G, 6);
260
261  snapshot.restore();
262
263  checkGraphNodeList(G, 3);
264  checkGraphArcList(G, 4);
265
266  checkGraphOutArcList(G, n1, 1);
267  checkGraphOutArcList(G, n2, 3);
268  checkGraphOutArcList(G, n3, 0);
269
270  checkGraphInArcList(G, n1, 1);
271  checkGraphInArcList(G, n2, 1);
272  checkGraphInArcList(G, n3, 2);
273
274  checkGraphConArcList(G, 4);
275
276  checkNodeIds(G);
277  checkArcIds(G);
278  checkGraphNodeMap(G);
279  checkGraphArcMap(G);
280
281  G.addNode();
282  snapshot.save(G);
283
284  G.addArc(G.addNode(), G.addNode());
285
286  snapshot.restore();
287
288  checkGraphNodeList(G, 4);
289  checkGraphArcList(G, 4);
290}
291
292void checkConcepts() {
293  { // Checking digraph components
294    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
295
296    checkConcept<IDableDigraphComponent<>,
297      IDableDigraphComponent<> >();
298
299    checkConcept<IterableDigraphComponent<>,
300      IterableDigraphComponent<> >();
301
302    checkConcept<MappableDigraphComponent<>,
303      MappableDigraphComponent<> >();
304  }
305  { // Checking skeleton digraph
306    checkConcept<Digraph, Digraph>();
307  }
308  { // Checking ListDigraph
309    checkConcept<Digraph, ListDigraph>();
310    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
311    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
312    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
313    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
314  }
315  { // Checking SmartDigraph
316    checkConcept<Digraph, SmartDigraph>();
317    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
318    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
319    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
320  }
321//  { // Checking FullDigraph
322//    checkConcept<Digraph, FullDigraph>();
323//  }
324//  { // Checking HyperCubeDigraph
325//    checkConcept<Digraph, HyperCubeDigraph>();
326//  }
327}
328
329template <typename Digraph>
330void checkDigraphValidity() {
331  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
332  Digraph g;
333
334  Node
335    n1 = g.addNode(),
336    n2 = g.addNode(),
337    n3 = g.addNode();
338
339  Arc
340    e1 = g.addArc(n1, n2),
341    e2 = g.addArc(n2, n3);
342
343  check(g.valid(n1), "Wrong validity check");
344  check(g.valid(e1), "Wrong validity check");
345
346  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
347  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
348}
349
350template <typename Digraph>
351void checkDigraphValidityErase() {
352  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
353  Digraph g;
354
355  Node
356    n1 = g.addNode(),
357    n2 = g.addNode(),
358    n3 = g.addNode();
359
360  Arc
361    e1 = g.addArc(n1, n2),
362    e2 = g.addArc(n2, n3);
363
364  check(g.valid(n1), "Wrong validity check");
365  check(g.valid(e1), "Wrong validity check");
366
367  g.erase(n1);
368
369  check(!g.valid(n1), "Wrong validity check");
370  check(g.valid(n2), "Wrong validity check");
371  check(g.valid(n3), "Wrong validity check");
372  check(!g.valid(e1), "Wrong validity check");
373  check(g.valid(e2), "Wrong validity check");
374
375  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
376  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
377}
378
379void checkDigraphs() {
380  { // Checking ListDigraph
381    checkDigraphBuild<ListDigraph>();
382    checkDigraphSplit<ListDigraph>();
383    checkDigraphAlter<ListDigraph>();
384    checkDigraphErase<ListDigraph>();
385    checkDigraphSnapshot<ListDigraph>();
386    checkDigraphValidityErase<ListDigraph>();
387  }
388  { // Checking SmartDigraph
389    checkDigraphBuild<SmartDigraph>();
390    checkDigraphSplit<SmartDigraph>();
391    checkDigraphSnapshot<SmartDigraph>();
392    checkDigraphValidity<SmartDigraph>();
393  }
394}
395
396int main() {
397  checkDigraphs();
398  checkConcepts();
399  return 0;
400}
Note: See TracBrowser for help on using the repository browser.