1.1 --- a/test/graph_test.cc Fri Nov 07 12:00:53 2008 +0100
1.2 +++ b/test/graph_test.cc Fri Nov 07 12:15:16 2008 +0100
1.3 @@ -29,12 +29,13 @@
1.4 using namespace lemon::concepts;
1.5
1.6 template <class Graph>
1.7 -void checkGraph() {
1.8 +void checkGraphBuild() {
1.9 TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.10
1.11 Graph G;
1.12 checkGraphNodeList(G, 0);
1.13 checkGraphEdgeList(G, 0);
1.14 + checkGraphArcList(G, 0);
1.15
1.16 Node
1.17 n1 = G.addNode(),
1.18 @@ -42,48 +43,36 @@
1.19 n3 = G.addNode();
1.20 checkGraphNodeList(G, 3);
1.21 checkGraphEdgeList(G, 0);
1.22 + checkGraphArcList(G, 0);
1.23
1.24 Edge e1 = G.addEdge(n1, n2);
1.25 check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
1.26 "Wrong edge");
1.27 +
1.28 checkGraphNodeList(G, 3);
1.29 + checkGraphEdgeList(G, 1);
1.30 checkGraphArcList(G, 2);
1.31 - checkGraphEdgeList(G, 1);
1.32
1.33 - checkGraphOutArcList(G, n1, 1);
1.34 - checkGraphOutArcList(G, n2, 1);
1.35 - checkGraphOutArcList(G, n3, 0);
1.36 + checkGraphIncEdgeArcLists(G, n1, 1);
1.37 + checkGraphIncEdgeArcLists(G, n2, 1);
1.38 + checkGraphIncEdgeArcLists(G, n3, 0);
1.39
1.40 - checkGraphInArcList(G, n1, 1);
1.41 - checkGraphInArcList(G, n2, 1);
1.42 - checkGraphInArcList(G, n3, 0);
1.43 + checkGraphConEdgeList(G, 1);
1.44 + checkGraphConArcList(G, 2);
1.45
1.46 - checkGraphIncEdgeList(G, n1, 1);
1.47 - checkGraphIncEdgeList(G, n2, 1);
1.48 - checkGraphIncEdgeList(G, n3, 0);
1.49 + Edge e2 = G.addEdge(n2, n1),
1.50 + e3 = G.addEdge(n2, n3);
1.51
1.52 - checkGraphConArcList(G, 2);
1.53 - checkGraphConEdgeList(G, 1);
1.54 + checkGraphNodeList(G, 3);
1.55 + checkGraphEdgeList(G, 3);
1.56 + checkGraphArcList(G, 6);
1.57
1.58 - Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
1.59 - checkGraphNodeList(G, 3);
1.60 - checkGraphArcList(G, 6);
1.61 - checkGraphEdgeList(G, 3);
1.62 + checkGraphIncEdgeArcLists(G, n1, 2);
1.63 + checkGraphIncEdgeArcLists(G, n2, 3);
1.64 + checkGraphIncEdgeArcLists(G, n3, 1);
1.65
1.66 - checkGraphOutArcList(G, n1, 2);
1.67 - checkGraphOutArcList(G, n2, 3);
1.68 - checkGraphOutArcList(G, n3, 1);
1.69 -
1.70 - checkGraphInArcList(G, n1, 2);
1.71 - checkGraphInArcList(G, n2, 3);
1.72 - checkGraphInArcList(G, n3, 1);
1.73 -
1.74 - checkGraphIncEdgeList(G, n1, 2);
1.75 - checkGraphIncEdgeList(G, n2, 3);
1.76 - checkGraphIncEdgeList(G, n3, 1);
1.77 -
1.78 + checkGraphConEdgeList(G, 3);
1.79 checkGraphConArcList(G, 6);
1.80 - checkGraphConEdgeList(G, 3);
1.81
1.82 checkArcDirections(G);
1.83
1.84 @@ -95,6 +84,183 @@
1.85 checkGraphEdgeMap(G);
1.86 }
1.87
1.88 +template <class Graph>
1.89 +void checkGraphAlter() {
1.90 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.91 +
1.92 + Graph G;
1.93 + Node n1 = G.addNode(), n2 = G.addNode(),
1.94 + n3 = G.addNode(), n4 = G.addNode();
1.95 + Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
1.96 + e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
1.97 + e5 = G.addEdge(n4, n3);
1.98 +
1.99 + checkGraphNodeList(G, 4);
1.100 + checkGraphEdgeList(G, 5);
1.101 + checkGraphArcList(G, 10);
1.102 +
1.103 + // Check changeU() and changeV()
1.104 + if (G.u(e2) == n2) {
1.105 + G.changeU(e2, n3);
1.106 + } else {
1.107 + G.changeV(e2, n3);
1.108 + }
1.109 +
1.110 + checkGraphNodeList(G, 4);
1.111 + checkGraphEdgeList(G, 5);
1.112 + checkGraphArcList(G, 10);
1.113 +
1.114 + checkGraphIncEdgeArcLists(G, n1, 3);
1.115 + checkGraphIncEdgeArcLists(G, n2, 2);
1.116 + checkGraphIncEdgeArcLists(G, n3, 3);
1.117 + checkGraphIncEdgeArcLists(G, n4, 2);
1.118 +
1.119 + checkGraphConEdgeList(G, 5);
1.120 + checkGraphConArcList(G, 10);
1.121 +
1.122 + if (G.u(e2) == n1) {
1.123 + G.changeU(e2, n2);
1.124 + } else {
1.125 + G.changeV(e2, n2);
1.126 + }
1.127 +
1.128 + checkGraphNodeList(G, 4);
1.129 + checkGraphEdgeList(G, 5);
1.130 + checkGraphArcList(G, 10);
1.131 +
1.132 + checkGraphIncEdgeArcLists(G, n1, 2);
1.133 + checkGraphIncEdgeArcLists(G, n2, 3);
1.134 + checkGraphIncEdgeArcLists(G, n3, 3);
1.135 + checkGraphIncEdgeArcLists(G, n4, 2);
1.136 +
1.137 + checkGraphConEdgeList(G, 5);
1.138 + checkGraphConArcList(G, 10);
1.139 +
1.140 + // Check contract()
1.141 + G.contract(n1, n4, false);
1.142 +
1.143 + checkGraphNodeList(G, 3);
1.144 + checkGraphEdgeList(G, 5);
1.145 + checkGraphArcList(G, 10);
1.146 +
1.147 + checkGraphIncEdgeArcLists(G, n1, 4);
1.148 + checkGraphIncEdgeArcLists(G, n2, 3);
1.149 + checkGraphIncEdgeArcLists(G, n3, 3);
1.150 +
1.151 + checkGraphConEdgeList(G, 5);
1.152 + checkGraphConArcList(G, 10);
1.153 +
1.154 + G.contract(n2, n3);
1.155 +
1.156 + checkGraphNodeList(G, 2);
1.157 + checkGraphEdgeList(G, 3);
1.158 + checkGraphArcList(G, 6);
1.159 +
1.160 + checkGraphIncEdgeArcLists(G, n1, 4);
1.161 + checkGraphIncEdgeArcLists(G, n2, 2);
1.162 +
1.163 + checkGraphConEdgeList(G, 3);
1.164 + checkGraphConArcList(G, 6);
1.165 +}
1.166 +
1.167 +template <class Graph>
1.168 +void checkGraphErase() {
1.169 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.170 +
1.171 + Graph G;
1.172 + Node n1 = G.addNode(), n2 = G.addNode(),
1.173 + n3 = G.addNode(), n4 = G.addNode();
1.174 + Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
1.175 + e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
1.176 + e5 = G.addEdge(n4, n3);
1.177 +
1.178 + // Check edge deletion
1.179 + G.erase(e2);
1.180 +
1.181 + checkGraphNodeList(G, 4);
1.182 + checkGraphEdgeList(G, 4);
1.183 + checkGraphArcList(G, 8);
1.184 +
1.185 + checkGraphIncEdgeArcLists(G, n1, 2);
1.186 + checkGraphIncEdgeArcLists(G, n2, 2);
1.187 + checkGraphIncEdgeArcLists(G, n3, 2);
1.188 + checkGraphIncEdgeArcLists(G, n4, 2);
1.189 +
1.190 + checkGraphConEdgeList(G, 4);
1.191 + checkGraphConArcList(G, 8);
1.192 +
1.193 + // Check node deletion
1.194 + G.erase(n3);
1.195 +
1.196 + checkGraphNodeList(G, 3);
1.197 + checkGraphEdgeList(G, 2);
1.198 + checkGraphArcList(G, 4);
1.199 +
1.200 + checkGraphIncEdgeArcLists(G, n1, 2);
1.201 + checkGraphIncEdgeArcLists(G, n2, 1);
1.202 + checkGraphIncEdgeArcLists(G, n4, 1);
1.203 +
1.204 + checkGraphConEdgeList(G, 2);
1.205 + checkGraphConArcList(G, 4);
1.206 +}
1.207 +
1.208 +
1.209 +template <class Graph>
1.210 +void checkGraphSnapshot() {
1.211 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.212 +
1.213 + Graph G;
1.214 + Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
1.215 + Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
1.216 + e3 = G.addEdge(n2, n3);
1.217 +
1.218 + checkGraphNodeList(G, 3);
1.219 + checkGraphEdgeList(G, 3);
1.220 + checkGraphArcList(G, 6);
1.221 +
1.222 + typename Graph::Snapshot snapshot(G);
1.223 +
1.224 + Node n = G.addNode();
1.225 + G.addEdge(n3, n);
1.226 + G.addEdge(n, n3);
1.227 + G.addEdge(n3, n2);
1.228 +
1.229 + checkGraphNodeList(G, 4);
1.230 + checkGraphEdgeList(G, 6);
1.231 + checkGraphArcList(G, 12);
1.232 +
1.233 + snapshot.restore();
1.234 +
1.235 + checkGraphNodeList(G, 3);
1.236 + checkGraphEdgeList(G, 3);
1.237 + checkGraphArcList(G, 6);
1.238 +
1.239 + checkGraphIncEdgeArcLists(G, n1, 2);
1.240 + checkGraphIncEdgeArcLists(G, n2, 3);
1.241 + checkGraphIncEdgeArcLists(G, n3, 1);
1.242 +
1.243 + checkGraphConEdgeList(G, 3);
1.244 + checkGraphConArcList(G, 6);
1.245 +
1.246 + checkNodeIds(G);
1.247 + checkEdgeIds(G);
1.248 + checkArcIds(G);
1.249 + checkGraphNodeMap(G);
1.250 + checkGraphEdgeMap(G);
1.251 + checkGraphArcMap(G);
1.252 +
1.253 + G.addNode();
1.254 + snapshot.save(G);
1.255 +
1.256 + G.addEdge(G.addNode(), G.addNode());
1.257 +
1.258 + snapshot.restore();
1.259 +
1.260 + checkGraphNodeList(G, 4);
1.261 + checkGraphEdgeList(G, 3);
1.262 + checkGraphArcList(G, 6);
1.263 +}
1.264 +
1.265 void checkConcepts() {
1.266 { // Checking graph components
1.267 checkConcept<BaseGraphComponent, BaseGraphComponent >();
1.268 @@ -234,11 +400,15 @@
1.269
1.270 void checkGraphs() {
1.271 { // Checking ListGraph
1.272 - checkGraph<ListGraph>();
1.273 + checkGraphBuild<ListGraph>();
1.274 + checkGraphAlter<ListGraph>();
1.275 + checkGraphErase<ListGraph>();
1.276 + checkGraphSnapshot<ListGraph>();
1.277 checkGraphValidityErase<ListGraph>();
1.278 }
1.279 { // Checking SmartGraph
1.280 - checkGraph<SmartGraph>();
1.281 + checkGraphBuild<SmartGraph>();
1.282 + checkGraphSnapshot<SmartGraph>();
1.283 checkGraphValidity<SmartGraph>();
1.284 }
1.285 // { // Checking FullGraph