COIN-OR::LEMON - Graph Library

source: lemon/test/bpgraph_test.cc @ 1189:a12cca3ad15a

Last change on this file since 1189:a12cca3ad15a was 1189:a12cca3ad15a, checked in by Balazs Dezso <deba@…>, 9 years ago

ListBpGraph? implementation (#69)

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