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>();
254 { // Checking SmartGraph
255 checkBpGraphBuild<SmartBpGraph>();
256 checkBpGraphSnapshot<SmartBpGraph>();
257 checkBpGraphValidity<SmartBpGraph>();