Changeset 374:49d9a36b3b84 in lemon1.2
 Timestamp:
 11/07/08 12:15:16 (12 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 test
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

test/digraph_test.cc
r228 r374 30 30 31 31 template <class Digraph> 32 void checkDigraph () {32 void checkDigraphBuild() { 33 33 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 34 34 Digraph G; … … 59 59 checkGraphConArcList(G, 1); 60 60 61 Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 61 Arc a2 = G.addArc(n2, n1), 62 a3 = G.addArc(n2, n3), 63 a4 = G.addArc(n2, n3); 64 62 65 checkGraphNodeList(G, 3); 63 66 checkGraphArcList(G, 4); … … 77 80 checkGraphNodeMap(G); 78 81 checkGraphArcMap(G); 79 80 } 81 82 } 83 84 template <class Digraph> 85 void checkDigraphSplit() { 86 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 87 88 Digraph G; 89 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 90 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 91 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 92 93 Node n4 = G.split(n2); 94 95 check(G.target(OutArcIt(G, n2)) == n4 && 96 G.source(InArcIt(G, n4)) == n2, 97 "Wrong split."); 98 99 checkGraphNodeList(G, 4); 100 checkGraphArcList(G, 5); 101 102 checkGraphOutArcList(G, n1, 1); 103 checkGraphOutArcList(G, n2, 1); 104 checkGraphOutArcList(G, n3, 0); 105 checkGraphOutArcList(G, n4, 3); 106 107 checkGraphInArcList(G, n1, 1); 108 checkGraphInArcList(G, n2, 1); 109 checkGraphInArcList(G, n3, 2); 110 checkGraphInArcList(G, n4, 1); 111 112 checkGraphConArcList(G, 5); 113 } 114 115 template <class Digraph> 116 void checkDigraphAlter() { 117 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 118 119 Digraph G; 120 Node n1 = G.addNode(), n2 = G.addNode(), 121 n3 = G.addNode(), n4 = G.addNode(); 122 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), 123 a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3), 124 a5 = G.addArc(n2, n4); 125 126 checkGraphNodeList(G, 4); 127 checkGraphArcList(G, 5); 128 129 // Check changeSource() and changeTarget() 130 G.changeTarget(a4, n1); 131 132 checkGraphNodeList(G, 4); 133 checkGraphArcList(G, 5); 134 135 checkGraphOutArcList(G, n1, 1); 136 checkGraphOutArcList(G, n2, 1); 137 checkGraphOutArcList(G, n3, 0); 138 checkGraphOutArcList(G, n4, 3); 139 140 checkGraphInArcList(G, n1, 2); 141 checkGraphInArcList(G, n2, 1); 142 checkGraphInArcList(G, n3, 1); 143 checkGraphInArcList(G, n4, 1); 144 145 checkGraphConArcList(G, 5); 146 147 G.changeSource(a4, n3); 148 149 checkGraphNodeList(G, 4); 150 checkGraphArcList(G, 5); 151 152 checkGraphOutArcList(G, n1, 1); 153 checkGraphOutArcList(G, n2, 1); 154 checkGraphOutArcList(G, n3, 1); 155 checkGraphOutArcList(G, n4, 2); 156 157 checkGraphInArcList(G, n1, 2); 158 checkGraphInArcList(G, n2, 1); 159 checkGraphInArcList(G, n3, 1); 160 checkGraphInArcList(G, n4, 1); 161 162 checkGraphConArcList(G, 5); 163 164 // Check contract() 165 G.contract(n2, n4, false); 166 167 checkGraphNodeList(G, 3); 168 checkGraphArcList(G, 5); 169 170 checkGraphOutArcList(G, n1, 1); 171 checkGraphOutArcList(G, n2, 3); 172 checkGraphOutArcList(G, n3, 1); 173 174 checkGraphInArcList(G, n1, 2); 175 checkGraphInArcList(G, n2, 2); 176 checkGraphInArcList(G, n3, 1); 177 178 checkGraphConArcList(G, 5); 179 180 G.contract(n2, n1); 181 182 checkGraphNodeList(G, 2); 183 checkGraphArcList(G, 3); 184 185 checkGraphOutArcList(G, n2, 2); 186 checkGraphOutArcList(G, n3, 1); 187 188 checkGraphInArcList(G, n2, 2); 189 checkGraphInArcList(G, n3, 1); 190 191 checkGraphConArcList(G, 3); 192 } 193 194 template <class Digraph> 195 void checkDigraphErase() { 196 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 197 198 Digraph G; 199 Node n1 = G.addNode(), n2 = G.addNode(), 200 n3 = G.addNode(), n4 = G.addNode(); 201 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), 202 a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1), 203 a5 = G.addArc(n2, n4); 204 205 // Check arc deletion 206 G.erase(a1); 207 208 checkGraphNodeList(G, 4); 209 checkGraphArcList(G, 4); 210 211 checkGraphOutArcList(G, n1, 0); 212 checkGraphOutArcList(G, n2, 1); 213 checkGraphOutArcList(G, n3, 1); 214 checkGraphOutArcList(G, n4, 2); 215 216 checkGraphInArcList(G, n1, 2); 217 checkGraphInArcList(G, n2, 0); 218 checkGraphInArcList(G, n3, 1); 219 checkGraphInArcList(G, n4, 1); 220 221 checkGraphConArcList(G, 4); 222 223 // Check node deletion 224 G.erase(n4); 225 226 checkGraphNodeList(G, 3); 227 checkGraphArcList(G, 1); 228 229 checkGraphOutArcList(G, n1, 0); 230 checkGraphOutArcList(G, n2, 0); 231 checkGraphOutArcList(G, n3, 1); 232 checkGraphOutArcList(G, n4, 0); 233 234 checkGraphInArcList(G, n1, 1); 235 checkGraphInArcList(G, n2, 0); 236 checkGraphInArcList(G, n3, 0); 237 checkGraphInArcList(G, n4, 0); 238 239 checkGraphConArcList(G, 1); 240 } 241 242 243 template <class Digraph> 244 void checkDigraphSnapshot() { 245 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 246 247 Digraph G; 248 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 249 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 250 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 251 252 typename Digraph::Snapshot snapshot(G); 253 254 Node n = G.addNode(); 255 G.addArc(n3, n); 256 G.addArc(n, n3); 257 258 checkGraphNodeList(G, 4); 259 checkGraphArcList(G, 6); 260 261 snapshot.restore(); 262 263 checkGraphNodeList(G, 3); 264 checkGraphArcList(G, 4); 265 266 checkGraphOutArcList(G, n1, 1); 267 checkGraphOutArcList(G, n2, 3); 268 checkGraphOutArcList(G, n3, 0); 269 270 checkGraphInArcList(G, n1, 1); 271 checkGraphInArcList(G, n2, 1); 272 checkGraphInArcList(G, n3, 2); 273 274 checkGraphConArcList(G, 4); 275 276 checkNodeIds(G); 277 checkArcIds(G); 278 checkGraphNodeMap(G); 279 checkGraphArcMap(G); 280 281 G.addNode(); 282 snapshot.save(G); 283 284 G.addArc(G.addNode(), G.addNode()); 285 286 snapshot.restore(); 287 288 checkGraphNodeList(G, 4); 289 checkGraphArcList(G, 4); 290 } 82 291 83 292 void checkConcepts() { … … 170 379 void checkDigraphs() { 171 380 { // Checking ListDigraph 172 checkDigraph<ListDigraph>(); 381 checkDigraphBuild<ListDigraph>(); 382 checkDigraphSplit<ListDigraph>(); 383 checkDigraphAlter<ListDigraph>(); 384 checkDigraphErase<ListDigraph>(); 385 checkDigraphSnapshot<ListDigraph>(); 173 386 checkDigraphValidityErase<ListDigraph>(); 174 387 } 175 388 { // Checking SmartDigraph 176 checkDigraph<SmartDigraph>(); 389 checkDigraphBuild<SmartDigraph>(); 390 checkDigraphSplit<SmartDigraph>(); 391 checkDigraphSnapshot<SmartDigraph>(); 177 392 checkDigraphValidity<SmartDigraph>(); 178 393 } 
test/graph_test.cc
r228 r374 30 30 31 31 template <class Graph> 32 void checkGraph () {32 void checkGraphBuild() { 33 33 TEMPLATE_GRAPH_TYPEDEFS(Graph); 34 34 … … 36 36 checkGraphNodeList(G, 0); 37 37 checkGraphEdgeList(G, 0); 38 checkGraphArcList(G, 0); 38 39 39 40 Node … … 43 44 checkGraphNodeList(G, 3); 44 45 checkGraphEdgeList(G, 0); 46 checkGraphArcList(G, 0); 45 47 46 48 Edge e1 = G.addEdge(n1, n2); 47 49 check((G.u(e1) == n1 && G.v(e1) == n2)  (G.u(e1) == n2 && G.v(e1) == n1), 48 50 "Wrong edge"); 49 checkGraphNodeList(G, 3); 51 52 checkGraphNodeList(G, 3); 53 checkGraphEdgeList(G, 1); 50 54 checkGraphArcList(G, 2); 51 checkGraphEdgeList(G, 1); 52 53 checkGraphOutArcList(G, n1, 1); 54 checkGraphOutArcList(G, n2, 1); 55 checkGraphOutArcList(G, n3, 0); 56 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 55 56 checkGraphIncEdgeArcLists(G, n1, 1); 57 checkGraphIncEdgeArcLists(G, n2, 1); 58 checkGraphIncEdgeArcLists(G, n3, 0); 59 60 checkGraphConEdgeList(G, 1); 65 61 checkGraphConArcList(G, 2); 66 checkGraphConEdgeList(G, 1); 67 68 Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); 69 checkGraphNodeList(G, 3); 62 63 Edge e2 = G.addEdge(n2, n1), 64 e3 = G.addEdge(n2, n3); 65 66 checkGraphNodeList(G, 3); 67 checkGraphEdgeList(G, 3); 70 68 checkGraphArcList(G, 6); 71 checkGraphEdgeList(G, 3); 72 73 checkGraphOutArcList(G, n1, 2); 74 checkGraphOutArcList(G, n2, 3); 75 checkGraphOutArcList(G, n3, 1); 76 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 69 70 checkGraphIncEdgeArcLists(G, n1, 2); 71 checkGraphIncEdgeArcLists(G, n2, 3); 72 checkGraphIncEdgeArcLists(G, n3, 1); 73 74 checkGraphConEdgeList(G, 3); 85 75 checkGraphConArcList(G, 6); 86 checkGraphConEdgeList(G, 3);87 76 88 77 checkArcDirections(G); … … 94 83 checkGraphArcMap(G); 95 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 … … 235 401 void checkGraphs() { 236 402 { // Checking ListGraph 237 checkGraph<ListGraph>(); 403 checkGraphBuild<ListGraph>(); 404 checkGraphAlter<ListGraph>(); 405 checkGraphErase<ListGraph>(); 406 checkGraphSnapshot<ListGraph>(); 238 407 checkGraphValidityErase<ListGraph>(); 239 408 } 240 409 { // Checking SmartGraph 241 checkGraph<SmartGraph>(); 410 checkGraphBuild<SmartGraph>(); 411 checkGraphSnapshot<SmartGraph>(); 242 412 checkGraphValidity<SmartGraph>(); 243 413 } 
test/graph_test.h
r263 r374 115 115 check(e==INVALID,"Wrong IncEdge list linking."); 116 116 check(countIncEdges(G,n)==cnt,"Wrong IncEdge number."); 117 } 118 119 template <class Graph> 120 void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n, 121 int cnt) 122 { 123 checkGraphIncEdgeList(G, n, cnt); 124 checkGraphOutArcList(G, n, cnt); 125 checkGraphInArcList(G, n, cnt); 117 126 } 118 127
Note: See TracChangeset
for help on using the changeset viewer.