COIN-OR::LEMON - Graph Library

source: lemon-main/test/digraph_test.cc @ 1116:07cd9a2d20e0

Last change on this file since 1116:07cd9a2d20e0 was 1092:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

File size: 13.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-2013
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  ::lemon::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  ::lemon::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  ::lemon::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  ::lemon::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  ::lemon::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  ::lemon::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  ::lemon::ignore_unused_variable_warning(a2,a3,a4);
446
447  digraphCopy(g, G).nodeRef(nref).run();
448
449  checkGraphNodeList(G, 3);
450  checkGraphArcList(G, 4);
451
452  checkGraphOutArcList(G, nref[n1], 1);
453  checkGraphOutArcList(G, nref[n2], 3);
454  checkGraphOutArcList(G, nref[n3], 0);
455
456  checkGraphInArcList(G, nref[n1], 1);
457  checkGraphInArcList(G, nref[n2], 1);
458  checkGraphInArcList(G, nref[n3], 2);
459
460  checkGraphConArcList(G, 4);
461
462  std::vector<std::pair<int,int> > arcs;
463  arcs.push_back(std::make_pair(0,1));
464  arcs.push_back(std::make_pair(0,2));
465  arcs.push_back(std::make_pair(1,3));
466  arcs.push_back(std::make_pair(1,2));
467  arcs.push_back(std::make_pair(3,0));
468  arcs.push_back(std::make_pair(3,3));
469  arcs.push_back(std::make_pair(4,2));
470  arcs.push_back(std::make_pair(4,3));
471  arcs.push_back(std::make_pair(4,1));
472
473  G.build(6, arcs.begin(), arcs.end());
474
475  checkGraphNodeList(G, 6);
476  checkGraphArcList(G, 9);
477
478  checkGraphOutArcList(G, G.node(0), 2);
479  checkGraphOutArcList(G, G.node(1), 2);
480  checkGraphOutArcList(G, G.node(2), 0);
481  checkGraphOutArcList(G, G.node(3), 2);
482  checkGraphOutArcList(G, G.node(4), 3);
483  checkGraphOutArcList(G, G.node(5), 0);
484
485  checkGraphInArcList(G, G.node(0), 1);
486  checkGraphInArcList(G, G.node(1), 2);
487  checkGraphInArcList(G, G.node(2), 3);
488  checkGraphInArcList(G, G.node(3), 3);
489  checkGraphInArcList(G, G.node(4), 0);
490  checkGraphInArcList(G, G.node(5), 0);
491
492  checkGraphConArcList(G, 9);
493
494  checkNodeIds(G);
495  checkArcIds(G);
496  checkGraphNodeMap(G);
497  checkGraphArcMap(G);
498
499  int n = G.nodeNum();
500  int m = G.arcNum();
501  check(G.index(G.node(n-1)) == n-1, "Wrong index.");
502  check(G.index(G.arc(m-1)) == m-1, "Wrong index.");
503}
504
505void checkFullDigraph(int num) {
506  typedef FullDigraph Digraph;
507  DIGRAPH_TYPEDEFS(Digraph);
508
509  Digraph G(num);
510  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
511
512  G.resize(num);
513  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
514
515  checkGraphNodeList(G, num);
516  checkGraphArcList(G, num * num);
517
518  for (NodeIt n(G); n != INVALID; ++n) {
519    checkGraphOutArcList(G, n, num);
520    checkGraphInArcList(G, n, num);
521  }
522
523  checkGraphConArcList(G, num * num);
524
525  checkNodeIds(G);
526  checkArcIds(G);
527  checkGraphNodeMap(G);
528  checkGraphArcMap(G);
529
530  for (int i = 0; i < G.nodeNum(); ++i) {
531    check(G.index(G(i)) == i, "Wrong index");
532  }
533
534  for (NodeIt s(G); s != INVALID; ++s) {
535    for (NodeIt t(G); t != INVALID; ++t) {
536      Arc a = G.arc(s, t);
537      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
538    }
539  }
540}
541
542void checkDigraphs() {
543  { // Checking ListDigraph
544    checkDigraphBuild<ListDigraph>();
545    checkDigraphSplit<ListDigraph>();
546    checkDigraphAlter<ListDigraph>();
547    checkDigraphErase<ListDigraph>();
548    checkDigraphSnapshot<ListDigraph>();
549    checkDigraphValidityErase<ListDigraph>();
550  }
551  { // Checking SmartDigraph
552    checkDigraphBuild<SmartDigraph>();
553    checkDigraphSplit<SmartDigraph>();
554    checkDigraphSnapshot<SmartDigraph>();
555    checkDigraphValidity<SmartDigraph>();
556  }
557  { // Checking StaticDigraph
558    checkStaticDigraph();
559  }
560  { // Checking FullDigraph
561    checkFullDigraph(8);
562  }
563}
564
565int main() {
566  checkDigraphs();
567  checkConcepts();
568  return 0;
569}
Note: See TracBrowser for help on using the repository browser.