COIN-OR::LEMON - Graph Library

source: lemon-main/test/bpgraph_test.cc @ 1019:4c89e925cfe2

Last change on this file since 1019:4c89e925cfe2 was 1019:4c89e925cfe2, checked in by Balazs Dezso <deba@…>, 14 years ago

SmartBpGraph? implementation (#69)

File size: 6.1 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-2010
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/bpgraph.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 BpGraph>
31void checkBpGraphBuild() {
32  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
33
34  BpGraph G;
35  checkGraphNodeList(G, 0);
36  checkGraphRedNodeList(G, 0);
37  checkGraphBlueNodeList(G, 0);
38  checkGraphEdgeList(G, 0);
39  checkGraphArcList(G, 0);
40
41  G.reserveNode(3);
42  G.reserveEdge(3);
43
44  Node
45    rn1 = G.addRedNode();
46  checkGraphNodeList(G, 1);
47  checkGraphRedNodeList(G, 1);
48  checkGraphBlueNodeList(G, 0);
49  checkGraphEdgeList(G, 0);
50  checkGraphArcList(G, 0);
51
52  Node
53    bn1 = G.addBlueNode(),
54    bn2 = G.addBlueNode();
55  checkGraphNodeList(G, 3);
56  checkGraphRedNodeList(G, 1);
57  checkGraphBlueNodeList(G, 2);
58  checkGraphEdgeList(G, 0);
59  checkGraphArcList(G, 0);
60
61  Edge e1 = G.addEdge(rn1, bn2);
62  check(G.redNode(e1) == rn1 && G.blueNode(e1) == bn2, "Wrong edge");
63  check(G.u(e1) == rn1 && G.v(e1) == bn2, "Wrong edge");
64
65  checkGraphNodeList(G, 3);
66  checkGraphRedNodeList(G, 1);
67  checkGraphBlueNodeList(G, 2);
68  checkGraphEdgeList(G, 1);
69  checkGraphArcList(G, 2);
70
71  checkGraphIncEdgeArcLists(G, rn1, 1);
72  checkGraphIncEdgeArcLists(G, bn1, 0);
73  checkGraphIncEdgeArcLists(G, bn2, 1);
74
75  checkGraphConEdgeList(G, 1);
76  checkGraphConArcList(G, 2);
77
78  Edge
79    e2 = G.addEdge(rn1, bn1),
80    e3 = G.addEdge(rn1, bn2);
81
82  checkGraphNodeList(G, 3);
83  checkGraphRedNodeList(G, 1);
84  checkGraphBlueNodeList(G, 2);
85  checkGraphEdgeList(G, 3);
86  checkGraphArcList(G, 6);
87
88  checkGraphIncEdgeArcLists(G, rn1, 3);
89  checkGraphIncEdgeArcLists(G, bn1, 1);
90  checkGraphIncEdgeArcLists(G, bn2, 2);
91
92  checkGraphConEdgeList(G, 3);
93  checkGraphConArcList(G, 6);
94
95  checkArcDirections(G);
96
97  checkNodeIds(G);
98  checkRedNodeIds(G);
99  checkBlueNodeIds(G);
100  checkArcIds(G);
101  checkEdgeIds(G);
102
103  checkGraphNodeMap(G);
104  checkGraphRedMap(G);
105  checkGraphBlueMap(G);
106  checkGraphArcMap(G);
107  checkGraphEdgeMap(G);
108}
109
110template <class Graph>
111void checkBpGraphSnapshot() {
112  TEMPLATE_BPGRAPH_TYPEDEFS(Graph);
113
114  Graph G;
115  Node
116    n1 = G.addRedNode(),
117    n2 = G.addBlueNode(),
118    n3 = G.addBlueNode();
119  Edge
120    e1 = G.addEdge(n1, n2),
121    e2 = G.addEdge(n1, n3);
122
123  checkGraphNodeList(G, 3);
124  checkGraphRedNodeList(G, 1);
125  checkGraphBlueNodeList(G, 2);
126  checkGraphEdgeList(G, 2);
127  checkGraphArcList(G, 4);
128
129  typename Graph::Snapshot snapshot(G);
130
131  Node n4 = G.addRedNode();
132  G.addEdge(n4, n2);
133  G.addEdge(n4, n3);
134
135  checkGraphNodeList(G, 4);
136  checkGraphRedNodeList(G, 2);
137  checkGraphBlueNodeList(G, 2);
138  checkGraphEdgeList(G, 4);
139  checkGraphArcList(G, 8);
140
141  snapshot.restore();
142
143  checkGraphNodeList(G, 3);
144  checkGraphRedNodeList(G, 1);
145  checkGraphBlueNodeList(G, 2);
146  checkGraphEdgeList(G, 2);
147  checkGraphArcList(G, 4);
148
149  checkGraphIncEdgeArcLists(G, n1, 2);
150  checkGraphIncEdgeArcLists(G, n2, 1);
151  checkGraphIncEdgeArcLists(G, n3, 1);
152
153  checkGraphConEdgeList(G, 2);
154  checkGraphConArcList(G, 4);
155
156  checkNodeIds(G);
157  checkRedNodeIds(G);
158  checkBlueNodeIds(G);
159  checkArcIds(G);
160  checkEdgeIds(G);
161
162  checkGraphNodeMap(G);
163  checkGraphRedMap(G);
164  checkGraphBlueMap(G);
165  checkGraphArcMap(G);
166  checkGraphEdgeMap(G);
167
168  G.addRedNode();
169  snapshot.save(G);
170
171  G.addEdge(G.addRedNode(), G.addBlueNode());
172
173  snapshot.restore();
174  snapshot.save(G);
175
176  checkGraphNodeList(G, 4);
177  checkGraphRedNodeList(G, 2);
178  checkGraphBlueNodeList(G, 2);
179  checkGraphEdgeList(G, 2);
180  checkGraphArcList(G, 4);
181
182  G.addEdge(G.addRedNode(), G.addBlueNode());
183
184  snapshot.restore();
185
186  checkGraphNodeList(G, 4);
187  checkGraphRedNodeList(G, 2);
188  checkGraphBlueNodeList(G, 2);
189  checkGraphEdgeList(G, 2);
190  checkGraphArcList(G, 4);
191}
192
193template <typename Graph>
194void checkBpGraphValidity() {
195  TEMPLATE_GRAPH_TYPEDEFS(Graph);
196  Graph g;
197
198  Node
199    n1 = g.addRedNode(),
200    n2 = g.addBlueNode(),
201    n3 = g.addBlueNode();
202
203  Edge
204    e1 = g.addEdge(n1, n2),
205    e2 = g.addEdge(n1, n3);
206
207  check(g.valid(n1), "Wrong validity check");
208  check(g.valid(e1), "Wrong validity check");
209  check(g.valid(g.direct(e1, true)), "Wrong validity check");
210
211  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
212  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
213  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
214}
215
216void checkConcepts() {
217  { // Checking graph components
218    checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();
219
220    checkConcept<IDableBpGraphComponent<>,
221      IDableBpGraphComponent<> >();
222
223    checkConcept<IterableBpGraphComponent<>,
224      IterableBpGraphComponent<> >();
225
226    checkConcept<AlterableBpGraphComponent<>,
227      AlterableBpGraphComponent<> >();
228
229    checkConcept<MappableBpGraphComponent<>,
230      MappableBpGraphComponent<> >();
231
232    checkConcept<ExtendableBpGraphComponent<>,
233      ExtendableBpGraphComponent<> >();
234
235    checkConcept<ErasableBpGraphComponent<>,
236      ErasableBpGraphComponent<> >();
237
238    checkConcept<ClearableBpGraphComponent<>,
239      ClearableBpGraphComponent<> >();
240
241  }
242  { // Checking skeleton graph
243    checkConcept<BpGraph, BpGraph>();
244  }
245  { // Checking SmartBpGraph
246    checkConcept<BpGraph, SmartBpGraph>();
247    checkConcept<AlterableBpGraphComponent<>, SmartBpGraph>();
248    checkConcept<ExtendableBpGraphComponent<>, SmartBpGraph>();
249    checkConcept<ClearableBpGraphComponent<>, SmartBpGraph>();
250  }
251}
252
253void checkGraphs() {
254  { // Checking SmartGraph
255    checkBpGraphBuild<SmartBpGraph>();
256    checkBpGraphSnapshot<SmartBpGraph>();
257    checkBpGraphValidity<SmartBpGraph>();
258  }
259}
260
261int main() {
262  checkConcepts();
263  checkGraphs();
264  return 0;
265}
Note: See TracBrowser for help on using the repository browser.