27 |
27 |
28 using namespace lemon; |
28 using namespace lemon; |
29 using namespace lemon::concepts; |
29 using namespace lemon::concepts; |
30 |
30 |
31 template <class Graph> |
31 template <class Graph> |
32 void checkGraph() { |
32 void checkGraphBuild() { |
33 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
33 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
34 |
34 |
35 Graph G; |
35 Graph G; |
36 checkGraphNodeList(G, 0); |
36 checkGraphNodeList(G, 0); |
37 checkGraphEdgeList(G, 0); |
37 checkGraphEdgeList(G, 0); |
|
38 checkGraphArcList(G, 0); |
38 |
39 |
39 Node |
40 Node |
40 n1 = G.addNode(), |
41 n1 = G.addNode(), |
41 n2 = G.addNode(), |
42 n2 = G.addNode(), |
42 n3 = G.addNode(); |
43 n3 = G.addNode(); |
43 checkGraphNodeList(G, 3); |
44 checkGraphNodeList(G, 3); |
44 checkGraphEdgeList(G, 0); |
45 checkGraphEdgeList(G, 0); |
|
46 checkGraphArcList(G, 0); |
45 |
47 |
46 Edge e1 = G.addEdge(n1, n2); |
48 Edge e1 = G.addEdge(n1, n2); |
47 check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), |
49 check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), |
48 "Wrong edge"); |
50 "Wrong edge"); |
49 checkGraphNodeList(G, 3); |
51 |
|
52 checkGraphNodeList(G, 3); |
|
53 checkGraphEdgeList(G, 1); |
50 checkGraphArcList(G, 2); |
54 checkGraphArcList(G, 2); |
51 checkGraphEdgeList(G, 1); |
55 |
52 |
56 checkGraphIncEdgeArcLists(G, n1, 1); |
53 checkGraphOutArcList(G, n1, 1); |
57 checkGraphIncEdgeArcLists(G, n2, 1); |
54 checkGraphOutArcList(G, n2, 1); |
58 checkGraphIncEdgeArcLists(G, n3, 0); |
55 checkGraphOutArcList(G, n3, 0); |
59 |
56 |
60 checkGraphConEdgeList(G, 1); |
57 checkGraphInArcList(G, n1, 1); |
|
58 checkGraphInArcList(G, n2, 1); |
|
59 checkGraphInArcList(G, n3, 0); |
|
60 |
|
61 checkGraphIncEdgeList(G, n1, 1); |
|
62 checkGraphIncEdgeList(G, n2, 1); |
|
63 checkGraphIncEdgeList(G, n3, 0); |
|
64 |
|
65 checkGraphConArcList(G, 2); |
61 checkGraphConArcList(G, 2); |
66 checkGraphConEdgeList(G, 1); |
62 |
67 |
63 Edge e2 = G.addEdge(n2, n1), |
68 Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); |
64 e3 = G.addEdge(n2, n3); |
69 checkGraphNodeList(G, 3); |
65 |
|
66 checkGraphNodeList(G, 3); |
|
67 checkGraphEdgeList(G, 3); |
70 checkGraphArcList(G, 6); |
68 checkGraphArcList(G, 6); |
71 checkGraphEdgeList(G, 3); |
69 |
72 |
70 checkGraphIncEdgeArcLists(G, n1, 2); |
73 checkGraphOutArcList(G, n1, 2); |
71 checkGraphIncEdgeArcLists(G, n2, 3); |
74 checkGraphOutArcList(G, n2, 3); |
72 checkGraphIncEdgeArcLists(G, n3, 1); |
75 checkGraphOutArcList(G, n3, 1); |
73 |
76 |
74 checkGraphConEdgeList(G, 3); |
77 checkGraphInArcList(G, n1, 2); |
|
78 checkGraphInArcList(G, n2, 3); |
|
79 checkGraphInArcList(G, n3, 1); |
|
80 |
|
81 checkGraphIncEdgeList(G, n1, 2); |
|
82 checkGraphIncEdgeList(G, n2, 3); |
|
83 checkGraphIncEdgeList(G, n3, 1); |
|
84 |
|
85 checkGraphConArcList(G, 6); |
75 checkGraphConArcList(G, 6); |
86 checkGraphConEdgeList(G, 3); |
|
87 |
76 |
88 checkArcDirections(G); |
77 checkArcDirections(G); |
89 |
78 |
90 checkNodeIds(G); |
79 checkNodeIds(G); |
91 checkArcIds(G); |
80 checkArcIds(G); |
92 checkEdgeIds(G); |
81 checkEdgeIds(G); |
93 checkGraphNodeMap(G); |
82 checkGraphNodeMap(G); |
94 checkGraphArcMap(G); |
83 checkGraphArcMap(G); |
95 checkGraphEdgeMap(G); |
84 checkGraphEdgeMap(G); |
|
85 } |
|
86 |
|
87 template <class Graph> |
|
88 void checkGraphAlter() { |
|
89 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
90 |
|
91 Graph G; |
|
92 Node n1 = G.addNode(), n2 = G.addNode(), |
|
93 n3 = G.addNode(), n4 = G.addNode(); |
|
94 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), |
|
95 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), |
|
96 e5 = G.addEdge(n4, n3); |
|
97 |
|
98 checkGraphNodeList(G, 4); |
|
99 checkGraphEdgeList(G, 5); |
|
100 checkGraphArcList(G, 10); |
|
101 |
|
102 // Check changeU() and changeV() |
|
103 if (G.u(e2) == n2) { |
|
104 G.changeU(e2, n3); |
|
105 } else { |
|
106 G.changeV(e2, n3); |
|
107 } |
|
108 |
|
109 checkGraphNodeList(G, 4); |
|
110 checkGraphEdgeList(G, 5); |
|
111 checkGraphArcList(G, 10); |
|
112 |
|
113 checkGraphIncEdgeArcLists(G, n1, 3); |
|
114 checkGraphIncEdgeArcLists(G, n2, 2); |
|
115 checkGraphIncEdgeArcLists(G, n3, 3); |
|
116 checkGraphIncEdgeArcLists(G, n4, 2); |
|
117 |
|
118 checkGraphConEdgeList(G, 5); |
|
119 checkGraphConArcList(G, 10); |
|
120 |
|
121 if (G.u(e2) == n1) { |
|
122 G.changeU(e2, n2); |
|
123 } else { |
|
124 G.changeV(e2, n2); |
|
125 } |
|
126 |
|
127 checkGraphNodeList(G, 4); |
|
128 checkGraphEdgeList(G, 5); |
|
129 checkGraphArcList(G, 10); |
|
130 |
|
131 checkGraphIncEdgeArcLists(G, n1, 2); |
|
132 checkGraphIncEdgeArcLists(G, n2, 3); |
|
133 checkGraphIncEdgeArcLists(G, n3, 3); |
|
134 checkGraphIncEdgeArcLists(G, n4, 2); |
|
135 |
|
136 checkGraphConEdgeList(G, 5); |
|
137 checkGraphConArcList(G, 10); |
|
138 |
|
139 // Check contract() |
|
140 G.contract(n1, n4, false); |
|
141 |
|
142 checkGraphNodeList(G, 3); |
|
143 checkGraphEdgeList(G, 5); |
|
144 checkGraphArcList(G, 10); |
|
145 |
|
146 checkGraphIncEdgeArcLists(G, n1, 4); |
|
147 checkGraphIncEdgeArcLists(G, n2, 3); |
|
148 checkGraphIncEdgeArcLists(G, n3, 3); |
|
149 |
|
150 checkGraphConEdgeList(G, 5); |
|
151 checkGraphConArcList(G, 10); |
|
152 |
|
153 G.contract(n2, n3); |
|
154 |
|
155 checkGraphNodeList(G, 2); |
|
156 checkGraphEdgeList(G, 3); |
|
157 checkGraphArcList(G, 6); |
|
158 |
|
159 checkGraphIncEdgeArcLists(G, n1, 4); |
|
160 checkGraphIncEdgeArcLists(G, n2, 2); |
|
161 |
|
162 checkGraphConEdgeList(G, 3); |
|
163 checkGraphConArcList(G, 6); |
|
164 } |
|
165 |
|
166 template <class Graph> |
|
167 void checkGraphErase() { |
|
168 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
169 |
|
170 Graph G; |
|
171 Node n1 = G.addNode(), n2 = G.addNode(), |
|
172 n3 = G.addNode(), n4 = G.addNode(); |
|
173 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), |
|
174 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), |
|
175 e5 = G.addEdge(n4, n3); |
|
176 |
|
177 // Check edge deletion |
|
178 G.erase(e2); |
|
179 |
|
180 checkGraphNodeList(G, 4); |
|
181 checkGraphEdgeList(G, 4); |
|
182 checkGraphArcList(G, 8); |
|
183 |
|
184 checkGraphIncEdgeArcLists(G, n1, 2); |
|
185 checkGraphIncEdgeArcLists(G, n2, 2); |
|
186 checkGraphIncEdgeArcLists(G, n3, 2); |
|
187 checkGraphIncEdgeArcLists(G, n4, 2); |
|
188 |
|
189 checkGraphConEdgeList(G, 4); |
|
190 checkGraphConArcList(G, 8); |
|
191 |
|
192 // Check node deletion |
|
193 G.erase(n3); |
|
194 |
|
195 checkGraphNodeList(G, 3); |
|
196 checkGraphEdgeList(G, 2); |
|
197 checkGraphArcList(G, 4); |
|
198 |
|
199 checkGraphIncEdgeArcLists(G, n1, 2); |
|
200 checkGraphIncEdgeArcLists(G, n2, 1); |
|
201 checkGraphIncEdgeArcLists(G, n4, 1); |
|
202 |
|
203 checkGraphConEdgeList(G, 2); |
|
204 checkGraphConArcList(G, 4); |
|
205 } |
|
206 |
|
207 |
|
208 template <class Graph> |
|
209 void checkGraphSnapshot() { |
|
210 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
211 |
|
212 Graph G; |
|
213 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); |
|
214 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), |
|
215 e3 = G.addEdge(n2, n3); |
|
216 |
|
217 checkGraphNodeList(G, 3); |
|
218 checkGraphEdgeList(G, 3); |
|
219 checkGraphArcList(G, 6); |
|
220 |
|
221 typename Graph::Snapshot snapshot(G); |
|
222 |
|
223 Node n = G.addNode(); |
|
224 G.addEdge(n3, n); |
|
225 G.addEdge(n, n3); |
|
226 G.addEdge(n3, n2); |
|
227 |
|
228 checkGraphNodeList(G, 4); |
|
229 checkGraphEdgeList(G, 6); |
|
230 checkGraphArcList(G, 12); |
|
231 |
|
232 snapshot.restore(); |
|
233 |
|
234 checkGraphNodeList(G, 3); |
|
235 checkGraphEdgeList(G, 3); |
|
236 checkGraphArcList(G, 6); |
|
237 |
|
238 checkGraphIncEdgeArcLists(G, n1, 2); |
|
239 checkGraphIncEdgeArcLists(G, n2, 3); |
|
240 checkGraphIncEdgeArcLists(G, n3, 1); |
|
241 |
|
242 checkGraphConEdgeList(G, 3); |
|
243 checkGraphConArcList(G, 6); |
|
244 |
|
245 checkNodeIds(G); |
|
246 checkEdgeIds(G); |
|
247 checkArcIds(G); |
|
248 checkGraphNodeMap(G); |
|
249 checkGraphEdgeMap(G); |
|
250 checkGraphArcMap(G); |
|
251 |
|
252 G.addNode(); |
|
253 snapshot.save(G); |
|
254 |
|
255 G.addEdge(G.addNode(), G.addNode()); |
|
256 |
|
257 snapshot.restore(); |
|
258 |
|
259 checkGraphNodeList(G, 4); |
|
260 checkGraphEdgeList(G, 3); |
|
261 checkGraphArcList(G, 6); |
96 } |
262 } |
97 |
263 |
98 void checkConcepts() { |
264 void checkConcepts() { |
99 { // Checking graph components |
265 { // Checking graph components |
100 checkConcept<BaseGraphComponent, BaseGraphComponent >(); |
266 checkConcept<BaseGraphComponent, BaseGraphComponent >(); |