COIN-OR::LEMON - Graph Library

source: lemon/test/digraph_test.cc @ 376:b4a01426c0d9

Last change on this file since 376:b4a01426c0d9 was 376:b4a01426c0d9, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Port hypercube digraph structure from SVN 3503 (#57)

File size: 6.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-2008
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#include <lemon/hypercube_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 checkDigraph() {
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), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
62  checkGraphNodeList(G, 3);
63  checkGraphArcList(G, 4);
64
65  checkGraphOutArcList(G, n1, 1);
66  checkGraphOutArcList(G, n2, 3);
67  checkGraphOutArcList(G, n3, 0);
68
69  checkGraphInArcList(G, n1, 1);
70  checkGraphInArcList(G, n2, 1);
71  checkGraphInArcList(G, n3, 2);
72
73  checkGraphConArcList(G, 4);
74
75  checkNodeIds(G);
76  checkArcIds(G);
77  checkGraphNodeMap(G);
78  checkGraphArcMap(G);
79
80}
81
82void checkFullDigraph(int num) {
83  typedef FullDigraph Digraph;
84  DIGRAPH_TYPEDEFS(Digraph);
85  Digraph G(num);
86
87  checkGraphNodeList(G, num);
88  checkGraphArcList(G, num * num);
89
90  for (NodeIt n(G); n != INVALID; ++n) {
91    checkGraphOutArcList(G, n, num);
92    checkGraphInArcList(G, n, num);
93  }
94
95  checkGraphConArcList(G, num * num);
96
97  checkNodeIds(G);
98  checkArcIds(G);
99  checkGraphNodeMap(G);
100  checkGraphArcMap(G);
101
102  for (int i = 0; i < G.nodeNum(); ++i) {
103    check(G.index(G(i)) == i, "Wrong index");
104  }
105
106  for (NodeIt s(G); s != INVALID; ++s) {
107    for (NodeIt t(G); t != INVALID; ++t) {
108      Arc a = G.arc(s, t);
109      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
110    }
111  }
112
113}
114
115void checkHypercubeDigraph(int dim) {
116  DIGRAPH_TYPEDEFS(HypercubeDigraph);
117
118  HypercubeDigraph G(dim);
119  checkGraphNodeList(G, 1 << dim);
120  checkGraphArcList(G, (1 << dim) * dim);
121
122  Node n = G.nodeFromId(dim);
123
124  checkGraphOutArcList(G, n, dim);
125  for (OutArcIt a(G, n); a != INVALID; ++a)
126    check(G.source(a) == n &&
127          G.id(G.target(a)) == G.id(n) ^ (1 << G.dimension(a)),
128          "Wrong arc");
129
130  checkGraphInArcList(G, n, dim);
131  for (InArcIt a(G, n); a != INVALID; ++a)
132    check(G.target(a) == n &&
133          G.id(G.source(a)) == G.id(n) ^ (1 << G.dimension(a)),
134          "Wrong arc");
135
136  checkGraphConArcList(G, (1 << dim) * dim);
137
138  checkNodeIds(G);
139  checkArcIds(G);
140  checkGraphNodeMap(G);
141  checkGraphArcMap(G);
142}
143
144
145void checkConcepts() {
146  { // Checking digraph components
147    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
148
149    checkConcept<IDableDigraphComponent<>,
150      IDableDigraphComponent<> >();
151
152    checkConcept<IterableDigraphComponent<>,
153      IterableDigraphComponent<> >();
154
155    checkConcept<MappableDigraphComponent<>,
156      MappableDigraphComponent<> >();
157  }
158  { // Checking skeleton digraph
159    checkConcept<Digraph, Digraph>();
160  }
161  { // Checking ListDigraph
162    checkConcept<Digraph, ListDigraph>();
163    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
164    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
165    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
166    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
167  }
168  { // Checking SmartDigraph
169    checkConcept<Digraph, SmartDigraph>();
170    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
171    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
172    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
173  }
174  { // Checking FullDigraph
175    checkConcept<Digraph, FullDigraph>();
176  }
177  { // Checking HypercubeDigraph
178    checkConcept<Digraph, HypercubeDigraph>();
179  }
180}
181
182template <typename Digraph>
183void checkDigraphValidity() {
184  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
185  Digraph g;
186
187  Node
188    n1 = g.addNode(),
189    n2 = g.addNode(),
190    n3 = g.addNode();
191
192  Arc
193    e1 = g.addArc(n1, n2),
194    e2 = g.addArc(n2, n3);
195
196  check(g.valid(n1), "Wrong validity check");
197  check(g.valid(e1), "Wrong validity check");
198
199  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
200  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
201}
202
203template <typename Digraph>
204void checkDigraphValidityErase() {
205  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
206  Digraph g;
207
208  Node
209    n1 = g.addNode(),
210    n2 = g.addNode(),
211    n3 = g.addNode();
212
213  Arc
214    e1 = g.addArc(n1, n2),
215    e2 = g.addArc(n2, n3);
216
217  check(g.valid(n1), "Wrong validity check");
218  check(g.valid(e1), "Wrong validity check");
219
220  g.erase(n1);
221
222  check(!g.valid(n1), "Wrong validity check");
223  check(g.valid(n2), "Wrong validity check");
224  check(g.valid(n3), "Wrong validity check");
225  check(!g.valid(e1), "Wrong validity check");
226  check(g.valid(e2), "Wrong validity check");
227
228  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
229  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
230}
231
232void checkDigraphs() {
233  { // Checking ListDigraph
234    checkDigraph<ListDigraph>();
235    checkDigraphValidityErase<ListDigraph>();
236  }
237  { // Checking SmartDigraph
238    checkDigraph<SmartDigraph>();
239    checkDigraphValidity<SmartDigraph>();
240  }
241  { // Checking FullDigraph
242    checkFullDigraph(8);
243  }
244  { // Checking HypercubeDigraph
245    checkHypercubeDigraph(1);
246    checkHypercubeDigraph(2);
247    checkHypercubeDigraph(3);
248    checkHypercubeDigraph(4);
249  }
250}
251
252int main() {
253  checkDigraphs();
254  checkConcepts();
255  return 0;
256}
Note: See TracBrowser for help on using the repository browser.