COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/digraph_test.cc @ 316:689f24ee83e6

Last change on this file since 316:689f24ee83e6 was 228:b6732e0d38c5, checked in by Balazs Dezso <deba@…>, 16 years ago

Reworking graph testing

  • The graph tests check more graph functionality.
  • The petersen graph is too regular, therefore special graphs are used.
  • The graph_test.h contains just general tools to test graphs.
File size: 4.6 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
82
83void checkConcepts() {
84  { // Checking digraph components
85    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
86
87    checkConcept<IDableDigraphComponent<>,
88      IDableDigraphComponent<> >();
89
90    checkConcept<IterableDigraphComponent<>,
91      IterableDigraphComponent<> >();
92
93    checkConcept<MappableDigraphComponent<>,
94      MappableDigraphComponent<> >();
95  }
96  { // Checking skeleton digraph
97    checkConcept<Digraph, Digraph>();
98  }
99  { // Checking ListDigraph
100    checkConcept<Digraph, ListDigraph>();
101    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
102    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
103    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
104    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
105  }
106  { // Checking SmartDigraph
107    checkConcept<Digraph, SmartDigraph>();
108    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
109    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
110    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
111  }
112//  { // Checking FullDigraph
113//    checkConcept<Digraph, FullDigraph>();
114//  }
115//  { // Checking HyperCubeDigraph
116//    checkConcept<Digraph, HyperCubeDigraph>();
117//  }
118}
119
120template <typename Digraph>
121void checkDigraphValidity() {
122  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
123  Digraph g;
124
125  Node
126    n1 = g.addNode(),
127    n2 = g.addNode(),
128    n3 = g.addNode();
129
130  Arc
131    e1 = g.addArc(n1, n2),
132    e2 = g.addArc(n2, n3);
133
134  check(g.valid(n1), "Wrong validity check");
135  check(g.valid(e1), "Wrong validity check");
136
137  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
138  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
139}
140
141template <typename Digraph>
142void checkDigraphValidityErase() {
143  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
144  Digraph g;
145
146  Node
147    n1 = g.addNode(),
148    n2 = g.addNode(),
149    n3 = g.addNode();
150
151  Arc
152    e1 = g.addArc(n1, n2),
153    e2 = g.addArc(n2, n3);
154
155  check(g.valid(n1), "Wrong validity check");
156  check(g.valid(e1), "Wrong validity check");
157
158  g.erase(n1);
159
160  check(!g.valid(n1), "Wrong validity check");
161  check(g.valid(n2), "Wrong validity check");
162  check(g.valid(n3), "Wrong validity check");
163  check(!g.valid(e1), "Wrong validity check");
164  check(g.valid(e2), "Wrong validity check");
165
166  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
167  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
168}
169
170void checkDigraphs() {
171  { // Checking ListDigraph
172    checkDigraph<ListDigraph>();
173    checkDigraphValidityErase<ListDigraph>();
174  }
175  { // Checking SmartDigraph
176    checkDigraph<SmartDigraph>();
177    checkDigraphValidity<SmartDigraph>();
178  }
179}
180
181int main() {
182  checkDigraphs();
183  checkConcepts();
184  return 0;
185}
Note: See TracBrowser for help on using the repository browser.