COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-main/test/digraph_test.cc @ 882:ece1f8a3052d

Last change on this file since 882:ece1f8a3052d was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 16 years ago

Happy New Year again

  • update the copyright headers + run the source unifier
File size: 10.0 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/full_graph.h>
23
24#include "test_tools.h"
25#include "graph_test.h"
26
27using namespace lemon;
28using namespace lemon::concepts;
29
30template <class Digraph>
31void checkDigraphBuild() {
32  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
33  Digraph G;
34
35  checkGraphNodeList(G, 0);
36  checkGraphArcList(G, 0);
37
38  Node
39    n1 = G.addNode(),
40    n2 = G.addNode(),
41    n3 = G.addNode();
42  checkGraphNodeList(G, 3);
43  checkGraphArcList(G, 0);
44
45  Arc a1 = G.addArc(n1, n2);
46  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
47  checkGraphNodeList(G, 3);
48  checkGraphArcList(G, 1);
49
50  checkGraphOutArcList(G, n1, 1);
51  checkGraphOutArcList(G, n2, 0);
52  checkGraphOutArcList(G, n3, 0);
53
54  checkGraphInArcList(G, n1, 0);
55  checkGraphInArcList(G, n2, 1);
56  checkGraphInArcList(G, n3, 0);
57
58  checkGraphConArcList(G, 1);
59
60  Arc a2 = G.addArc(n2, n1),
61      a3 = G.addArc(n2, n3),
62      a4 = G.addArc(n2, n3);
63
64  checkGraphNodeList(G, 3);
65  checkGraphArcList(G, 4);
66
67  checkGraphOutArcList(G, n1, 1);
68  checkGraphOutArcList(G, n2, 3);
69  checkGraphOutArcList(G, n3, 0);
70
71  checkGraphInArcList(G, n1, 1);
72  checkGraphInArcList(G, n2, 1);
73  checkGraphInArcList(G, n3, 2);
74
75  checkGraphConArcList(G, 4);
76
77  checkNodeIds(G);
78  checkArcIds(G);
79  checkGraphNodeMap(G);
80  checkGraphArcMap(G);
81}
82
83template <class Digraph>
84void checkDigraphSplit() {
85  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
86
87  Digraph G;
88  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
89  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
90      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
91
92  Node n4 = G.split(n2);
93
94  check(G.target(OutArcIt(G, n2)) == n4 &&
95        G.source(InArcIt(G, n4)) == n2,
96        "Wrong split.");
97
98  checkGraphNodeList(G, 4);
99  checkGraphArcList(G, 5);
100
101  checkGraphOutArcList(G, n1, 1);
102  checkGraphOutArcList(G, n2, 1);
103  checkGraphOutArcList(G, n3, 0);
104  checkGraphOutArcList(G, n4, 3);
105
106  checkGraphInArcList(G, n1, 1);
107  checkGraphInArcList(G, n2, 1);
108  checkGraphInArcList(G, n3, 2);
109  checkGraphInArcList(G, n4, 1);
110
111  checkGraphConArcList(G, 5);
112}
113
114template <class Digraph>
115void checkDigraphAlter() {
116  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
117
118  Digraph G;
119  Node n1 = G.addNode(), n2 = G.addNode(),
120       n3 = G.addNode(), n4 = G.addNode();
121  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
122      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
123      a5 = G.addArc(n2, n4);
124
125  checkGraphNodeList(G, 4);
126  checkGraphArcList(G, 5);
127
128  // Check changeSource() and changeTarget()
129  G.changeTarget(a4, n1);
130
131  checkGraphNodeList(G, 4);
132  checkGraphArcList(G, 5);
133
134  checkGraphOutArcList(G, n1, 1);
135  checkGraphOutArcList(G, n2, 1);
136  checkGraphOutArcList(G, n3, 0);
137  checkGraphOutArcList(G, n4, 3);
138
139  checkGraphInArcList(G, n1, 2);
140  checkGraphInArcList(G, n2, 1);
141  checkGraphInArcList(G, n3, 1);
142  checkGraphInArcList(G, n4, 1);
143
144  checkGraphConArcList(G, 5);
145
146  G.changeSource(a4, n3);
147
148  checkGraphNodeList(G, 4);
149  checkGraphArcList(G, 5);
150
151  checkGraphOutArcList(G, n1, 1);
152  checkGraphOutArcList(G, n2, 1);
153  checkGraphOutArcList(G, n3, 1);
154  checkGraphOutArcList(G, n4, 2);
155
156  checkGraphInArcList(G, n1, 2);
157  checkGraphInArcList(G, n2, 1);
158  checkGraphInArcList(G, n3, 1);
159  checkGraphInArcList(G, n4, 1);
160
161  checkGraphConArcList(G, 5);
162
163  // Check contract()
164  G.contract(n2, n4, false);
165
166  checkGraphNodeList(G, 3);
167  checkGraphArcList(G, 5);
168
169  checkGraphOutArcList(G, n1, 1);
170  checkGraphOutArcList(G, n2, 3);
171  checkGraphOutArcList(G, n3, 1);
172
173  checkGraphInArcList(G, n1, 2);
174  checkGraphInArcList(G, n2, 2);
175  checkGraphInArcList(G, n3, 1);
176
177  checkGraphConArcList(G, 5);
178
179  G.contract(n2, n1);
180
181  checkGraphNodeList(G, 2);
182  checkGraphArcList(G, 3);
183
184  checkGraphOutArcList(G, n2, 2);
185  checkGraphOutArcList(G, n3, 1);
186
187  checkGraphInArcList(G, n2, 2);
188  checkGraphInArcList(G, n3, 1);
189
190  checkGraphConArcList(G, 3);
191}
192
193template <class Digraph>
194void checkDigraphErase() {
195  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
196
197  Digraph G;
198  Node n1 = G.addNode(), n2 = G.addNode(),
199       n3 = G.addNode(), n4 = G.addNode();
200  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
201      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
202      a5 = G.addArc(n2, n4);
203
204  // Check arc deletion
205  G.erase(a1);
206
207  checkGraphNodeList(G, 4);
208  checkGraphArcList(G, 4);
209
210  checkGraphOutArcList(G, n1, 0);
211  checkGraphOutArcList(G, n2, 1);
212  checkGraphOutArcList(G, n3, 1);
213  checkGraphOutArcList(G, n4, 2);
214
215  checkGraphInArcList(G, n1, 2);
216  checkGraphInArcList(G, n2, 0);
217  checkGraphInArcList(G, n3, 1);
218  checkGraphInArcList(G, n4, 1);
219
220  checkGraphConArcList(G, 4);
221
222  // Check node deletion
223  G.erase(n4);
224
225  checkGraphNodeList(G, 3);
226  checkGraphArcList(G, 1);
227
228  checkGraphOutArcList(G, n1, 0);
229  checkGraphOutArcList(G, n2, 0);
230  checkGraphOutArcList(G, n3, 1);
231  checkGraphOutArcList(G, n4, 0);
232
233  checkGraphInArcList(G, n1, 1);
234  checkGraphInArcList(G, n2, 0);
235  checkGraphInArcList(G, n3, 0);
236  checkGraphInArcList(G, n4, 0);
237
238  checkGraphConArcList(G, 1);
239}
240
241
242template <class Digraph>
243void checkDigraphSnapshot() {
244  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
245
246  Digraph G;
247  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
248  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
249      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
250
251  typename Digraph::Snapshot snapshot(G);
252
253  Node n = G.addNode();
254  G.addArc(n3, n);
255  G.addArc(n, n3);
256
257  checkGraphNodeList(G, 4);
258  checkGraphArcList(G, 6);
259
260  snapshot.restore();
261
262  checkGraphNodeList(G, 3);
263  checkGraphArcList(G, 4);
264
265  checkGraphOutArcList(G, n1, 1);
266  checkGraphOutArcList(G, n2, 3);
267  checkGraphOutArcList(G, n3, 0);
268
269  checkGraphInArcList(G, n1, 1);
270  checkGraphInArcList(G, n2, 1);
271  checkGraphInArcList(G, n3, 2);
272
273  checkGraphConArcList(G, 4);
274
275  checkNodeIds(G);
276  checkArcIds(G);
277  checkGraphNodeMap(G);
278  checkGraphArcMap(G);
279
280  G.addNode();
281  snapshot.save(G);
282
283  G.addArc(G.addNode(), G.addNode());
284
285  snapshot.restore();
286
287  checkGraphNodeList(G, 4);
288  checkGraphArcList(G, 4);
289}
290
291void checkConcepts() {
292  { // Checking digraph components
293    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
294
295    checkConcept<IDableDigraphComponent<>,
296      IDableDigraphComponent<> >();
297
298    checkConcept<IterableDigraphComponent<>,
299      IterableDigraphComponent<> >();
300
301    checkConcept<MappableDigraphComponent<>,
302      MappableDigraphComponent<> >();
303  }
304  { // Checking skeleton digraph
305    checkConcept<Digraph, Digraph>();
306  }
307  { // Checking ListDigraph
308    checkConcept<Digraph, ListDigraph>();
309    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
310    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
311    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
312    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
313  }
314  { // Checking SmartDigraph
315    checkConcept<Digraph, SmartDigraph>();
316    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
317    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
318    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
319  }
320  { // Checking FullDigraph
321    checkConcept<Digraph, FullDigraph>();
322  }
323}
324
325template <typename Digraph>
326void checkDigraphValidity() {
327  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
328  Digraph g;
329
330  Node
331    n1 = g.addNode(),
332    n2 = g.addNode(),
333    n3 = g.addNode();
334
335  Arc
336    e1 = g.addArc(n1, n2),
337    e2 = g.addArc(n2, n3);
338
339  check(g.valid(n1), "Wrong validity check");
340  check(g.valid(e1), "Wrong validity check");
341
342  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
343  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
344}
345
346template <typename Digraph>
347void checkDigraphValidityErase() {
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
360  check(g.valid(n1), "Wrong validity check");
361  check(g.valid(e1), "Wrong validity check");
362
363  g.erase(n1);
364
365  check(!g.valid(n1), "Wrong validity check");
366  check(g.valid(n2), "Wrong validity check");
367  check(g.valid(n3), "Wrong validity check");
368  check(!g.valid(e1), "Wrong validity check");
369  check(g.valid(e2), "Wrong validity check");
370
371  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
372  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
373}
374
375void checkFullDigraph(int num) {
376  typedef FullDigraph Digraph;
377  DIGRAPH_TYPEDEFS(Digraph);
378  Digraph G(num);
379
380  checkGraphNodeList(G, num);
381  checkGraphArcList(G, num * num);
382
383  for (NodeIt n(G); n != INVALID; ++n) {
384    checkGraphOutArcList(G, n, num);
385    checkGraphInArcList(G, n, num);
386  }
387
388  checkGraphConArcList(G, num * num);
389
390  checkNodeIds(G);
391  checkArcIds(G);
392  checkGraphNodeMap(G);
393  checkGraphArcMap(G);
394
395  for (int i = 0; i < G.nodeNum(); ++i) {
396    check(G.index(G(i)) == i, "Wrong index");
397  }
398
399  for (NodeIt s(G); s != INVALID; ++s) {
400    for (NodeIt t(G); t != INVALID; ++t) {
401      Arc a = G.arc(s, t);
402      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
403    }
404  }
405}
406
407void checkDigraphs() {
408  { // Checking ListDigraph
409    checkDigraphBuild<ListDigraph>();
410    checkDigraphSplit<ListDigraph>();
411    checkDigraphAlter<ListDigraph>();
412    checkDigraphErase<ListDigraph>();
413    checkDigraphSnapshot<ListDigraph>();
414    checkDigraphValidityErase<ListDigraph>();
415  }
416  { // Checking SmartDigraph
417    checkDigraphBuild<SmartDigraph>();
418    checkDigraphSplit<SmartDigraph>();
419    checkDigraphSnapshot<SmartDigraph>();
420    checkDigraphValidity<SmartDigraph>();
421  }
422  { // Checking FullDigraph
423    checkFullDigraph(8);
424  }
425}
426
427int main() {
428  checkDigraphs();
429  checkConcepts();
430  return 0;
431}
Note: See TracBrowser for help on using the repository browser.