1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #include <lemon/concepts/bpgraph.h>
20 //#include <lemon/list_graph.h>
21 #include <lemon/smart_graph.h>
22 #include <lemon/full_graph.h>
24 #include "test_tools.h"
25 #include "graph_test.h"
27 using namespace lemon;
28 using namespace lemon::concepts;
30 template <class BpGraph>
31 void checkBpGraphBuild() {
32 TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
35 checkGraphNodeList(G, 0);
36 checkGraphRedNodeList(G, 0);
37 checkGraphBlueNodeList(G, 0);
38 checkGraphEdgeList(G, 0);
39 checkGraphArcList(G, 0);
46 checkGraphNodeList(G, 1);
47 checkGraphRedNodeList(G, 1);
48 checkGraphBlueNodeList(G, 0);
49 checkGraphEdgeList(G, 0);
50 checkGraphArcList(G, 0);
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);
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");
65 checkGraphNodeList(G, 3);
66 checkGraphRedNodeList(G, 1);
67 checkGraphBlueNodeList(G, 2);
68 checkGraphEdgeList(G, 1);
69 checkGraphArcList(G, 2);
71 checkGraphIncEdgeArcLists(G, rn1, 1);
72 checkGraphIncEdgeArcLists(G, bn1, 0);
73 checkGraphIncEdgeArcLists(G, bn2, 1);
75 checkGraphConEdgeList(G, 1);
76 checkGraphConArcList(G, 2);
79 e2 = G.addEdge(rn1, bn1),
80 e3 = G.addEdge(rn1, bn2);
82 checkGraphNodeList(G, 3);
83 checkGraphRedNodeList(G, 1);
84 checkGraphBlueNodeList(G, 2);
85 checkGraphEdgeList(G, 3);
86 checkGraphArcList(G, 6);
88 checkGraphIncEdgeArcLists(G, rn1, 3);
89 checkGraphIncEdgeArcLists(G, bn1, 1);
90 checkGraphIncEdgeArcLists(G, bn2, 2);
92 checkGraphConEdgeList(G, 3);
93 checkGraphConArcList(G, 6);
95 checkArcDirections(G);
103 checkGraphNodeMap(G);
105 checkGraphBlueMap(G);
107 checkGraphEdgeMap(G);
110 template <class Graph>
111 void checkBpGraphSnapshot() {
112 TEMPLATE_BPGRAPH_TYPEDEFS(Graph);
117 n2 = G.addBlueNode(),
118 n3 = G.addBlueNode();
120 e1 = G.addEdge(n1, n2),
121 e2 = G.addEdge(n1, n3);
123 checkGraphNodeList(G, 3);
124 checkGraphRedNodeList(G, 1);
125 checkGraphBlueNodeList(G, 2);
126 checkGraphEdgeList(G, 2);
127 checkGraphArcList(G, 4);
129 typename Graph::Snapshot snapshot(G);
131 Node n4 = G.addRedNode();
135 checkGraphNodeList(G, 4);
136 checkGraphRedNodeList(G, 2);
137 checkGraphBlueNodeList(G, 2);
138 checkGraphEdgeList(G, 4);
139 checkGraphArcList(G, 8);
143 checkGraphNodeList(G, 3);
144 checkGraphRedNodeList(G, 1);
145 checkGraphBlueNodeList(G, 2);
146 checkGraphEdgeList(G, 2);
147 checkGraphArcList(G, 4);
149 checkGraphIncEdgeArcLists(G, n1, 2);
150 checkGraphIncEdgeArcLists(G, n2, 1);
151 checkGraphIncEdgeArcLists(G, n3, 1);
153 checkGraphConEdgeList(G, 2);
154 checkGraphConArcList(G, 4);
162 checkGraphNodeMap(G);
164 checkGraphBlueMap(G);
166 checkGraphEdgeMap(G);
171 G.addEdge(G.addRedNode(), G.addBlueNode());
176 checkGraphNodeList(G, 4);
177 checkGraphRedNodeList(G, 2);
178 checkGraphBlueNodeList(G, 2);
179 checkGraphEdgeList(G, 2);
180 checkGraphArcList(G, 4);
182 G.addEdge(G.addRedNode(), G.addBlueNode());
186 checkGraphNodeList(G, 4);
187 checkGraphRedNodeList(G, 2);
188 checkGraphBlueNodeList(G, 2);
189 checkGraphEdgeList(G, 2);
190 checkGraphArcList(G, 4);
193 template <typename Graph>
194 void checkBpGraphValidity() {
195 TEMPLATE_GRAPH_TYPEDEFS(Graph);
200 n2 = g.addBlueNode(),
201 n3 = g.addBlueNode();
204 e1 = g.addEdge(n1, n2),
205 e2 = g.addEdge(n1, n3);
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");
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");
216 void checkConcepts() {
217 { // Checking graph components
218 checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();
220 checkConcept<IDableBpGraphComponent<>,
221 IDableBpGraphComponent<> >();
223 checkConcept<IterableBpGraphComponent<>,
224 IterableBpGraphComponent<> >();
226 checkConcept<AlterableBpGraphComponent<>,
227 AlterableBpGraphComponent<> >();
229 checkConcept<MappableBpGraphComponent<>,
230 MappableBpGraphComponent<> >();
232 checkConcept<ExtendableBpGraphComponent<>,
233 ExtendableBpGraphComponent<> >();
235 checkConcept<ErasableBpGraphComponent<>,
236 ErasableBpGraphComponent<> >();
238 checkConcept<ClearableBpGraphComponent<>,
239 ClearableBpGraphComponent<> >();
242 { // Checking skeleton graph
243 checkConcept<BpGraph, BpGraph>();
245 { // Checking SmartBpGraph
246 checkConcept<BpGraph, SmartBpGraph>();
247 checkConcept<AlterableBpGraphComponent<>, SmartBpGraph>();
248 checkConcept<ExtendableBpGraphComponent<>, SmartBpGraph>();
249 checkConcept<ClearableBpGraphComponent<>, SmartBpGraph>();
253 void checkFullBpGraph(int redNum, int blueNum) {
254 typedef FullBpGraph BpGraph;
255 BPGRAPH_TYPEDEFS(BpGraph);
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);
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);
271 for (RedIt n(G); n != INVALID; ++n) {
272 checkGraphOutArcList(G, n, blueNum);
273 checkGraphInArcList(G, n, blueNum);
274 checkGraphIncEdgeList(G, n, blueNum);
277 for (BlueIt n(G); n != INVALID; ++n) {
278 checkGraphOutArcList(G, n, redNum);
279 checkGraphInArcList(G, n, redNum);
280 checkGraphIncEdgeList(G, n, redNum);
283 checkGraphConArcList(G, 2 * redNum * blueNum);
284 checkGraphConEdgeList(G, redNum * blueNum);
286 checkArcDirections(G);
294 checkGraphNodeMap(G);
296 checkGraphBlueMap(G);
298 checkGraphEdgeMap(G);
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");
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");
310 for (NodeIt u(G); u != INVALID; ++u) {
311 for (NodeIt v(G); v != INVALID; ++v) {
312 Edge e = G.edge(u, v);
314 if (G.red(u) == G.red(v)) {
315 check(e == INVALID, "Wrong edge lookup");
316 check(a == INVALID, "Wrong arc lookup");
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");
328 { // Checking SmartGraph
329 checkBpGraphBuild<SmartBpGraph>();
330 checkBpGraphSnapshot<SmartBpGraph>();
331 checkBpGraphValidity<SmartBpGraph>();
333 { // Checking FullBpGraph
334 checkFullBpGraph(6, 8);
335 checkFullBpGraph(7, 4);