COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/digraph_test.cc @ 857:abb95d48e89e

Last change on this file since 857:abb95d48e89e was 780:580af8cf2f6a, checked in by Alpar Juttner <alpar@…>, 14 years ago

Merge #68 (Port static graph implementation)

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