COIN-OR::LEMON - Graph Library

source: lemon-main/test/digraph_test.cc @ 777:5764dd9b6e18

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

Add a new build() function to StaticDigraph? (#68)

This function builds the digraph from an arc list that
contains pairs of integer indices from the range [0..n-1].
It is useful in the cases when you would like to build a
StaticDigraph? from scratch, i.e. you do not want to build
another digraph that can be copied using the other build()
function.

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