COIN-OR::LEMON - Graph Library

source: lemon/test/digraph_test.cc @ 823:eff1caf6d32e

Last change on this file since 823:eff1caf6d32e was 823:eff1caf6d32e, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Extend the interface of StaticDigraph? (#68)
with index(), arc() and node() functions similarly to
other static graph structures.

File size: 11.9 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/static_graph.h>
23#include <lemon/full_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 StaticDigraph
322    checkConcept<Digraph, StaticDigraph>();
323    checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
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
344  check(g.valid(n1), "Wrong validity check");
345  check(g.valid(e1), "Wrong validity check");
346
347  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
348  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
349}
350
351template <typename Digraph>
352void checkDigraphValidityErase() {
353  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
354  Digraph g;
355
356  Node
357    n1 = g.addNode(),
358    n2 = g.addNode(),
359    n3 = g.addNode();
360
361  Arc
362    e1 = g.addArc(n1, n2),
363    e2 = g.addArc(n2, n3);
364
365  check(g.valid(n1), "Wrong validity check");
366  check(g.valid(e1), "Wrong validity check");
367
368  g.erase(n1);
369
370  check(!g.valid(n1), "Wrong validity check");
371  check(g.valid(n2), "Wrong validity check");
372  check(g.valid(n3), "Wrong validity check");
373  check(!g.valid(e1), "Wrong validity check");
374  check(g.valid(e2), "Wrong validity check");
375
376  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
377  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
378}
379
380void checkStaticDigraph() {
381  SmartDigraph g;
382  SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
383  SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
384 
385  StaticDigraph G;
386 
387  checkGraphNodeList(G, 0);
388  checkGraphArcList(G, 0);
389
390  G.build(g, nref, aref);
391
392  checkGraphNodeList(G, 0);
393  checkGraphArcList(G, 0);
394
395  SmartDigraph::Node
396    n1 = g.addNode(),
397    n2 = g.addNode(),
398    n3 = g.addNode();
399
400  G.build(g, nref, aref);
401
402  checkGraphNodeList(G, 3);
403  checkGraphArcList(G, 0);
404
405  SmartDigraph::Arc a1 = g.addArc(n1, n2);
406
407  G.build(g, nref, aref);
408
409  check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
410        "Wrong arc or wrong references");
411  checkGraphNodeList(G, 3);
412  checkGraphArcList(G, 1);
413
414  checkGraphOutArcList(G, nref[n1], 1);
415  checkGraphOutArcList(G, nref[n2], 0);
416  checkGraphOutArcList(G, nref[n3], 0);
417
418  checkGraphInArcList(G, nref[n1], 0);
419  checkGraphInArcList(G, nref[n2], 1);
420  checkGraphInArcList(G, nref[n3], 0);
421
422  checkGraphConArcList(G, 1);
423
424  SmartDigraph::Arc
425    a2 = g.addArc(n2, n1),
426    a3 = g.addArc(n2, n3),
427    a4 = g.addArc(n2, n3);
428
429  digraphCopy(g, G).nodeRef(nref).run();
430
431  checkGraphNodeList(G, 3);
432  checkGraphArcList(G, 4);
433
434  checkGraphOutArcList(G, nref[n1], 1);
435  checkGraphOutArcList(G, nref[n2], 3);
436  checkGraphOutArcList(G, nref[n3], 0);
437
438  checkGraphInArcList(G, nref[n1], 1);
439  checkGraphInArcList(G, nref[n2], 1);
440  checkGraphInArcList(G, nref[n3], 2);
441
442  checkGraphConArcList(G, 4);
443
444  checkNodeIds(G);
445  checkArcIds(G);
446  checkGraphNodeMap(G);
447  checkGraphArcMap(G);
448 
449  int n = G.nodeNum();
450  int m = G.arcNum();
451  check(G.index(G.node(n-1)) == n-1, "Wrong index.");
452  check(G.index(G.arc(m-1)) == m-1, "Wrong index.");
453}
454
455void checkFullDigraph(int num) {
456  typedef FullDigraph Digraph;
457  DIGRAPH_TYPEDEFS(Digraph);
458  Digraph G(num);
459
460  checkGraphNodeList(G, num);
461  checkGraphArcList(G, num * num);
462
463  for (NodeIt n(G); n != INVALID; ++n) {
464    checkGraphOutArcList(G, n, num);
465    checkGraphInArcList(G, n, num);
466  }
467
468  checkGraphConArcList(G, num * num);
469
470  checkNodeIds(G);
471  checkArcIds(G);
472  checkGraphNodeMap(G);
473  checkGraphArcMap(G);
474
475  for (int i = 0; i < G.nodeNum(); ++i) {
476    check(G.index(G(i)) == i, "Wrong index");
477  }
478
479  for (NodeIt s(G); s != INVALID; ++s) {
480    for (NodeIt t(G); t != INVALID; ++t) {
481      Arc a = G.arc(s, t);
482      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
483    }
484  }
485}
486
487void checkDigraphs() {
488  { // Checking ListDigraph
489    checkDigraphBuild<ListDigraph>();
490    checkDigraphSplit<ListDigraph>();
491    checkDigraphAlter<ListDigraph>();
492    checkDigraphErase<ListDigraph>();
493    checkDigraphSnapshot<ListDigraph>();
494    checkDigraphValidityErase<ListDigraph>();
495  }
496  { // Checking SmartDigraph
497    checkDigraphBuild<SmartDigraph>();
498    checkDigraphSplit<SmartDigraph>();
499    checkDigraphSnapshot<SmartDigraph>();
500    checkDigraphValidity<SmartDigraph>();
501  }
502  { // Checking StaticDigraph
503    checkStaticDigraph();
504  }
505  { // Checking FullDigraph
506    checkFullDigraph(8);
507  }
508}
509
510int main() {
511  checkDigraphs();
512  checkConcepts();
513  return 0;
514}
Note: See TracBrowser for help on using the repository browser.