COIN-OR::LEMON - Graph Library

source: lemon/test/bpgraph_test.cc @ 1188:5ef0ab7b61cd

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

FullBpGraph? implementation (#69)

File size: 8.2 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 checkFullBpGraph(int redNum, int blueNum) {
254  typedef FullBpGraph BpGraph;
255  BPGRAPH_TYPEDEFS(BpGraph);
256
257  BpGraph G(redNum, blueNum);
258  checkGraphNodeList(G, redNum + blueNum);
259  checkGraphRedNodeList(G, redNum);
260  checkGraphBlueNodeList(G, blueNum);
261  checkGraphEdgeList(G, redNum * blueNum);
262  checkGraphArcList(G, 2 * redNum * blueNum);
263
264  G.resize(redNum, blueNum);
265  checkGraphNodeList(G, redNum + blueNum);
266  checkGraphRedNodeList(G, redNum);
267  checkGraphBlueNodeList(G, blueNum);
268  checkGraphEdgeList(G, redNum * blueNum);
269  checkGraphArcList(G, 2 * redNum * blueNum);
270
271  for (RedIt n(G); n != INVALID; ++n) {
272    checkGraphOutArcList(G, n, blueNum);
273    checkGraphInArcList(G, n, blueNum);
274    checkGraphIncEdgeList(G, n, blueNum);
275  }
276
277  for (BlueIt n(G); n != INVALID; ++n) {
278    checkGraphOutArcList(G, n, redNum);
279    checkGraphInArcList(G, n, redNum);
280    checkGraphIncEdgeList(G, n, redNum);
281  }
282
283  checkGraphConArcList(G, 2 * redNum * blueNum);
284  checkGraphConEdgeList(G, redNum * blueNum);
285
286  checkArcDirections(G);
287
288  checkNodeIds(G);
289  checkRedNodeIds(G);
290  checkBlueNodeIds(G);
291  checkArcIds(G);
292  checkEdgeIds(G);
293
294  checkGraphNodeMap(G);
295  checkGraphRedMap(G);
296  checkGraphBlueMap(G);
297  checkGraphArcMap(G);
298  checkGraphEdgeMap(G);
299
300  for (int i = 0; i < G.redNum(); ++i) {
301    check(G.red(G.redNode(i)), "Wrong node");
302    check(G.redIndex(G.redNode(i)) == i, "Wrong index");
303  }
304
305  for (int i = 0; i < G.blueNum(); ++i) {
306    check(G.blue(G.blueNode(i)), "Wrong node");
307    check(G.blueIndex(G.blueNode(i)) == i, "Wrong index");
308  }
309
310  for (NodeIt u(G); u != INVALID; ++u) {
311    for (NodeIt v(G); v != INVALID; ++v) {
312      Edge e = G.edge(u, v);
313      Arc a = G.arc(u, v);
314      if (G.red(u) == G.red(v)) {
315        check(e == INVALID, "Wrong edge lookup");
316        check(a == INVALID, "Wrong arc lookup");
317      } else {
318        check((G.u(e) == u && G.v(e) == v) ||
319              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
320        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
321      }
322    }
323  }
324
325}
326
327void checkGraphs() {
328  { // Checking SmartGraph
329    checkBpGraphBuild<SmartBpGraph>();
330    checkBpGraphSnapshot<SmartBpGraph>();
331    checkBpGraphValidity<SmartBpGraph>();
332  }
333  { // Checking FullBpGraph
334    checkFullBpGraph(6, 8);
335    checkFullBpGraph(7, 4);
336  }
337}
338
339int main() {
340  checkConcepts();
341  checkGraphs();
342  return 0;
343}
Note: See TracBrowser for help on using the repository browser.