COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-main/test/bpgraph_test.cc @ 1166:e2732b9da429

Last change on this file since 1166:e2732b9da429 was 1092:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

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