Changes in / [388:2d87dbd7f8c8:385:7b6466ed488a] in lemon
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/smart_graph.h
r388 r384 738 738 dir.push_back(arcFromId(n-1)); 739 739 Parent::notifier(Arc()).erase(dir); 740 nodes[arcs[n -1].target].first_out=arcs[n].next_out;741 nodes[arcs[n ].target].first_out=arcs[n-1].next_out;740 nodes[arcs[n].target].first_out=arcs[n].next_out; 741 nodes[arcs[n-1].target].first_out=arcs[n-1].next_out; 742 742 arcs.pop_back(); 743 743 arcs.pop_back(); -
test/digraph_test.cc
r388 r377 29 29 30 30 template <class Digraph> 31 void checkDigraph Build() {31 void checkDigraph() { 32 32 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 33 33 Digraph G; … … 58 58 checkGraphConArcList(G, 1); 59 59 60 Arc a2 = G.addArc(n2, n1), 61 a3 = G.addArc(n2, n3), 62 a4 = G.addArc(n2, n3); 63 60 Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 64 61 checkGraphNodeList(G, 3); 65 62 checkGraphArcList(G, 4); … … 79 76 checkGraphNodeMap(G); 80 77 checkGraphArcMap(G); 81 } 82 83 template <class Digraph> 84 void checkDigraphSplit() { 85 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 86 87 Digraph G; 88 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 89 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 90 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 91 92 Node n4 = G.split(n2); 93 94 check(G.target(OutArcIt(G, n2)) == n4 && 95 G.source(InArcIt(G, n4)) == n2, 96 "Wrong split."); 97 98 checkGraphNodeList(G, 4); 99 checkGraphArcList(G, 5); 100 101 checkGraphOutArcList(G, n1, 1); 102 checkGraphOutArcList(G, n2, 1); 103 checkGraphOutArcList(G, n3, 0); 104 checkGraphOutArcList(G, n4, 3); 105 106 checkGraphInArcList(G, n1, 1); 107 checkGraphInArcList(G, n2, 1); 108 checkGraphInArcList(G, n3, 2); 109 checkGraphInArcList(G, n4, 1); 110 111 checkGraphConArcList(G, 5); 112 } 113 114 template <class Digraph> 115 void checkDigraphAlter() { 116 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 117 118 Digraph G; 119 Node n1 = G.addNode(), n2 = G.addNode(), 120 n3 = G.addNode(), n4 = G.addNode(); 121 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), 122 a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3), 123 a5 = G.addArc(n2, n4); 124 125 checkGraphNodeList(G, 4); 126 checkGraphArcList(G, 5); 127 128 // Check changeSource() and changeTarget() 129 G.changeTarget(a4, n1); 130 131 checkGraphNodeList(G, 4); 132 checkGraphArcList(G, 5); 133 134 checkGraphOutArcList(G, n1, 1); 135 checkGraphOutArcList(G, n2, 1); 136 checkGraphOutArcList(G, n3, 0); 137 checkGraphOutArcList(G, n4, 3); 138 139 checkGraphInArcList(G, n1, 2); 140 checkGraphInArcList(G, n2, 1); 141 checkGraphInArcList(G, n3, 1); 142 checkGraphInArcList(G, n4, 1); 143 144 checkGraphConArcList(G, 5); 145 146 G.changeSource(a4, n3); 147 148 checkGraphNodeList(G, 4); 149 checkGraphArcList(G, 5); 150 151 checkGraphOutArcList(G, n1, 1); 152 checkGraphOutArcList(G, n2, 1); 153 checkGraphOutArcList(G, n3, 1); 154 checkGraphOutArcList(G, n4, 2); 155 156 checkGraphInArcList(G, n1, 2); 157 checkGraphInArcList(G, n2, 1); 158 checkGraphInArcList(G, n3, 1); 159 checkGraphInArcList(G, n4, 1); 160 161 checkGraphConArcList(G, 5); 162 163 // Check contract() 164 G.contract(n2, n4, false); 165 166 checkGraphNodeList(G, 3); 167 checkGraphArcList(G, 5); 168 169 checkGraphOutArcList(G, n1, 1); 170 checkGraphOutArcList(G, n2, 3); 171 checkGraphOutArcList(G, n3, 1); 172 173 checkGraphInArcList(G, n1, 2); 174 checkGraphInArcList(G, n2, 2); 175 checkGraphInArcList(G, n3, 1); 176 177 checkGraphConArcList(G, 5); 178 179 G.contract(n2, n1); 180 181 checkGraphNodeList(G, 2); 182 checkGraphArcList(G, 3); 183 184 checkGraphOutArcList(G, n2, 2); 185 checkGraphOutArcList(G, n3, 1); 186 187 checkGraphInArcList(G, n2, 2); 188 checkGraphInArcList(G, n3, 1); 189 190 checkGraphConArcList(G, 3); 191 } 192 193 template <class Digraph> 194 void checkDigraphErase() { 195 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 196 197 Digraph G; 198 Node n1 = G.addNode(), n2 = G.addNode(), 199 n3 = G.addNode(), n4 = G.addNode(); 200 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), 201 a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1), 202 a5 = G.addArc(n2, n4); 203 204 // Check arc deletion 205 G.erase(a1); 206 207 checkGraphNodeList(G, 4); 208 checkGraphArcList(G, 4); 209 210 checkGraphOutArcList(G, n1, 0); 211 checkGraphOutArcList(G, n2, 1); 212 checkGraphOutArcList(G, n3, 1); 213 checkGraphOutArcList(G, n4, 2); 214 215 checkGraphInArcList(G, n1, 2); 216 checkGraphInArcList(G, n2, 0); 217 checkGraphInArcList(G, n3, 1); 218 checkGraphInArcList(G, n4, 1); 219 220 checkGraphConArcList(G, 4); 221 222 // Check node deletion 223 G.erase(n4); 224 225 checkGraphNodeList(G, 3); 226 checkGraphArcList(G, 1); 227 228 checkGraphOutArcList(G, n1, 0); 229 checkGraphOutArcList(G, n2, 0); 230 checkGraphOutArcList(G, n3, 1); 231 checkGraphOutArcList(G, n4, 0); 232 233 checkGraphInArcList(G, n1, 1); 234 checkGraphInArcList(G, n2, 0); 235 checkGraphInArcList(G, n3, 0); 236 checkGraphInArcList(G, n4, 0); 237 238 checkGraphConArcList(G, 1); 239 } 240 241 242 template <class Digraph> 243 void checkDigraphSnapshot() { 244 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 245 246 Digraph G; 247 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 248 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 249 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 250 251 typename Digraph::Snapshot snapshot(G); 252 253 Node n = G.addNode(); 254 G.addArc(n3, n); 255 G.addArc(n, n3); 256 257 checkGraphNodeList(G, 4); 258 checkGraphArcList(G, 6); 259 260 snapshot.restore(); 261 262 checkGraphNodeList(G, 3); 263 checkGraphArcList(G, 4); 264 265 checkGraphOutArcList(G, n1, 1); 266 checkGraphOutArcList(G, n2, 3); 267 checkGraphOutArcList(G, n3, 0); 268 269 checkGraphInArcList(G, n1, 1); 270 checkGraphInArcList(G, n2, 1); 271 checkGraphInArcList(G, n3, 2); 272 273 checkGraphConArcList(G, 4); 78 79 } 80 81 void checkFullDigraph(int num) { 82 typedef FullDigraph Digraph; 83 DIGRAPH_TYPEDEFS(Digraph); 84 Digraph G(num); 85 86 checkGraphNodeList(G, num); 87 checkGraphArcList(G, num * num); 88 89 for (NodeIt n(G); n != INVALID; ++n) { 90 checkGraphOutArcList(G, n, num); 91 checkGraphInArcList(G, n, num); 92 } 93 94 checkGraphConArcList(G, num * num); 274 95 275 96 checkNodeIds(G); … … 278 99 checkGraphArcMap(G); 279 100 280 G.addNode(); 281 snapshot.save(G); 282 283 G.addArc(G.addNode(), G.addNode()); 284 285 snapshot.restore(); 286 287 checkGraphNodeList(G, 4); 288 checkGraphArcList(G, 4); 101 for (int i = 0; i < G.nodeNum(); ++i) { 102 check(G.index(G(i)) == i, "Wrong index"); 103 } 104 105 for (NodeIt s(G); s != INVALID; ++s) { 106 for (NodeIt t(G); t != INVALID; ++t) { 107 Arc a = G.arc(s, t); 108 check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup"); 109 } 110 } 111 289 112 } 290 113 … … 373 196 } 374 197 375 void checkFullDigraph(int num) {376 typedef FullDigraph Digraph;377 DIGRAPH_TYPEDEFS(Digraph);378 Digraph G(num);379 380 checkGraphNodeList(G, num);381 checkGraphArcList(G, num * num);382 383 for (NodeIt n(G); n != INVALID; ++n) {384 checkGraphOutArcList(G, n, num);385 checkGraphInArcList(G, n, num);386 }387 388 checkGraphConArcList(G, num * num);389 390 checkNodeIds(G);391 checkArcIds(G);392 checkGraphNodeMap(G);393 checkGraphArcMap(G);394 395 for (int i = 0; i < G.nodeNum(); ++i) {396 check(G.index(G(i)) == i, "Wrong index");397 }398 399 for (NodeIt s(G); s != INVALID; ++s) {400 for (NodeIt t(G); t != INVALID; ++t) {401 Arc a = G.arc(s, t);402 check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");403 }404 }405 }406 407 198 void checkDigraphs() { 408 199 { // Checking ListDigraph 409 checkDigraphBuild<ListDigraph>(); 410 checkDigraphSplit<ListDigraph>(); 411 checkDigraphAlter<ListDigraph>(); 412 checkDigraphErase<ListDigraph>(); 413 checkDigraphSnapshot<ListDigraph>(); 200 checkDigraph<ListDigraph>(); 414 201 checkDigraphValidityErase<ListDigraph>(); 415 202 } 416 203 { // Checking SmartDigraph 417 checkDigraphBuild<SmartDigraph>(); 418 checkDigraphSplit<SmartDigraph>(); 419 checkDigraphSnapshot<SmartDigraph>(); 204 checkDigraph<SmartDigraph>(); 420 205 checkDigraphValidity<SmartDigraph>(); 421 206 } -
test/graph_test.cc
r388 r385 31 31 32 32 template <class Graph> 33 void checkGraph Build() {33 void checkGraph() { 34 34 TEMPLATE_GRAPH_TYPEDEFS(Graph); 35 35 … … 37 37 checkGraphNodeList(G, 0); 38 38 checkGraphEdgeList(G, 0); 39 checkGraphArcList(G, 0);40 39 41 40 Node … … 45 44 checkGraphNodeList(G, 3); 46 45 checkGraphEdgeList(G, 0); 47 checkGraphArcList(G, 0);48 46 49 47 Edge e1 = G.addEdge(n1, n2); 50 48 check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), 51 49 "Wrong edge"); 52 53 50 checkGraphNodeList(G, 3); 51 checkGraphArcList(G, 2); 54 52 checkGraphEdgeList(G, 1); 55 checkGraphArcList(G, 2); 56 57 checkGraphIncEdgeArcLists(G, n1, 1); 58 checkGraphIncEdgeArcLists(G, n2, 1); 59 checkGraphIncEdgeArcLists(G, n3, 0); 60 53 54 checkGraphOutArcList(G, n1, 1); 55 checkGraphOutArcList(G, n2, 1); 56 checkGraphOutArcList(G, n3, 0); 57 58 checkGraphInArcList(G, n1, 1); 59 checkGraphInArcList(G, n2, 1); 60 checkGraphInArcList(G, n3, 0); 61 62 checkGraphIncEdgeList(G, n1, 1); 63 checkGraphIncEdgeList(G, n2, 1); 64 checkGraphIncEdgeList(G, n3, 0); 65 66 checkGraphConArcList(G, 2); 61 67 checkGraphConEdgeList(G, 1); 62 checkGraphConArcList(G, 2); 63 64 Edge e2 = G.addEdge(n2, n1), 65 e3 = G.addEdge(n2, n3); 66 68 69 Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); 67 70 checkGraphNodeList(G, 3); 71 checkGraphArcList(G, 6); 68 72 checkGraphEdgeList(G, 3); 69 checkGraphArcList(G, 6); 70 71 checkGraphIncEdgeArcLists(G, n1, 2); 72 checkGraphIncEdgeArcLists(G, n2, 3); 73 checkGraphIncEdgeArcLists(G, n3, 1); 74 73 74 checkGraphOutArcList(G, n1, 2); 75 checkGraphOutArcList(G, n2, 3); 76 checkGraphOutArcList(G, n3, 1); 77 78 checkGraphInArcList(G, n1, 2); 79 checkGraphInArcList(G, n2, 3); 80 checkGraphInArcList(G, n3, 1); 81 82 checkGraphIncEdgeList(G, n1, 2); 83 checkGraphIncEdgeList(G, n2, 3); 84 checkGraphIncEdgeList(G, n3, 1); 85 86 checkGraphConArcList(G, 6); 75 87 checkGraphConEdgeList(G, 3); 76 checkGraphConArcList(G, 6);77 88 78 89 checkArcDirections(G); … … 84 95 checkGraphArcMap(G); 85 96 checkGraphEdgeMap(G); 86 }87 88 template <class Graph>89 void checkGraphAlter() {90 TEMPLATE_GRAPH_TYPEDEFS(Graph);91 92 Graph G;93 Node n1 = G.addNode(), n2 = G.addNode(),94 n3 = G.addNode(), n4 = G.addNode();95 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),96 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),97 e5 = G.addEdge(n4, n3);98 99 checkGraphNodeList(G, 4);100 checkGraphEdgeList(G, 5);101 checkGraphArcList(G, 10);102 103 // Check changeU() and changeV()104 if (G.u(e2) == n2) {105 G.changeU(e2, n3);106 } else {107 G.changeV(e2, n3);108 }109 110 checkGraphNodeList(G, 4);111 checkGraphEdgeList(G, 5);112 checkGraphArcList(G, 10);113 114 checkGraphIncEdgeArcLists(G, n1, 3);115 checkGraphIncEdgeArcLists(G, n2, 2);116 checkGraphIncEdgeArcLists(G, n3, 3);117 checkGraphIncEdgeArcLists(G, n4, 2);118 119 checkGraphConEdgeList(G, 5);120 checkGraphConArcList(G, 10);121 122 if (G.u(e2) == n1) {123 G.changeU(e2, n2);124 } else {125 G.changeV(e2, n2);126 }127 128 checkGraphNodeList(G, 4);129 checkGraphEdgeList(G, 5);130 checkGraphArcList(G, 10);131 132 checkGraphIncEdgeArcLists(G, n1, 2);133 checkGraphIncEdgeArcLists(G, n2, 3);134 checkGraphIncEdgeArcLists(G, n3, 3);135 checkGraphIncEdgeArcLists(G, n4, 2);136 137 checkGraphConEdgeList(G, 5);138 checkGraphConArcList(G, 10);139 140 // Check contract()141 G.contract(n1, n4, false);142 143 checkGraphNodeList(G, 3);144 checkGraphEdgeList(G, 5);145 checkGraphArcList(G, 10);146 147 checkGraphIncEdgeArcLists(G, n1, 4);148 checkGraphIncEdgeArcLists(G, n2, 3);149 checkGraphIncEdgeArcLists(G, n3, 3);150 151 checkGraphConEdgeList(G, 5);152 checkGraphConArcList(G, 10);153 154 G.contract(n2, n3);155 156 checkGraphNodeList(G, 2);157 checkGraphEdgeList(G, 3);158 checkGraphArcList(G, 6);159 160 checkGraphIncEdgeArcLists(G, n1, 4);161 checkGraphIncEdgeArcLists(G, n2, 2);162 163 checkGraphConEdgeList(G, 3);164 checkGraphConArcList(G, 6);165 }166 167 template <class Graph>168 void checkGraphErase() {169 TEMPLATE_GRAPH_TYPEDEFS(Graph);170 171 Graph G;172 Node n1 = G.addNode(), n2 = G.addNode(),173 n3 = G.addNode(), n4 = G.addNode();174 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),175 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),176 e5 = G.addEdge(n4, n3);177 178 // Check edge deletion179 G.erase(e2);180 181 checkGraphNodeList(G, 4);182 checkGraphEdgeList(G, 4);183 checkGraphArcList(G, 8);184 185 checkGraphIncEdgeArcLists(G, n1, 2);186 checkGraphIncEdgeArcLists(G, n2, 2);187 checkGraphIncEdgeArcLists(G, n3, 2);188 checkGraphIncEdgeArcLists(G, n4, 2);189 190 checkGraphConEdgeList(G, 4);191 checkGraphConArcList(G, 8);192 193 // Check node deletion194 G.erase(n3);195 196 checkGraphNodeList(G, 3);197 checkGraphEdgeList(G, 2);198 checkGraphArcList(G, 4);199 200 checkGraphIncEdgeArcLists(G, n1, 2);201 checkGraphIncEdgeArcLists(G, n2, 1);202 checkGraphIncEdgeArcLists(G, n4, 1);203 204 checkGraphConEdgeList(G, 2);205 checkGraphConArcList(G, 4);206 }207 208 209 template <class Graph>210 void checkGraphSnapshot() {211 TEMPLATE_GRAPH_TYPEDEFS(Graph);212 213 Graph G;214 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();215 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),216 e3 = G.addEdge(n2, n3);217 218 checkGraphNodeList(G, 3);219 checkGraphEdgeList(G, 3);220 checkGraphArcList(G, 6);221 222 typename Graph::Snapshot snapshot(G);223 224 Node n = G.addNode();225 G.addEdge(n3, n);226 G.addEdge(n, n3);227 G.addEdge(n3, n2);228 229 checkGraphNodeList(G, 4);230 checkGraphEdgeList(G, 6);231 checkGraphArcList(G, 12);232 233 snapshot.restore();234 235 checkGraphNodeList(G, 3);236 checkGraphEdgeList(G, 3);237 checkGraphArcList(G, 6);238 239 checkGraphIncEdgeArcLists(G, n1, 2);240 checkGraphIncEdgeArcLists(G, n2, 3);241 checkGraphIncEdgeArcLists(G, n3, 1);242 243 checkGraphConEdgeList(G, 3);244 checkGraphConArcList(G, 6);245 246 checkNodeIds(G);247 checkEdgeIds(G);248 checkArcIds(G);249 checkGraphNodeMap(G);250 checkGraphEdgeMap(G);251 checkGraphArcMap(G);252 253 G.addNode();254 snapshot.save(G);255 256 G.addEdge(G.addNode(), G.addNode());257 258 snapshot.restore();259 260 checkGraphNodeList(G, 4);261 checkGraphEdgeList(G, 3);262 checkGraphArcList(G, 6);263 97 } 264 98 … … 533 367 void checkGraphs() { 534 368 { // Checking ListGraph 535 checkGraphBuild<ListGraph>(); 536 checkGraphAlter<ListGraph>(); 537 checkGraphErase<ListGraph>(); 538 checkGraphSnapshot<ListGraph>(); 369 checkGraph<ListGraph>(); 539 370 checkGraphValidityErase<ListGraph>(); 540 371 } 541 372 { // Checking SmartGraph 542 checkGraphBuild<SmartGraph>(); 543 checkGraphSnapshot<SmartGraph>(); 373 checkGraph<SmartGraph>(); 544 374 checkGraphValidity<SmartGraph>(); 545 375 } -
test/graph_test.h
r387 r263 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);126 117 } 127 118
Note: See TracChangeset
for help on using the changeset viewer.