COIN-OR::LEMON - Graph Library

source: lemon/test/digraph_test.cc @ 384:164fe3abc024

Last change on this file since 384:164fe3abc024 was 377:a12eef1f82b2, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Rework hypercube graph implementation to be undirected (#57)

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