COIN-OR::LEMON - Graph Library

source: lemon-main/test/digraph_test.cc @ 1007:7e368d9b67f7

Last change on this file since 1007:7e368d9b67f7 was 997:761fe0846f49, checked in by Alpar Juttner <alpar@…>, 12 years ago

Fix clang compilation warnings and errors (#449)

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