COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/digraph_test.cc @ 354:80a4d0742e98

Last change on this file since 354:80a4d0742e98 was 354:80a4d0742e98, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Improvements related to full graphs (#57)

File size: 5.4 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
115
116void checkConcepts() {
117  { // Checking digraph components
118    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
119
120    checkConcept<IDableDigraphComponent<>,
121      IDableDigraphComponent<> >();
122
123    checkConcept<IterableDigraphComponent<>,
124      IterableDigraphComponent<> >();
125
126    checkConcept<MappableDigraphComponent<>,
127      MappableDigraphComponent<> >();
128  }
129  { // Checking skeleton digraph
130    checkConcept<Digraph, Digraph>();
131  }
132  { // Checking ListDigraph
133    checkConcept<Digraph, ListDigraph>();
134    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
135    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
136    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
137    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
138  }
139  { // Checking SmartDigraph
140    checkConcept<Digraph, SmartDigraph>();
141    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
142    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
143    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
144  }
145  { // Checking FullDigraph
146    checkConcept<Digraph, FullDigraph>();
147  }
148//  { // Checking HyperCubeDigraph
149//    checkConcept<Digraph, HyperCubeDigraph>();
150//  }
151}
152
153template <typename Digraph>
154void checkDigraphValidity() {
155  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
156  Digraph g;
157
158  Node
159    n1 = g.addNode(),
160    n2 = g.addNode(),
161    n3 = g.addNode();
162
163  Arc
164    e1 = g.addArc(n1, n2),
165    e2 = g.addArc(n2, n3);
166
167  check(g.valid(n1), "Wrong validity check");
168  check(g.valid(e1), "Wrong validity check");
169
170  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
171  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
172}
173
174template <typename Digraph>
175void checkDigraphValidityErase() {
176  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
177  Digraph g;
178
179  Node
180    n1 = g.addNode(),
181    n2 = g.addNode(),
182    n3 = g.addNode();
183
184  Arc
185    e1 = g.addArc(n1, n2),
186    e2 = g.addArc(n2, n3);
187
188  check(g.valid(n1), "Wrong validity check");
189  check(g.valid(e1), "Wrong validity check");
190
191  g.erase(n1);
192
193  check(!g.valid(n1), "Wrong validity check");
194  check(g.valid(n2), "Wrong validity check");
195  check(g.valid(n3), "Wrong validity check");
196  check(!g.valid(e1), "Wrong validity check");
197  check(g.valid(e2), "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
203void checkDigraphs() {
204  { // Checking ListDigraph
205    checkDigraph<ListDigraph>();
206    checkDigraphValidityErase<ListDigraph>();
207  }
208  { // Checking SmartDigraph
209    checkDigraph<SmartDigraph>();
210    checkDigraphValidity<SmartDigraph>();
211  }
212  { // Checking FullDigraph
213    checkFullDigraph(8);
214  }
215}
216
217int main() {
218  checkDigraphs();
219  checkConcepts();
220  return 0;
221}
Note: See TracBrowser for help on using the repository browser.