[503] | 1 | #include<iostream> |
---|
[542] | 2 | #include<hugo/smart_graph.h> |
---|
[564] | 3 | #include<hugo/skeletons/graph.h> |
---|
[578] | 4 | #include<hugo/list_graph.h> |
---|
[592] | 5 | #include<hugo/full_graph.h> |
---|
[578] | 6 | |
---|
[567] | 7 | #include"test_tools.h" |
---|
| 8 | |
---|
[774] | 9 | /** |
---|
| 10 | \file |
---|
[503] | 11 | This test makes consistency checks of list graph structures. |
---|
| 12 | |
---|
[774] | 13 | G.addNode(), G.addEdge(), G.tail(), G.head() |
---|
[503] | 14 | |
---|
[592] | 15 | \todo Checks for empty graphs and isolated points. |
---|
[774] | 16 | \todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt} |
---|
| 17 | conversion. |
---|
[503] | 18 | */ |
---|
| 19 | |
---|
| 20 | using namespace hugo; |
---|
| 21 | |
---|
[592] | 22 | template<class Graph> void checkCompileStaticGraph(Graph &G) |
---|
[503] | 23 | { |
---|
| 24 | typedef typename Graph::Node Node; |
---|
| 25 | typedef typename Graph::NodeIt NodeIt; |
---|
| 26 | typedef typename Graph::Edge Edge; |
---|
| 27 | typedef typename Graph::EdgeIt EdgeIt; |
---|
| 28 | typedef typename Graph::InEdgeIt InEdgeIt; |
---|
| 29 | typedef typename Graph::OutEdgeIt OutEdgeIt; |
---|
| 30 | |
---|
| 31 | { |
---|
| 32 | Node i; Node j(i); Node k(INVALID); |
---|
| 33 | i=j; |
---|
[774] | 34 | // bool b=G.valid(i); b=b; |
---|
| 35 | bool b; b=b; |
---|
| 36 | b=(i==INVALID); b=(i!=INVALID); |
---|
[503] | 37 | b=(i==j); b=(i!=j); b=(i<j); |
---|
| 38 | } |
---|
| 39 | { |
---|
| 40 | NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G); |
---|
| 41 | i=j; |
---|
| 42 | j=G.first(i); |
---|
[774] | 43 | j=++i; |
---|
| 44 | // bool b=G.valid(i); b=b; |
---|
| 45 | bool b; b=b; |
---|
| 46 | b=(i==INVALID); b=(i!=INVALID); |
---|
[503] | 47 | Node n(i); |
---|
| 48 | n=i; |
---|
| 49 | b=(i==j); b=(i!=j); b=(i<j); |
---|
[774] | 50 | //Node ->NodeIt conversion |
---|
| 51 | NodeIt ni(G,n); |
---|
[503] | 52 | } |
---|
| 53 | { |
---|
| 54 | Edge i; Edge j(i); Edge k(INVALID); |
---|
| 55 | i=j; |
---|
[774] | 56 | // bool b=G.valid(i); b=b; |
---|
| 57 | bool b; b=b; |
---|
| 58 | b=(i==INVALID); b=(i!=INVALID); |
---|
[503] | 59 | b=(i==j); b=(i!=j); b=(i<j); |
---|
| 60 | } |
---|
| 61 | { |
---|
| 62 | EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G); |
---|
| 63 | i=j; |
---|
| 64 | j=G.first(i); |
---|
[774] | 65 | j=++i; |
---|
| 66 | // bool b=G.valid(i); b=b; |
---|
| 67 | bool b; b=b; |
---|
| 68 | b=(i==INVALID); b=(i!=INVALID); |
---|
[503] | 69 | Edge e(i); |
---|
| 70 | e=i; |
---|
| 71 | b=(i==j); b=(i!=j); b=(i<j); |
---|
[774] | 72 | //Edge ->EdgeIt conversion |
---|
| 73 | EdgeIt ei(G,e); |
---|
[503] | 74 | } |
---|
| 75 | { |
---|
| 76 | Node n; |
---|
| 77 | InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); |
---|
| 78 | i=j; |
---|
| 79 | j=G.first(i,n); |
---|
[774] | 80 | j=++i; |
---|
| 81 | // bool b=G.valid(i); b=b; |
---|
| 82 | bool b; b=b; |
---|
| 83 | b=(i==INVALID); b=(i!=INVALID); |
---|
[503] | 84 | Edge e(i); |
---|
| 85 | e=i; |
---|
| 86 | b=(i==j); b=(i!=j); b=(i<j); |
---|
[774] | 87 | //Edge ->InEdgeIt conversion |
---|
| 88 | InEdgeIt ei(G,e); |
---|
[503] | 89 | } |
---|
| 90 | { |
---|
| 91 | Node n; |
---|
| 92 | OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); |
---|
| 93 | i=j; |
---|
| 94 | j=G.first(i,n); |
---|
[774] | 95 | j=++i; |
---|
| 96 | // bool b=G.valid(i); b=b; |
---|
| 97 | bool b; b=b; |
---|
| 98 | b=(i==INVALID); b=(i!=INVALID); |
---|
[503] | 99 | Edge e(i); |
---|
| 100 | e=i; |
---|
| 101 | b=(i==j); b=(i!=j); b=(i<j); |
---|
[774] | 102 | //Edge ->OutEdgeIt conversion |
---|
| 103 | OutEdgeIt ei(G,e); |
---|
[503] | 104 | } |
---|
[774] | 105 | { |
---|
| 106 | Node n,m; |
---|
| 107 | n=m=INVALID; |
---|
| 108 | Edge e; |
---|
| 109 | e=INVALID; |
---|
| 110 | n=G.tail(e); |
---|
| 111 | n=G.head(e); |
---|
| 112 | } |
---|
[503] | 113 | // id tests |
---|
[774] | 114 | { Node n; int i=G.id(n); i=i; } |
---|
| 115 | { Edge e; int i=G.id(e); i=i; } |
---|
[503] | 116 | //NodeMap tests |
---|
| 117 | { |
---|
| 118 | Node k; |
---|
[515] | 119 | typename Graph::template NodeMap<int> m(G); |
---|
[774] | 120 | //Const map |
---|
| 121 | typename Graph::template NodeMap<int> const &cm = m; |
---|
[515] | 122 | //Inicialize with default value |
---|
| 123 | typename Graph::template NodeMap<int> mdef(G,12); |
---|
[774] | 124 | //Copy |
---|
| 125 | typename Graph::template NodeMap<int> mm(cm); |
---|
| 126 | //Copy from another type |
---|
| 127 | typename Graph::template NodeMap<double> dm(cm); |
---|
[503] | 128 | int v; |
---|
| 129 | v=m[k]; m[k]=v; m.set(k,v); |
---|
| 130 | v=cm[k]; |
---|
| 131 | |
---|
| 132 | m=cm; |
---|
| 133 | dm=cm; //Copy from another type |
---|
[787] | 134 | { |
---|
| 135 | //Check the typedef's |
---|
| 136 | typename Graph::template NodeMap<int>::ValueType val; |
---|
| 137 | val=1; |
---|
| 138 | typename Graph::template NodeMap<int>::KeyType key; |
---|
| 139 | key = typename Graph::NodeIt(G); |
---|
| 140 | } |
---|
[503] | 141 | } |
---|
| 142 | { //bool NodeMap |
---|
| 143 | Node k; |
---|
[515] | 144 | typename Graph::template NodeMap<bool> m(G); |
---|
| 145 | typename Graph::template NodeMap<bool> const &cm = m; //Const map |
---|
| 146 | //Inicialize with default value |
---|
| 147 | typename Graph::template NodeMap<bool> mdef(G,12); |
---|
| 148 | typename Graph::template NodeMap<bool> mm(cm); //Copy |
---|
| 149 | typename Graph::template NodeMap<int> dm(cm); //Copy from another type |
---|
[503] | 150 | bool v; |
---|
| 151 | v=m[k]; m[k]=v; m.set(k,v); |
---|
| 152 | v=cm[k]; |
---|
| 153 | |
---|
| 154 | m=cm; |
---|
| 155 | dm=cm; //Copy from another type |
---|
[504] | 156 | m=dm; //Copy to another type |
---|
[787] | 157 | |
---|
| 158 | { |
---|
| 159 | //Check the typedef's |
---|
| 160 | typename Graph::template NodeMap<bool>::ValueType val; |
---|
| 161 | val=true; |
---|
| 162 | typename Graph::template NodeMap<bool>::KeyType key; |
---|
| 163 | key= typename Graph::NodeIt(G); |
---|
| 164 | } |
---|
[503] | 165 | } |
---|
| 166 | //EdgeMap tests |
---|
| 167 | { |
---|
| 168 | Edge k; |
---|
[515] | 169 | typename Graph::template EdgeMap<int> m(G); |
---|
| 170 | typename Graph::template EdgeMap<int> const &cm = m; //Const map |
---|
| 171 | //Inicialize with default value |
---|
| 172 | typename Graph::template EdgeMap<int> mdef(G,12); |
---|
| 173 | typename Graph::template EdgeMap<int> mm(cm); //Copy |
---|
| 174 | typename Graph::template EdgeMap<double> dm(cm); //Copy from another type |
---|
[503] | 175 | int v; |
---|
| 176 | v=m[k]; m[k]=v; m.set(k,v); |
---|
| 177 | v=cm[k]; |
---|
| 178 | |
---|
| 179 | m=cm; |
---|
| 180 | dm=cm; //Copy from another type |
---|
[787] | 181 | { |
---|
| 182 | //Check the typedef's |
---|
| 183 | typename Graph::template EdgeMap<int>::ValueType val; |
---|
| 184 | val=1; |
---|
| 185 | typename Graph::template EdgeMap<int>::KeyType key; |
---|
| 186 | key= typename Graph::EdgeIt(G); |
---|
| 187 | } |
---|
[503] | 188 | } |
---|
| 189 | { //bool EdgeMap |
---|
| 190 | Edge k; |
---|
[515] | 191 | typename Graph::template EdgeMap<bool> m(G); |
---|
| 192 | typename Graph::template EdgeMap<bool> const &cm = m; //Const map |
---|
| 193 | //Inicialize with default value |
---|
| 194 | typename Graph::template EdgeMap<bool> mdef(G,12); |
---|
| 195 | typename Graph::template EdgeMap<bool> mm(cm); //Copy |
---|
| 196 | typename Graph::template EdgeMap<int> dm(cm); //Copy from another type |
---|
[503] | 197 | bool v; |
---|
| 198 | v=m[k]; m[k]=v; m.set(k,v); |
---|
| 199 | v=cm[k]; |
---|
| 200 | |
---|
| 201 | m=cm; |
---|
| 202 | dm=cm; //Copy from another type |
---|
[504] | 203 | m=dm; //Copy to another type |
---|
[787] | 204 | { |
---|
| 205 | //Check the typedef's |
---|
| 206 | typename Graph::template EdgeMap<bool>::ValueType val; |
---|
| 207 | val=true; |
---|
| 208 | typename Graph::template EdgeMap<bool>::KeyType key; |
---|
| 209 | key= typename Graph::EdgeIt(G); |
---|
| 210 | } |
---|
[503] | 211 | } |
---|
| 212 | } |
---|
| 213 | |
---|
[592] | 214 | template<class Graph> void checkCompile(Graph &G) |
---|
| 215 | { |
---|
| 216 | checkCompileStaticGraph(G); |
---|
| 217 | |
---|
| 218 | typedef typename Graph::Node Node; |
---|
| 219 | typedef typename Graph::NodeIt NodeIt; |
---|
| 220 | typedef typename Graph::Edge Edge; |
---|
| 221 | typedef typename Graph::EdgeIt EdgeIt; |
---|
| 222 | typedef typename Graph::InEdgeIt InEdgeIt; |
---|
| 223 | typedef typename Graph::OutEdgeIt OutEdgeIt; |
---|
| 224 | |
---|
| 225 | Node n,m; |
---|
| 226 | n=G.addNode(); |
---|
| 227 | m=G.addNode(); |
---|
[774] | 228 | Edge e; |
---|
| 229 | e=G.addEdge(n,m); |
---|
[592] | 230 | |
---|
[774] | 231 | // G.clear(); |
---|
| 232 | } |
---|
| 233 | |
---|
| 234 | template<class Graph> void checkCompileErase(Graph &G) |
---|
| 235 | { |
---|
| 236 | typedef typename Graph::Node Node; |
---|
| 237 | typedef typename Graph::Edge Edge; |
---|
| 238 | Node n; |
---|
| 239 | Edge e; |
---|
| 240 | G.erase(n); |
---|
| 241 | G.erase(e); |
---|
| 242 | } |
---|
| 243 | |
---|
| 244 | template<class Graph> void checkCompileEraseEdge(Graph &G) |
---|
| 245 | { |
---|
| 246 | typedef typename Graph::Edge Edge; |
---|
| 247 | Edge e; |
---|
| 248 | G.erase(e); |
---|
| 249 | } |
---|
| 250 | |
---|
| 251 | template<class Graph> void checkCompileFindEdge(Graph &G) |
---|
| 252 | { |
---|
| 253 | typedef typename Graph::NodeIt Node; |
---|
| 254 | typedef typename Graph::NodeIt NodeIt; |
---|
| 255 | |
---|
| 256 | G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); |
---|
| 257 | G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); |
---|
[592] | 258 | } |
---|
| 259 | |
---|
| 260 | |
---|
[503] | 261 | template<class Graph> void checkNodeList(Graph &G, int nn) |
---|
| 262 | { |
---|
| 263 | typename Graph::NodeIt n(G); |
---|
| 264 | for(int i=0;i<nn;i++) { |
---|
[774] | 265 | check(n!=INVALID,"Wrong Node list linking."); |
---|
| 266 | ++n; |
---|
[503] | 267 | } |
---|
[774] | 268 | check(n==INVALID,"Wrong Node list linking."); |
---|
[503] | 269 | } |
---|
| 270 | |
---|
| 271 | template<class Graph> void checkEdgeList(Graph &G, int nn) |
---|
| 272 | { |
---|
| 273 | typedef typename Graph::EdgeIt EdgeIt; |
---|
| 274 | |
---|
| 275 | EdgeIt e(G); |
---|
| 276 | for(int i=0;i<nn;i++) { |
---|
[774] | 277 | check(e!=INVALID,"Wrong Edge list linking."); |
---|
| 278 | ++e; |
---|
[503] | 279 | } |
---|
[774] | 280 | check(e==INVALID,"Wrong Edge list linking."); |
---|
[503] | 281 | } |
---|
| 282 | |
---|
| 283 | template<class Graph> void checkOutEdgeList(Graph &G, |
---|
| 284 | typename Graph::Node n, |
---|
| 285 | int nn) |
---|
| 286 | { |
---|
| 287 | typename Graph::OutEdgeIt e(G,n); |
---|
| 288 | for(int i=0;i<nn;i++) { |
---|
[774] | 289 | check(e!=INVALID,"Wrong OutEdge list linking."); |
---|
| 290 | ++e; |
---|
[503] | 291 | } |
---|
[774] | 292 | check(e==INVALID,"Wrong OutEdge list linking."); |
---|
[503] | 293 | } |
---|
| 294 | |
---|
| 295 | template<class Graph> void checkInEdgeList(Graph &G, |
---|
[774] | 296 | typename Graph::Node n, |
---|
| 297 | int nn) |
---|
[503] | 298 | { |
---|
| 299 | typename Graph::InEdgeIt e(G,n); |
---|
| 300 | for(int i=0;i<nn;i++) { |
---|
[774] | 301 | check(e!=INVALID,"Wrong InEdge list linking."); |
---|
| 302 | ++e; |
---|
[503] | 303 | } |
---|
[774] | 304 | check(e==INVALID,"Wrong InEdge list linking."); |
---|
[503] | 305 | } |
---|
| 306 | |
---|
[774] | 307 | ///\file |
---|
| 308 | ///\todo Checks head(), tail() as well; |
---|
| 309 | |
---|
[503] | 310 | template<class Graph> void bidirPetersen(Graph &G) |
---|
| 311 | { |
---|
| 312 | typedef typename Graph::Edge Edge; |
---|
| 313 | typedef typename Graph::EdgeIt EdgeIt; |
---|
| 314 | |
---|
| 315 | checkEdgeList(G,15); |
---|
| 316 | |
---|
| 317 | std::vector<Edge> ee; |
---|
| 318 | |
---|
[774] | 319 | for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e); |
---|
[503] | 320 | |
---|
| 321 | for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++) |
---|
| 322 | G.addEdge(G.head(*p),G.tail(*p)); |
---|
| 323 | } |
---|
| 324 | |
---|
| 325 | template<class Graph> void checkPetersen(Graph &G) |
---|
| 326 | { |
---|
| 327 | typedef typename Graph::Node Node; |
---|
| 328 | |
---|
| 329 | typedef typename Graph::EdgeIt EdgeIt; |
---|
| 330 | typedef typename Graph::NodeIt NodeIt; |
---|
| 331 | |
---|
| 332 | checkNodeList(G,10); |
---|
| 333 | checkEdgeList(G,30); |
---|
| 334 | |
---|
[774] | 335 | for(NodeIt n(G);n!=INVALID;++n) { |
---|
[503] | 336 | checkInEdgeList(G,n,3); |
---|
| 337 | checkOutEdgeList(G,n,3); |
---|
[774] | 338 | ++n; |
---|
[503] | 339 | } |
---|
| 340 | } |
---|
| 341 | |
---|
[774] | 342 | //Compile GraphSkeleton |
---|
[793] | 343 | template void checkCompileStaticGraph<skeleton::StaticGraphSkeleton> |
---|
| 344 | (skeleton::StaticGraphSkeleton &); |
---|
| 345 | |
---|
| 346 | template void checkCompile<skeleton::GraphSkeleton>(skeleton::GraphSkeleton &); |
---|
| 347 | |
---|
| 348 | template void checkCompileErase<skeleton::EraseableGraphSkeleton> |
---|
| 349 | (skeleton::EraseableGraphSkeleton &); |
---|
[733] | 350 | |
---|
[774] | 351 | //Compile SmartGraph |
---|
[503] | 352 | template void checkCompile<SmartGraph>(SmartGraph &); |
---|
[783] | 353 | |
---|
[774] | 354 | //Compile SymSmartGraph |
---|
[503] | 355 | template void checkCompile<SymSmartGraph>(SymSmartGraph &); |
---|
[774] | 356 | |
---|
| 357 | //Compile ListGraph |
---|
[578] | 358 | template void checkCompile<ListGraph>(ListGraph &); |
---|
[774] | 359 | template void checkCompileErase<ListGraph>(ListGraph &); |
---|
| 360 | template void checkCompileFindEdge<ListGraph>(ListGraph &); |
---|
| 361 | |
---|
[783] | 362 | |
---|
[774] | 363 | //Compile SymListGraph |
---|
[578] | 364 | template void checkCompile<SymListGraph>(SymListGraph &); |
---|
[774] | 365 | template void checkCompileErase<SymListGraph>(SymListGraph &); |
---|
| 366 | template void checkCompileFindEdge<SymListGraph>(SymListGraph &); |
---|
| 367 | |
---|
| 368 | //Compile FullGraph |
---|
[592] | 369 | template void checkCompileStaticGraph<FullGraph>(FullGraph &); |
---|
[774] | 370 | template void checkCompileFindEdge<FullGraph>(FullGraph &); |
---|
[550] | 371 | |
---|
[774] | 372 | //Compile EdgeSet <ListGraph> |
---|
[579] | 373 | template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
---|
[774] | 374 | template |
---|
| 375 | void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
---|
| 376 | template |
---|
| 377 | void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
---|
| 378 | |
---|
| 379 | //Compile EdgeSet <NodeSet> |
---|
[717] | 380 | template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
---|
[774] | 381 | template |
---|
| 382 | void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
---|
| 383 | template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
---|
| 384 | |
---|
[503] | 385 | |
---|
| 386 | int main() |
---|
| 387 | { |
---|
| 388 | { |
---|
| 389 | SmartGraph G; |
---|
| 390 | addPetersen(G); |
---|
| 391 | bidirPetersen(G); |
---|
| 392 | checkPetersen(G); |
---|
| 393 | } |
---|
[578] | 394 | { |
---|
| 395 | ListGraph G; |
---|
| 396 | addPetersen(G); |
---|
| 397 | bidirPetersen(G); |
---|
| 398 | checkPetersen(G); |
---|
| 399 | } |
---|
[503] | 400 | { |
---|
| 401 | SymSmartGraph G; |
---|
| 402 | addPetersen(G); |
---|
| 403 | checkPetersen(G); |
---|
| 404 | } |
---|
[578] | 405 | { |
---|
| 406 | SymListGraph G; |
---|
| 407 | addPetersen(G); |
---|
| 408 | checkPetersen(G); |
---|
| 409 | } |
---|
[503] | 410 | |
---|
[774] | 411 | ///\file |
---|
| 412 | ///\todo map tests. |
---|
| 413 | ///\todo copy constr tests. |
---|
[503] | 414 | |
---|
| 415 | std::cout << __FILE__ ": All tests passed.\n"; |
---|
| 416 | |
---|
[579] | 417 | return 0; |
---|
[503] | 418 | } |
---|