1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
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>
25 #include "test_tools.h"
26 #include "graph_test.h"
28 using namespace lemon;
29 using namespace lemon::concepts;
31 template <class Digraph>
33 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
36 checkGraphNodeList(G, 0);
37 checkGraphArcList(G, 0);
43 checkGraphNodeList(G, 3);
44 checkGraphArcList(G, 0);
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);
51 checkGraphOutArcList(G, n1, 1);
52 checkGraphOutArcList(G, n2, 0);
53 checkGraphOutArcList(G, n3, 0);
55 checkGraphInArcList(G, n1, 0);
56 checkGraphInArcList(G, n2, 1);
57 checkGraphInArcList(G, n3, 0);
59 checkGraphConArcList(G, 1);
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);
65 checkGraphOutArcList(G, n1, 1);
66 checkGraphOutArcList(G, n2, 3);
67 checkGraphOutArcList(G, n3, 0);
69 checkGraphInArcList(G, n1, 1);
70 checkGraphInArcList(G, n2, 1);
71 checkGraphInArcList(G, n3, 2);
73 checkGraphConArcList(G, 4);
82 void checkFullDigraph(int num) {
83 typedef FullDigraph Digraph;
84 DIGRAPH_TYPEDEFS(Digraph);
87 checkGraphNodeList(G, num);
88 checkGraphArcList(G, num * num);
90 for (NodeIt n(G); n != INVALID; ++n) {
91 checkGraphOutArcList(G, n, num);
92 checkGraphInArcList(G, n, num);
95 checkGraphConArcList(G, num * num);
102 for (int i = 0; i < G.nodeNum(); ++i) {
103 check(G.index(G(i)) == i, "Wrong index");
106 for (NodeIt s(G); s != INVALID; ++s) {
107 for (NodeIt t(G); t != INVALID; ++t) {
109 check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
115 void checkHypercubeDigraph(int dim) {
116 DIGRAPH_TYPEDEFS(HypercubeDigraph);
118 HypercubeDigraph G(dim);
119 checkGraphNodeList(G, 1 << dim);
120 checkGraphArcList(G, (1 << dim) * dim);
122 Node n = G.nodeFromId(dim);
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)),
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)),
136 checkGraphConArcList(G, (1 << dim) * dim);
140 checkGraphNodeMap(G);
145 void checkConcepts() {
146 { // Checking digraph components
147 checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
149 checkConcept<IDableDigraphComponent<>,
150 IDableDigraphComponent<> >();
152 checkConcept<IterableDigraphComponent<>,
153 IterableDigraphComponent<> >();
155 checkConcept<MappableDigraphComponent<>,
156 MappableDigraphComponent<> >();
158 { // Checking skeleton digraph
159 checkConcept<Digraph, Digraph>();
161 { // Checking ListDigraph
162 checkConcept<Digraph, ListDigraph>();
163 checkConcept<AlterableDigraphComponent<>, ListDigraph>();
164 checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
165 checkConcept<ClearableDigraphComponent<>, ListDigraph>();
166 checkConcept<ErasableDigraphComponent<>, ListDigraph>();
168 { // Checking SmartDigraph
169 checkConcept<Digraph, SmartDigraph>();
170 checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
171 checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
172 checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
174 { // Checking FullDigraph
175 checkConcept<Digraph, FullDigraph>();
177 { // Checking HypercubeDigraph
178 checkConcept<Digraph, HypercubeDigraph>();
182 template <typename Digraph>
183 void checkDigraphValidity() {
184 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
193 e1 = g.addArc(n1, n2),
194 e2 = g.addArc(n2, n3);
196 check(g.valid(n1), "Wrong validity check");
197 check(g.valid(e1), "Wrong validity check");
199 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
200 check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
203 template <typename Digraph>
204 void checkDigraphValidityErase() {
205 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
214 e1 = g.addArc(n1, n2),
215 e2 = g.addArc(n2, n3);
217 check(g.valid(n1), "Wrong validity check");
218 check(g.valid(e1), "Wrong validity check");
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");
228 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
229 check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
232 void checkDigraphs() {
233 { // Checking ListDigraph
234 checkDigraph<ListDigraph>();
235 checkDigraphValidityErase<ListDigraph>();
237 { // Checking SmartDigraph
238 checkDigraph<SmartDigraph>();
239 checkDigraphValidity<SmartDigraph>();
241 { // Checking FullDigraph
244 { // Checking HypercubeDigraph
245 checkHypercubeDigraph(1);
246 checkHypercubeDigraph(2);
247 checkHypercubeDigraph(3);
248 checkHypercubeDigraph(4);