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