COIN-OR::LEMON - Graph Library

source: lemon/test/digraph_test.cc @ 1419:73bd8d5200df

Last change on this file since 1419:73bd8d5200df was 1419:73bd8d5200df, checked in by Gabriel Gouvine <gabriel.gouvine.GIT@…>, 3 years ago

CompactDigraph? implementation (#377)

Smaller version of StaticDigraph? (n+m) if InArcIt? is not needed

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