16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #include <lemon/concepts/bpgraph.h> |
19 #include <lemon/concepts/bpgraph.h> |
20 //#include <lemon/list_graph.h> |
20 //#include <lemon/list_graph.h> |
21 //#include <lemon/smart_graph.h> |
21 #include <lemon/smart_graph.h> |
22 //#include <lemon/full_graph.h> |
22 //#include <lemon/full_graph.h> |
23 //#include <lemon/grid_graph.h> |
|
24 //#include <lemon/hypercube_graph.h> |
|
25 |
23 |
26 #include "test_tools.h" |
24 #include "test_tools.h" |
27 #include "graph_test.h" |
25 #include "graph_test.h" |
28 |
26 |
29 using namespace lemon; |
27 using namespace lemon; |
30 using namespace lemon::concepts; |
28 using namespace lemon::concepts; |
|
29 |
|
30 template <class BpGraph> |
|
31 void 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 |
|
110 template <class Graph> |
|
111 void 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 |
|
193 template <typename Graph> |
|
194 void 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 } |
31 |
215 |
32 void checkConcepts() { |
216 void checkConcepts() { |
33 { // Checking graph components |
217 { // Checking graph components |
34 checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >(); |
218 checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >(); |
35 |
219 |