COIN-OR::LEMON - Graph Library

source: lemon/test/bpgraph_test.cc @ 1392:7c86f14b3bc5

Last change on this file since 1392:7c86f14b3bc5 was 1292:688a55e4c878, checked in by Alpar Juttner <alpar@…>, 6 years ago

Resolve clang++-3.2 'unused variable warning's in bpgraph_test.cc (#472)

File size: 11.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-2013
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  RedNode
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  BlueNode
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(bn1, rn1),
80    e3 = G.addEdge(rn1, bn2);
81  ::lemon::ignore_unused_variable_warning(e2,e3);
82
83  checkGraphNodeList(G, 3);
84  checkGraphRedNodeList(G, 1);
85  checkGraphBlueNodeList(G, 2);
86  checkGraphEdgeList(G, 3);
87  checkGraphArcList(G, 6);
88
89  checkGraphIncEdgeArcLists(G, rn1, 3);
90  checkGraphIncEdgeArcLists(G, bn1, 1);
91  checkGraphIncEdgeArcLists(G, bn2, 2);
92
93  checkGraphConEdgeList(G, 3);
94  checkGraphConArcList(G, 6);
95
96  checkArcDirections(G);
97
98  checkNodeIds(G);
99  checkRedNodeIds(G);
100  checkBlueNodeIds(G);
101  checkArcIds(G);
102  checkEdgeIds(G);
103
104  checkGraphNodeMap(G);
105  checkGraphRedNodeMap(G);
106  checkGraphBlueNodeMap(G);
107  checkGraphArcMap(G);
108  checkGraphEdgeMap(G);
109}
110
111template <class BpGraph>
112void checkBpGraphErase() {
113  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
114
115  BpGraph G;
116  RedNode
117    n1 = G.addRedNode(), n4 = G.addRedNode();
118  BlueNode
119    n2 = G.addBlueNode(), n3 = G.addBlueNode();
120  Edge
121    e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
122    e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
123  ::lemon::ignore_unused_variable_warning(e1,e3,e4);
124
125  // Check edge deletion
126  G.erase(e2);
127
128  checkGraphNodeList(G, 4);
129  checkGraphRedNodeList(G, 2);
130  checkGraphBlueNodeList(G, 2);
131  checkGraphEdgeList(G, 3);
132  checkGraphArcList(G, 6);
133
134  checkGraphIncEdgeArcLists(G, n1, 1);
135  checkGraphIncEdgeArcLists(G, n2, 2);
136  checkGraphIncEdgeArcLists(G, n3, 1);
137  checkGraphIncEdgeArcLists(G, n4, 2);
138
139  checkGraphConEdgeList(G, 3);
140  checkGraphConArcList(G, 6);
141
142  // Check node deletion
143  G.erase(n3);
144
145  checkGraphNodeList(G, 3);
146  checkGraphRedNodeList(G, 2);
147  checkGraphBlueNodeList(G, 1);
148  checkGraphEdgeList(G, 2);
149  checkGraphArcList(G, 4);
150
151  checkGraphIncEdgeArcLists(G, n1, 1);
152  checkGraphIncEdgeArcLists(G, n2, 2);
153  checkGraphIncEdgeArcLists(G, n4, 1);
154
155  checkGraphConEdgeList(G, 2);
156  checkGraphConArcList(G, 4);
157
158}
159
160template <class BpGraph>
161void checkBpGraphAlter() {
162  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
163
164  BpGraph G;
165  RedNode
166    n1 = G.addRedNode(), n4 = G.addRedNode();
167  BlueNode
168    n2 = G.addBlueNode(), n3 = G.addBlueNode();
169  Edge
170    e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
171    e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
172  ::lemon::ignore_unused_variable_warning(e1,e3,e4);
173
174  G.changeRed(e2, n4);
175  check(G.redNode(e2) == n4, "Wrong red node");
176  check(G.blueNode(e2) == n3, "Wrong blue node");
177
178  checkGraphNodeList(G, 4);
179  checkGraphRedNodeList(G, 2);
180  checkGraphBlueNodeList(G, 2);
181  checkGraphEdgeList(G, 4);
182  checkGraphArcList(G, 8);
183
184  checkGraphIncEdgeArcLists(G, n1, 1);
185  checkGraphIncEdgeArcLists(G, n2, 2);
186  checkGraphIncEdgeArcLists(G, n3, 2);
187  checkGraphIncEdgeArcLists(G, n4, 3);
188
189  checkGraphConEdgeList(G, 4);
190  checkGraphConArcList(G, 8);
191
192  G.changeBlue(e2, n2);
193  check(G.redNode(e2) == n4, "Wrong red node");
194  check(G.blueNode(e2) == n2, "Wrong blue node");
195
196  checkGraphNodeList(G, 4);
197  checkGraphRedNodeList(G, 2);
198  checkGraphBlueNodeList(G, 2);
199  checkGraphEdgeList(G, 4);
200  checkGraphArcList(G, 8);
201
202  checkGraphIncEdgeArcLists(G, n1, 1);
203  checkGraphIncEdgeArcLists(G, n2, 3);
204  checkGraphIncEdgeArcLists(G, n3, 1);
205  checkGraphIncEdgeArcLists(G, n4, 3);
206
207  checkGraphConEdgeList(G, 4);
208  checkGraphConArcList(G, 8);
209}
210
211
212template <class BpGraph>
213void checkBpGraphSnapshot() {
214  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
215
216  BpGraph G;
217  RedNode
218    n1 = G.addRedNode();
219  BlueNode
220    n2 = G.addBlueNode(),
221    n3 = G.addBlueNode();
222  Edge
223    e1 = G.addEdge(n1, n2),
224    e2 = G.addEdge(n1, n3);
225  ::lemon::ignore_unused_variable_warning(e1,e2);
226
227  checkGraphNodeList(G, 3);
228  checkGraphRedNodeList(G, 1);
229  checkGraphBlueNodeList(G, 2);
230  checkGraphEdgeList(G, 2);
231  checkGraphArcList(G, 4);
232
233  typename BpGraph::Snapshot snapshot(G);
234
235  RedNode n4 = G.addRedNode();
236  G.addEdge(n4, n2);
237  G.addEdge(n4, n3);
238
239  checkGraphNodeList(G, 4);
240  checkGraphRedNodeList(G, 2);
241  checkGraphBlueNodeList(G, 2);
242  checkGraphEdgeList(G, 4);
243  checkGraphArcList(G, 8);
244
245  snapshot.restore();
246
247  checkGraphNodeList(G, 3);
248  checkGraphRedNodeList(G, 1);
249  checkGraphBlueNodeList(G, 2);
250  checkGraphEdgeList(G, 2);
251  checkGraphArcList(G, 4);
252
253  checkGraphIncEdgeArcLists(G, n1, 2);
254  checkGraphIncEdgeArcLists(G, n2, 1);
255  checkGraphIncEdgeArcLists(G, n3, 1);
256
257  checkGraphConEdgeList(G, 2);
258  checkGraphConArcList(G, 4);
259
260  checkNodeIds(G);
261  checkRedNodeIds(G);
262  checkBlueNodeIds(G);
263  checkArcIds(G);
264  checkEdgeIds(G);
265
266  checkGraphNodeMap(G);
267  checkGraphRedNodeMap(G);
268  checkGraphBlueNodeMap(G);
269  checkGraphArcMap(G);
270  checkGraphEdgeMap(G);
271
272  G.addRedNode();
273  snapshot.save(G);
274
275  G.addEdge(G.addRedNode(), G.addBlueNode());
276
277  snapshot.restore();
278  snapshot.save(G);
279
280  checkGraphNodeList(G, 4);
281  checkGraphRedNodeList(G, 2);
282  checkGraphBlueNodeList(G, 2);
283  checkGraphEdgeList(G, 2);
284  checkGraphArcList(G, 4);
285
286  G.addEdge(G.addRedNode(), G.addBlueNode());
287
288  snapshot.restore();
289
290  checkGraphNodeList(G, 4);
291  checkGraphRedNodeList(G, 2);
292  checkGraphBlueNodeList(G, 2);
293  checkGraphEdgeList(G, 2);
294  checkGraphArcList(G, 4);
295}
296
297template <typename BpGraph>
298void checkBpGraphValidity() {
299  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
300  BpGraph g;
301
302  RedNode
303    n1 = g.addRedNode();
304  BlueNode
305    n2 = g.addBlueNode(),
306    n3 = g.addBlueNode();
307
308  Edge
309    e1 = g.addEdge(n1, n2),
310    e2 = g.addEdge(n1, n3);
311  ::lemon::ignore_unused_variable_warning(e2);
312
313  check(g.valid(n1), "Wrong validity check");
314  check(g.valid(e1), "Wrong validity check");
315  check(g.valid(g.direct(e1, true)), "Wrong validity check");
316
317  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
318  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
319  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
320}
321
322void checkConcepts() {
323  { // Checking graph components
324    checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();
325
326    checkConcept<IDableBpGraphComponent<>,
327      IDableBpGraphComponent<> >();
328
329    checkConcept<IterableBpGraphComponent<>,
330      IterableBpGraphComponent<> >();
331
332    checkConcept<AlterableBpGraphComponent<>,
333      AlterableBpGraphComponent<> >();
334
335    checkConcept<MappableBpGraphComponent<>,
336      MappableBpGraphComponent<> >();
337
338    checkConcept<ExtendableBpGraphComponent<>,
339      ExtendableBpGraphComponent<> >();
340
341    checkConcept<ErasableBpGraphComponent<>,
342      ErasableBpGraphComponent<> >();
343
344    checkConcept<ClearableBpGraphComponent<>,
345      ClearableBpGraphComponent<> >();
346
347  }
348  { // Checking skeleton graph
349    checkConcept<BpGraph, BpGraph>();
350  }
351  { // Checking SmartBpGraph
352    checkConcept<BpGraph, SmartBpGraph>();
353    checkConcept<AlterableBpGraphComponent<>, SmartBpGraph>();
354    checkConcept<ExtendableBpGraphComponent<>, SmartBpGraph>();
355    checkConcept<ClearableBpGraphComponent<>, SmartBpGraph>();
356  }
357}
358
359void checkFullBpGraph(int redNum, int blueNum) {
360  typedef FullBpGraph BpGraph;
361  BPGRAPH_TYPEDEFS(BpGraph);
362
363  BpGraph G(redNum, blueNum);
364  checkGraphNodeList(G, redNum + blueNum);
365  checkGraphRedNodeList(G, redNum);
366  checkGraphBlueNodeList(G, blueNum);
367  checkGraphEdgeList(G, redNum * blueNum);
368  checkGraphArcList(G, 2 * redNum * blueNum);
369
370  G.resize(redNum, blueNum);
371  checkGraphNodeList(G, redNum + blueNum);
372  checkGraphRedNodeList(G, redNum);
373  checkGraphBlueNodeList(G, blueNum);
374  checkGraphEdgeList(G, redNum * blueNum);
375  checkGraphArcList(G, 2 * redNum * blueNum);
376
377  for (RedNodeIt n(G); n != INVALID; ++n) {
378    checkGraphOutArcList(G, n, blueNum);
379    checkGraphInArcList(G, n, blueNum);
380    checkGraphIncEdgeList(G, n, blueNum);
381  }
382
383  for (BlueNodeIt n(G); n != INVALID; ++n) {
384    checkGraphOutArcList(G, n, redNum);
385    checkGraphInArcList(G, n, redNum);
386    checkGraphIncEdgeList(G, n, redNum);
387  }
388
389  checkGraphConArcList(G, 2 * redNum * blueNum);
390  checkGraphConEdgeList(G, redNum * blueNum);
391
392  checkArcDirections(G);
393
394  checkNodeIds(G);
395  checkRedNodeIds(G);
396  checkBlueNodeIds(G);
397  checkArcIds(G);
398  checkEdgeIds(G);
399
400  checkGraphNodeMap(G);
401  checkGraphRedNodeMap(G);
402  checkGraphBlueNodeMap(G);
403  checkGraphArcMap(G);
404  checkGraphEdgeMap(G);
405
406  for (int i = 0; i < G.redNum(); ++i) {
407    check(G.red(G.redNode(i)), "Wrong node");
408    check(G.index(G.redNode(i)) == i, "Wrong index");
409  }
410
411  for (int i = 0; i < G.blueNum(); ++i) {
412    check(G.blue(G.blueNode(i)), "Wrong node");
413    check(G.index(G.blueNode(i)) == i, "Wrong index");
414  }
415
416  for (NodeIt u(G); u != INVALID; ++u) {
417    for (NodeIt v(G); v != INVALID; ++v) {
418      Edge e = G.edge(u, v);
419      Arc a = G.arc(u, v);
420      if (G.red(u) == G.red(v)) {
421        check(e == INVALID, "Wrong edge lookup");
422        check(a == INVALID, "Wrong arc lookup");
423      } else {
424        check((G.u(e) == u && G.v(e) == v) ||
425              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
426        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
427      }
428    }
429  }
430
431}
432
433void checkGraphs() {
434  { // Checking ListGraph
435    checkBpGraphBuild<ListBpGraph>();
436    checkBpGraphErase<ListBpGraph>();
437    checkBpGraphAlter<ListBpGraph>();
438    checkBpGraphSnapshot<ListBpGraph>();
439    checkBpGraphValidity<ListBpGraph>();
440  }
441  { // Checking SmartGraph
442    checkBpGraphBuild<SmartBpGraph>();
443    checkBpGraphSnapshot<SmartBpGraph>();
444    checkBpGraphValidity<SmartBpGraph>();
445  }
446  { // Checking FullBpGraph
447    checkFullBpGraph(6, 8);
448    checkFullBpGraph(7, 4);
449  }
450}
451
452int main() {
453  checkConcepts();
454  checkGraphs();
455  return 0;
456}
Note: See TracBrowser for help on using the repository browser.