COIN-OR::LEMON - Graph Library

source: lemon-main/test/digraph_test.cc @ 998:7fdaa05a69a1

Last change on this file since 998:7fdaa05a69a1 was 998:7fdaa05a69a1, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge #449 to branches >=1.2

File size: 13.5 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-2010
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  G.reserveNode(3);
40  G.reserveArc(4);
41
42  Node
43    n1 = G.addNode(),
44    n2 = G.addNode(),
45    n3 = G.addNode();
46  checkGraphNodeList(G, 3);
47  checkGraphArcList(G, 0);
48
49  Arc a1 = G.addArc(n1, n2);
50  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
51  checkGraphNodeList(G, 3);
52  checkGraphArcList(G, 1);
53
54  checkGraphOutArcList(G, n1, 1);
55  checkGraphOutArcList(G, n2, 0);
56  checkGraphOutArcList(G, n3, 0);
57
58  checkGraphInArcList(G, n1, 0);
59  checkGraphInArcList(G, n2, 1);
60  checkGraphInArcList(G, n3, 0);
61
62  checkGraphConArcList(G, 1);
63
64  Arc a2 = G.addArc(n2, n1),
65      a3 = G.addArc(n2, n3),
66      a4 = G.addArc(n2, n3);
67  ignore_unused_variable_warning(a2,a3,a4);
68
69  checkGraphNodeList(G, 3);
70  checkGraphArcList(G, 4);
71
72  checkGraphOutArcList(G, n1, 1);
73  checkGraphOutArcList(G, n2, 3);
74  checkGraphOutArcList(G, n3, 0);
75
76  checkGraphInArcList(G, n1, 1);
77  checkGraphInArcList(G, n2, 1);
78  checkGraphInArcList(G, n3, 2);
79
80  checkGraphConArcList(G, 4);
81
82  checkNodeIds(G);
83  checkArcIds(G);
84  checkGraphNodeMap(G);
85  checkGraphArcMap(G);
86}
87
88template <class Digraph>
89void checkDigraphSplit() {
90  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
91
92  Digraph G;
93  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
94  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
95      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
96  ignore_unused_variable_warning(a1,a2,a3,a4);
97
98  Node n4 = G.split(n2);
99
100  check(G.target(OutArcIt(G, n2)) == n4 &&
101        G.source(InArcIt(G, n4)) == n2,
102        "Wrong split.");
103
104  checkGraphNodeList(G, 4);
105  checkGraphArcList(G, 5);
106
107  checkGraphOutArcList(G, n1, 1);
108  checkGraphOutArcList(G, n2, 1);
109  checkGraphOutArcList(G, n3, 0);
110  checkGraphOutArcList(G, n4, 3);
111
112  checkGraphInArcList(G, n1, 1);
113  checkGraphInArcList(G, n2, 1);
114  checkGraphInArcList(G, n3, 2);
115  checkGraphInArcList(G, n4, 1);
116
117  checkGraphConArcList(G, 5);
118}
119
120template <class Digraph>
121void checkDigraphAlter() {
122  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
123
124  Digraph G;
125  Node n1 = G.addNode(), n2 = G.addNode(),
126       n3 = G.addNode(), n4 = G.addNode();
127  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
128      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
129      a5 = G.addArc(n2, n4);
130  ignore_unused_variable_warning(a1,a2,a3,a5);
131
132  checkGraphNodeList(G, 4);
133  checkGraphArcList(G, 5);
134
135  // Check changeSource() and changeTarget()
136  G.changeTarget(a4, n1);
137
138  checkGraphNodeList(G, 4);
139  checkGraphArcList(G, 5);
140
141  checkGraphOutArcList(G, n1, 1);
142  checkGraphOutArcList(G, n2, 1);
143  checkGraphOutArcList(G, n3, 0);
144  checkGraphOutArcList(G, n4, 3);
145
146  checkGraphInArcList(G, n1, 2);
147  checkGraphInArcList(G, n2, 1);
148  checkGraphInArcList(G, n3, 1);
149  checkGraphInArcList(G, n4, 1);
150
151  checkGraphConArcList(G, 5);
152
153  G.changeSource(a4, n3);
154
155  checkGraphNodeList(G, 4);
156  checkGraphArcList(G, 5);
157
158  checkGraphOutArcList(G, n1, 1);
159  checkGraphOutArcList(G, n2, 1);
160  checkGraphOutArcList(G, n3, 1);
161  checkGraphOutArcList(G, n4, 2);
162
163  checkGraphInArcList(G, n1, 2);
164  checkGraphInArcList(G, n2, 1);
165  checkGraphInArcList(G, n3, 1);
166  checkGraphInArcList(G, n4, 1);
167
168  checkGraphConArcList(G, 5);
169
170  // Check contract()
171  G.contract(n2, n4, false);
172
173  checkGraphNodeList(G, 3);
174  checkGraphArcList(G, 5);
175
176  checkGraphOutArcList(G, n1, 1);
177  checkGraphOutArcList(G, n2, 3);
178  checkGraphOutArcList(G, n3, 1);
179
180  checkGraphInArcList(G, n1, 2);
181  checkGraphInArcList(G, n2, 2);
182  checkGraphInArcList(G, n3, 1);
183
184  checkGraphConArcList(G, 5);
185
186  G.contract(n2, n1);
187
188  checkGraphNodeList(G, 2);
189  checkGraphArcList(G, 3);
190
191  checkGraphOutArcList(G, n2, 2);
192  checkGraphOutArcList(G, n3, 1);
193
194  checkGraphInArcList(G, n2, 2);
195  checkGraphInArcList(G, n3, 1);
196
197  checkGraphConArcList(G, 3);
198}
199
200template <class Digraph>
201void checkDigraphErase() {
202  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
203
204  Digraph G;
205  Node n1 = G.addNode(), n2 = G.addNode(),
206       n3 = G.addNode(), n4 = G.addNode();
207  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
208      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
209      a5 = G.addArc(n2, n4);
210  ignore_unused_variable_warning(a2,a3,a4,a5);
211
212  // Check arc deletion
213  G.erase(a1);
214
215  checkGraphNodeList(G, 4);
216  checkGraphArcList(G, 4);
217
218  checkGraphOutArcList(G, n1, 0);
219  checkGraphOutArcList(G, n2, 1);
220  checkGraphOutArcList(G, n3, 1);
221  checkGraphOutArcList(G, n4, 2);
222
223  checkGraphInArcList(G, n1, 2);
224  checkGraphInArcList(G, n2, 0);
225  checkGraphInArcList(G, n3, 1);
226  checkGraphInArcList(G, n4, 1);
227
228  checkGraphConArcList(G, 4);
229
230  // Check node deletion
231  G.erase(n4);
232
233  checkGraphNodeList(G, 3);
234  checkGraphArcList(G, 1);
235
236  checkGraphOutArcList(G, n1, 0);
237  checkGraphOutArcList(G, n2, 0);
238  checkGraphOutArcList(G, n3, 1);
239  checkGraphOutArcList(G, n4, 0);
240
241  checkGraphInArcList(G, n1, 1);
242  checkGraphInArcList(G, n2, 0);
243  checkGraphInArcList(G, n3, 0);
244  checkGraphInArcList(G, n4, 0);
245
246  checkGraphConArcList(G, 1);
247}
248
249
250template <class Digraph>
251void checkDigraphSnapshot() {
252  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
253
254  Digraph G;
255  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
256  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
257      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
258  ignore_unused_variable_warning(a1,a2,a3,a4);
259
260  typename Digraph::Snapshot snapshot(G);
261
262  Node n = G.addNode();
263  G.addArc(n3, n);
264  G.addArc(n, n3);
265
266  checkGraphNodeList(G, 4);
267  checkGraphArcList(G, 6);
268
269  snapshot.restore();
270
271  checkGraphNodeList(G, 3);
272  checkGraphArcList(G, 4);
273
274  checkGraphOutArcList(G, n1, 1);
275  checkGraphOutArcList(G, n2, 3);
276  checkGraphOutArcList(G, n3, 0);
277
278  checkGraphInArcList(G, n1, 1);
279  checkGraphInArcList(G, n2, 1);
280  checkGraphInArcList(G, n3, 2);
281
282  checkGraphConArcList(G, 4);
283
284  checkNodeIds(G);
285  checkArcIds(G);
286  checkGraphNodeMap(G);
287  checkGraphArcMap(G);
288
289  G.addNode();
290  snapshot.save(G);
291
292  G.addArc(G.addNode(), G.addNode());
293
294  snapshot.restore();
295  snapshot.save(G);
296
297  checkGraphNodeList(G, 4);
298  checkGraphArcList(G, 4);
299
300  G.addArc(G.addNode(), G.addNode());
301
302  snapshot.restore();
303
304  checkGraphNodeList(G, 4);
305  checkGraphArcList(G, 4);
306}
307
308void checkConcepts() {
309  { // Checking digraph components
310    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
311
312    checkConcept<IDableDigraphComponent<>,
313      IDableDigraphComponent<> >();
314
315    checkConcept<IterableDigraphComponent<>,
316      IterableDigraphComponent<> >();
317
318    checkConcept<MappableDigraphComponent<>,
319      MappableDigraphComponent<> >();
320  }
321  { // Checking skeleton digraph
322    checkConcept<Digraph, Digraph>();
323  }
324  { // Checking ListDigraph
325    checkConcept<Digraph, ListDigraph>();
326    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
327    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
328    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
329    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
330  }
331  { // Checking SmartDigraph
332    checkConcept<Digraph, SmartDigraph>();
333    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
334    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
335    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
336  }
337  { // Checking StaticDigraph
338    checkConcept<Digraph, StaticDigraph>();
339    checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
340  }
341  { // Checking FullDigraph
342    checkConcept<Digraph, FullDigraph>();
343  }
344}
345
346template <typename Digraph>
347void checkDigraphValidity() {
348  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
349  Digraph g;
350
351  Node
352    n1 = g.addNode(),
353    n2 = g.addNode(),
354    n3 = g.addNode();
355
356  Arc
357    e1 = g.addArc(n1, n2),
358    e2 = g.addArc(n2, n3);
359  ignore_unused_variable_warning(e2);
360
361  check(g.valid(n1), "Wrong validity check");
362  check(g.valid(e1), "Wrong validity check");
363
364  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
365  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
366}
367
368template <typename Digraph>
369void checkDigraphValidityErase() {
370  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
371  Digraph g;
372
373  Node
374    n1 = g.addNode(),
375    n2 = g.addNode(),
376    n3 = g.addNode();
377
378  Arc
379    e1 = g.addArc(n1, n2),
380    e2 = g.addArc(n2, n3);
381
382  check(g.valid(n1), "Wrong validity check");
383  check(g.valid(e1), "Wrong validity check");
384
385  g.erase(n1);
386
387  check(!g.valid(n1), "Wrong validity check");
388  check(g.valid(n2), "Wrong validity check");
389  check(g.valid(n3), "Wrong validity check");
390  check(!g.valid(e1), "Wrong validity check");
391  check(g.valid(e2), "Wrong validity check");
392
393  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
394  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
395}
396
397void checkStaticDigraph() {
398  SmartDigraph g;
399  SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
400  SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
401
402  StaticDigraph G;
403
404  checkGraphNodeList(G, 0);
405  checkGraphArcList(G, 0);
406
407  G.build(g, nref, aref);
408
409  checkGraphNodeList(G, 0);
410  checkGraphArcList(G, 0);
411
412  SmartDigraph::Node
413    n1 = g.addNode(),
414    n2 = g.addNode(),
415    n3 = g.addNode();
416
417  G.build(g, nref, aref);
418
419  checkGraphNodeList(G, 3);
420  checkGraphArcList(G, 0);
421
422  SmartDigraph::Arc a1 = g.addArc(n1, n2);
423
424  G.build(g, nref, aref);
425
426  check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
427        "Wrong arc or wrong references");
428  checkGraphNodeList(G, 3);
429  checkGraphArcList(G, 1);
430
431  checkGraphOutArcList(G, nref[n1], 1);
432  checkGraphOutArcList(G, nref[n2], 0);
433  checkGraphOutArcList(G, nref[n3], 0);
434
435  checkGraphInArcList(G, nref[n1], 0);
436  checkGraphInArcList(G, nref[n2], 1);
437  checkGraphInArcList(G, nref[n3], 0);
438
439  checkGraphConArcList(G, 1);
440
441  SmartDigraph::Arc
442    a2 = g.addArc(n2, n1),
443    a3 = g.addArc(n2, n3),
444    a4 = g.addArc(n2, n3);
445
446  digraphCopy(g, G).nodeRef(nref).run();
447
448  checkGraphNodeList(G, 3);
449  checkGraphArcList(G, 4);
450
451  checkGraphOutArcList(G, nref[n1], 1);
452  checkGraphOutArcList(G, nref[n2], 3);
453  checkGraphOutArcList(G, nref[n3], 0);
454
455  checkGraphInArcList(G, nref[n1], 1);
456  checkGraphInArcList(G, nref[n2], 1);
457  checkGraphInArcList(G, nref[n3], 2);
458
459  checkGraphConArcList(G, 4);
460
461  std::vector<std::pair<int,int> > arcs;
462  arcs.push_back(std::make_pair(0,1));
463  arcs.push_back(std::make_pair(0,2));
464  arcs.push_back(std::make_pair(1,3));
465  arcs.push_back(std::make_pair(1,2));
466  arcs.push_back(std::make_pair(3,0));
467  arcs.push_back(std::make_pair(3,3));
468  arcs.push_back(std::make_pair(4,2));
469  arcs.push_back(std::make_pair(4,3));
470  arcs.push_back(std::make_pair(4,1));
471
472  G.build(6, arcs.begin(), arcs.end());
473
474  checkGraphNodeList(G, 6);
475  checkGraphArcList(G, 9);
476
477  checkGraphOutArcList(G, G.node(0), 2);
478  checkGraphOutArcList(G, G.node(1), 2);
479  checkGraphOutArcList(G, G.node(2), 0);
480  checkGraphOutArcList(G, G.node(3), 2);
481  checkGraphOutArcList(G, G.node(4), 3);
482  checkGraphOutArcList(G, G.node(5), 0);
483
484  checkGraphInArcList(G, G.node(0), 1);
485  checkGraphInArcList(G, G.node(1), 2);
486  checkGraphInArcList(G, G.node(2), 3);
487  checkGraphInArcList(G, G.node(3), 3);
488  checkGraphInArcList(G, G.node(4), 0);
489  checkGraphInArcList(G, G.node(5), 0);
490
491  checkGraphConArcList(G, 9);
492
493  checkNodeIds(G);
494  checkArcIds(G);
495  checkGraphNodeMap(G);
496  checkGraphArcMap(G);
497
498  int n = G.nodeNum();
499  int m = G.arcNum();
500  check(G.index(G.node(n-1)) == n-1, "Wrong index.");
501  check(G.index(G.arc(m-1)) == m-1, "Wrong index.");
502}
503
504void checkFullDigraph(int num) {
505  typedef FullDigraph Digraph;
506  DIGRAPH_TYPEDEFS(Digraph);
507
508  Digraph G(num);
509  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
510
511  G.resize(num);
512  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
513
514  checkGraphNodeList(G, num);
515  checkGraphArcList(G, num * num);
516
517  for (NodeIt n(G); n != INVALID; ++n) {
518    checkGraphOutArcList(G, n, num);
519    checkGraphInArcList(G, n, num);
520  }
521
522  checkGraphConArcList(G, num * num);
523
524  checkNodeIds(G);
525  checkArcIds(G);
526  checkGraphNodeMap(G);
527  checkGraphArcMap(G);
528
529  for (int i = 0; i < G.nodeNum(); ++i) {
530    check(G.index(G(i)) == i, "Wrong index");
531  }
532
533  for (NodeIt s(G); s != INVALID; ++s) {
534    for (NodeIt t(G); t != INVALID; ++t) {
535      Arc a = G.arc(s, t);
536      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
537    }
538  }
539}
540
541void checkDigraphs() {
542  { // Checking ListDigraph
543    checkDigraphBuild<ListDigraph>();
544    checkDigraphSplit<ListDigraph>();
545    checkDigraphAlter<ListDigraph>();
546    checkDigraphErase<ListDigraph>();
547    checkDigraphSnapshot<ListDigraph>();
548    checkDigraphValidityErase<ListDigraph>();
549  }
550  { // Checking SmartDigraph
551    checkDigraphBuild<SmartDigraph>();
552    checkDigraphSplit<SmartDigraph>();
553    checkDigraphSnapshot<SmartDigraph>();
554    checkDigraphValidity<SmartDigraph>();
555  }
556  { // Checking StaticDigraph
557    checkStaticDigraph();
558  }
559  { // Checking FullDigraph
560    checkFullDigraph(8);
561  }
562}
563
564int main() {
565  checkDigraphs();
566  checkConcepts();
567  return 0;
568}
Note: See TracBrowser for help on using the repository browser.