author Peter Kovacs Fri, 07 Nov 2008 12:15:16 +0100 changeset 374 49d9a36b3b84 parent 373 5a3d689ea770 child 375 2d87dbd7f8c8
Extend test cases for graphs and digraphs (#172)
 test/digraph_test.cc file | annotate | diff | comparison | revisions test/graph_test.cc file | annotate | diff | comparison | revisions test/graph_test.h file | annotate | diff | comparison | revisions
```     1.1 --- a/test/digraph_test.cc	Fri Nov 07 12:00:53 2008 +0100
1.2 +++ b/test/digraph_test.cc	Fri Nov 07 12:15:16 2008 +0100
1.3 @@ -29,7 +29,7 @@
1.4  using namespace lemon::concepts;
1.5
1.6  template <class Digraph>
1.7 -void checkDigraph() {
1.8 +void checkDigraphBuild() {
1.9    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.10    Digraph G;
1.11
1.12 @@ -58,7 +58,208 @@
1.13
1.14    checkGraphConArcList(G, 1);
1.15
1.17 +  Arc a2 = G.addArc(n2, n1),
1.18 +      a3 = G.addArc(n2, n3),
1.19 +      a4 = G.addArc(n2, n3);
1.20 +
1.21 +  checkGraphNodeList(G, 3);
1.22 +  checkGraphArcList(G, 4);
1.23 +
1.24 +  checkGraphOutArcList(G, n1, 1);
1.25 +  checkGraphOutArcList(G, n2, 3);
1.26 +  checkGraphOutArcList(G, n3, 0);
1.27 +
1.28 +  checkGraphInArcList(G, n1, 1);
1.29 +  checkGraphInArcList(G, n2, 1);
1.30 +  checkGraphInArcList(G, n3, 2);
1.31 +
1.32 +  checkGraphConArcList(G, 4);
1.33 +
1.34 +  checkNodeIds(G);
1.35 +  checkArcIds(G);
1.36 +  checkGraphNodeMap(G);
1.37 +  checkGraphArcMap(G);
1.38 +}
1.39 +
1.40 +template <class Digraph>
1.41 +void checkDigraphSplit() {
1.42 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.43 +
1.44 +  Digraph G;
1.48 +
1.49 +  Node n4 = G.split(n2);
1.50 +
1.51 +  check(G.target(OutArcIt(G, n2)) == n4 &&
1.52 +        G.source(InArcIt(G, n4)) == n2,
1.53 +        "Wrong split.");
1.54 +
1.55 +  checkGraphNodeList(G, 4);
1.56 +  checkGraphArcList(G, 5);
1.57 +
1.58 +  checkGraphOutArcList(G, n1, 1);
1.59 +  checkGraphOutArcList(G, n2, 1);
1.60 +  checkGraphOutArcList(G, n3, 0);
1.61 +  checkGraphOutArcList(G, n4, 3);
1.62 +
1.63 +  checkGraphInArcList(G, n1, 1);
1.64 +  checkGraphInArcList(G, n2, 1);
1.65 +  checkGraphInArcList(G, n3, 2);
1.66 +  checkGraphInArcList(G, n4, 1);
1.67 +
1.68 +  checkGraphConArcList(G, 5);
1.69 +}
1.70 +
1.71 +template <class Digraph>
1.72 +void checkDigraphAlter() {
1.73 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.74 +
1.75 +  Digraph G;
1.80 +      a5 = G.addArc(n2, n4);
1.81 +
1.82 +  checkGraphNodeList(G, 4);
1.83 +  checkGraphArcList(G, 5);
1.84 +
1.85 +  // Check changeSource() and changeTarget()
1.86 +  G.changeTarget(a4, n1);
1.87 +
1.88 +  checkGraphNodeList(G, 4);
1.89 +  checkGraphArcList(G, 5);
1.90 +
1.91 +  checkGraphOutArcList(G, n1, 1);
1.92 +  checkGraphOutArcList(G, n2, 1);
1.93 +  checkGraphOutArcList(G, n3, 0);
1.94 +  checkGraphOutArcList(G, n4, 3);
1.95 +
1.96 +  checkGraphInArcList(G, n1, 2);
1.97 +  checkGraphInArcList(G, n2, 1);
1.98 +  checkGraphInArcList(G, n3, 1);
1.99 +  checkGraphInArcList(G, n4, 1);
1.100 +
1.101 +  checkGraphConArcList(G, 5);
1.102 +
1.103 +  G.changeSource(a4, n3);
1.104 +
1.105 +  checkGraphNodeList(G, 4);
1.106 +  checkGraphArcList(G, 5);
1.107 +
1.108 +  checkGraphOutArcList(G, n1, 1);
1.109 +  checkGraphOutArcList(G, n2, 1);
1.110 +  checkGraphOutArcList(G, n3, 1);
1.111 +  checkGraphOutArcList(G, n4, 2);
1.112 +
1.113 +  checkGraphInArcList(G, n1, 2);
1.114 +  checkGraphInArcList(G, n2, 1);
1.115 +  checkGraphInArcList(G, n3, 1);
1.116 +  checkGraphInArcList(G, n4, 1);
1.117 +
1.118 +  checkGraphConArcList(G, 5);
1.119 +
1.120 +  // Check contract()
1.121 +  G.contract(n2, n4, false);
1.122 +
1.123 +  checkGraphNodeList(G, 3);
1.124 +  checkGraphArcList(G, 5);
1.125 +
1.126 +  checkGraphOutArcList(G, n1, 1);
1.127 +  checkGraphOutArcList(G, n2, 3);
1.128 +  checkGraphOutArcList(G, n3, 1);
1.129 +
1.130 +  checkGraphInArcList(G, n1, 2);
1.131 +  checkGraphInArcList(G, n2, 2);
1.132 +  checkGraphInArcList(G, n3, 1);
1.133 +
1.134 +  checkGraphConArcList(G, 5);
1.135 +
1.136 +  G.contract(n2, n1);
1.137 +
1.138 +  checkGraphNodeList(G, 2);
1.139 +  checkGraphArcList(G, 3);
1.140 +
1.141 +  checkGraphOutArcList(G, n2, 2);
1.142 +  checkGraphOutArcList(G, n3, 1);
1.143 +
1.144 +  checkGraphInArcList(G, n2, 2);
1.145 +  checkGraphInArcList(G, n3, 1);
1.146 +
1.147 +  checkGraphConArcList(G, 3);
1.148 +}
1.149 +
1.150 +template <class Digraph>
1.151 +void checkDigraphErase() {
1.152 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.153 +
1.154 +  Digraph G;
1.159 +      a5 = G.addArc(n2, n4);
1.160 +
1.161 +  // Check arc deletion
1.162 +  G.erase(a1);
1.163 +
1.164 +  checkGraphNodeList(G, 4);
1.165 +  checkGraphArcList(G, 4);
1.166 +
1.167 +  checkGraphOutArcList(G, n1, 0);
1.168 +  checkGraphOutArcList(G, n2, 1);
1.169 +  checkGraphOutArcList(G, n3, 1);
1.170 +  checkGraphOutArcList(G, n4, 2);
1.171 +
1.172 +  checkGraphInArcList(G, n1, 2);
1.173 +  checkGraphInArcList(G, n2, 0);
1.174 +  checkGraphInArcList(G, n3, 1);
1.175 +  checkGraphInArcList(G, n4, 1);
1.176 +
1.177 +  checkGraphConArcList(G, 4);
1.178 +
1.179 +  // Check node deletion
1.180 +  G.erase(n4);
1.181 +
1.182 +  checkGraphNodeList(G, 3);
1.183 +  checkGraphArcList(G, 1);
1.184 +
1.185 +  checkGraphOutArcList(G, n1, 0);
1.186 +  checkGraphOutArcList(G, n2, 0);
1.187 +  checkGraphOutArcList(G, n3, 1);
1.188 +  checkGraphOutArcList(G, n4, 0);
1.189 +
1.190 +  checkGraphInArcList(G, n1, 1);
1.191 +  checkGraphInArcList(G, n2, 0);
1.192 +  checkGraphInArcList(G, n3, 0);
1.193 +  checkGraphInArcList(G, n4, 0);
1.194 +
1.195 +  checkGraphConArcList(G, 1);
1.196 +}
1.197 +
1.198 +
1.199 +template <class Digraph>
1.200 +void checkDigraphSnapshot() {
1.201 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.202 +
1.203 +  Digraph G;
1.207 +
1.208 +  typename Digraph::Snapshot snapshot(G);
1.209 +
1.210 +  Node n = G.addNode();
1.213 +
1.214 +  checkGraphNodeList(G, 4);
1.215 +  checkGraphArcList(G, 6);
1.216 +
1.217 +  snapshot.restore();
1.218 +
1.219    checkGraphNodeList(G, 3);
1.220    checkGraphArcList(G, 4);
1.221
1.222 @@ -77,9 +278,17 @@
1.223    checkGraphNodeMap(G);
1.224    checkGraphArcMap(G);
1.225
1.227 +  snapshot.save(G);
1.228 +
1.230 +
1.231 +  snapshot.restore();
1.232 +
1.233 +  checkGraphNodeList(G, 4);
1.234 +  checkGraphArcList(G, 4);
1.235  }
1.236
1.237 -
1.238  void checkConcepts() {
1.239    { // Checking digraph components
1.240      checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
1.241 @@ -169,11 +378,17 @@
1.242
1.243  void checkDigraphs() {
1.244    { // Checking ListDigraph
1.245 -    checkDigraph<ListDigraph>();
1.246 +    checkDigraphBuild<ListDigraph>();
1.247 +    checkDigraphSplit<ListDigraph>();
1.248 +    checkDigraphAlter<ListDigraph>();
1.249 +    checkDigraphErase<ListDigraph>();
1.250 +    checkDigraphSnapshot<ListDigraph>();
1.251      checkDigraphValidityErase<ListDigraph>();
1.252    }
1.253    { // Checking SmartDigraph
1.254 -    checkDigraph<SmartDigraph>();
1.255 +    checkDigraphBuild<SmartDigraph>();
1.256 +    checkDigraphSplit<SmartDigraph>();
1.257 +    checkDigraphSnapshot<SmartDigraph>();
1.258      checkDigraphValidity<SmartDigraph>();
1.259    }
1.260  }
```
```     2.1 --- a/test/graph_test.cc	Fri Nov 07 12:00:53 2008 +0100
2.2 +++ b/test/graph_test.cc	Fri Nov 07 12:15:16 2008 +0100
2.3 @@ -29,12 +29,13 @@
2.4  using namespace lemon::concepts;
2.5
2.6  template <class Graph>
2.7 -void checkGraph() {
2.8 +void checkGraphBuild() {
2.9    TEMPLATE_GRAPH_TYPEDEFS(Graph);
2.10
2.11    Graph G;
2.12    checkGraphNodeList(G, 0);
2.13    checkGraphEdgeList(G, 0);
2.14 +  checkGraphArcList(G, 0);
2.15
2.16    Node
2.18 @@ -42,48 +43,36 @@
2.20    checkGraphNodeList(G, 3);
2.21    checkGraphEdgeList(G, 0);
2.22 +  checkGraphArcList(G, 0);
2.23
2.24    Edge e1 = G.addEdge(n1, n2);
2.25    check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
2.26          "Wrong edge");
2.27 +
2.28    checkGraphNodeList(G, 3);
2.29 +  checkGraphEdgeList(G, 1);
2.30    checkGraphArcList(G, 2);
2.31 -  checkGraphEdgeList(G, 1);
2.32
2.33 -  checkGraphOutArcList(G, n1, 1);
2.34 -  checkGraphOutArcList(G, n2, 1);
2.35 -  checkGraphOutArcList(G, n3, 0);
2.36 +  checkGraphIncEdgeArcLists(G, n1, 1);
2.37 +  checkGraphIncEdgeArcLists(G, n2, 1);
2.38 +  checkGraphIncEdgeArcLists(G, n3, 0);
2.39
2.40 -  checkGraphInArcList(G, n1, 1);
2.41 -  checkGraphInArcList(G, n2, 1);
2.42 -  checkGraphInArcList(G, n3, 0);
2.43 +  checkGraphConEdgeList(G, 1);
2.44 +  checkGraphConArcList(G, 2);
2.45
2.46 -  checkGraphIncEdgeList(G, n1, 1);
2.47 -  checkGraphIncEdgeList(G, n2, 1);
2.48 -  checkGraphIncEdgeList(G, n3, 0);
2.49 +  Edge e2 = G.addEdge(n2, n1),
2.50 +       e3 = G.addEdge(n2, n3);
2.51
2.52 -  checkGraphConArcList(G, 2);
2.53 -  checkGraphConEdgeList(G, 1);
2.54 +  checkGraphNodeList(G, 3);
2.55 +  checkGraphEdgeList(G, 3);
2.56 +  checkGraphArcList(G, 6);
2.57
2.59 -  checkGraphNodeList(G, 3);
2.60 -  checkGraphArcList(G, 6);
2.61 -  checkGraphEdgeList(G, 3);
2.62 +  checkGraphIncEdgeArcLists(G, n1, 2);
2.63 +  checkGraphIncEdgeArcLists(G, n2, 3);
2.64 +  checkGraphIncEdgeArcLists(G, n3, 1);
2.65
2.66 -  checkGraphOutArcList(G, n1, 2);
2.67 -  checkGraphOutArcList(G, n2, 3);
2.68 -  checkGraphOutArcList(G, n3, 1);
2.69 -
2.70 -  checkGraphInArcList(G, n1, 2);
2.71 -  checkGraphInArcList(G, n2, 3);
2.72 -  checkGraphInArcList(G, n3, 1);
2.73 -
2.74 -  checkGraphIncEdgeList(G, n1, 2);
2.75 -  checkGraphIncEdgeList(G, n2, 3);
2.76 -  checkGraphIncEdgeList(G, n3, 1);
2.77 -
2.78 +  checkGraphConEdgeList(G, 3);
2.79    checkGraphConArcList(G, 6);
2.80 -  checkGraphConEdgeList(G, 3);
2.81
2.82    checkArcDirections(G);
2.83
2.84 @@ -95,6 +84,183 @@
2.85    checkGraphEdgeMap(G);
2.86  }
2.87
2.88 +template <class Graph>
2.89 +void checkGraphAlter() {
2.90 +  TEMPLATE_GRAPH_TYPEDEFS(Graph);
2.91 +
2.92 +  Graph G;
2.97 +       e5 = G.addEdge(n4, n3);
2.98 +
2.99 +  checkGraphNodeList(G, 4);
2.100 +  checkGraphEdgeList(G, 5);
2.101 +  checkGraphArcList(G, 10);
2.102 +
2.103 +  // Check changeU() and changeV()
2.104 +  if (G.u(e2) == n2) {
2.105 +    G.changeU(e2, n3);
2.106 +  } else {
2.107 +    G.changeV(e2, n3);
2.108 +  }
2.109 +
2.110 +  checkGraphNodeList(G, 4);
2.111 +  checkGraphEdgeList(G, 5);
2.112 +  checkGraphArcList(G, 10);
2.113 +
2.114 +  checkGraphIncEdgeArcLists(G, n1, 3);
2.115 +  checkGraphIncEdgeArcLists(G, n2, 2);
2.116 +  checkGraphIncEdgeArcLists(G, n3, 3);
2.117 +  checkGraphIncEdgeArcLists(G, n4, 2);
2.118 +
2.119 +  checkGraphConEdgeList(G, 5);
2.120 +  checkGraphConArcList(G, 10);
2.121 +
2.122 +  if (G.u(e2) == n1) {
2.123 +    G.changeU(e2, n2);
2.124 +  } else {
2.125 +    G.changeV(e2, n2);
2.126 +  }
2.127 +
2.128 +  checkGraphNodeList(G, 4);
2.129 +  checkGraphEdgeList(G, 5);
2.130 +  checkGraphArcList(G, 10);
2.131 +
2.132 +  checkGraphIncEdgeArcLists(G, n1, 2);
2.133 +  checkGraphIncEdgeArcLists(G, n2, 3);
2.134 +  checkGraphIncEdgeArcLists(G, n3, 3);
2.135 +  checkGraphIncEdgeArcLists(G, n4, 2);
2.136 +
2.137 +  checkGraphConEdgeList(G, 5);
2.138 +  checkGraphConArcList(G, 10);
2.139 +
2.140 +  // Check contract()
2.141 +  G.contract(n1, n4, false);
2.142 +
2.143 +  checkGraphNodeList(G, 3);
2.144 +  checkGraphEdgeList(G, 5);
2.145 +  checkGraphArcList(G, 10);
2.146 +
2.147 +  checkGraphIncEdgeArcLists(G, n1, 4);
2.148 +  checkGraphIncEdgeArcLists(G, n2, 3);
2.149 +  checkGraphIncEdgeArcLists(G, n3, 3);
2.150 +
2.151 +  checkGraphConEdgeList(G, 5);
2.152 +  checkGraphConArcList(G, 10);
2.153 +
2.154 +  G.contract(n2, n3);
2.155 +
2.156 +  checkGraphNodeList(G, 2);
2.157 +  checkGraphEdgeList(G, 3);
2.158 +  checkGraphArcList(G, 6);
2.159 +
2.160 +  checkGraphIncEdgeArcLists(G, n1, 4);
2.161 +  checkGraphIncEdgeArcLists(G, n2, 2);
2.162 +
2.163 +  checkGraphConEdgeList(G, 3);
2.164 +  checkGraphConArcList(G, 6);
2.165 +}
2.166 +
2.167 +template <class Graph>
2.168 +void checkGraphErase() {
2.169 +  TEMPLATE_GRAPH_TYPEDEFS(Graph);
2.170 +
2.171 +  Graph G;
2.176 +       e5 = G.addEdge(n4, n3);
2.177 +
2.178 +  // Check edge deletion
2.179 +  G.erase(e2);
2.180 +
2.181 +  checkGraphNodeList(G, 4);
2.182 +  checkGraphEdgeList(G, 4);
2.183 +  checkGraphArcList(G, 8);
2.184 +
2.185 +  checkGraphIncEdgeArcLists(G, n1, 2);
2.186 +  checkGraphIncEdgeArcLists(G, n2, 2);
2.187 +  checkGraphIncEdgeArcLists(G, n3, 2);
2.188 +  checkGraphIncEdgeArcLists(G, n4, 2);
2.189 +
2.190 +  checkGraphConEdgeList(G, 4);
2.191 +  checkGraphConArcList(G, 8);
2.192 +
2.193 +  // Check node deletion
2.194 +  G.erase(n3);
2.195 +
2.196 +  checkGraphNodeList(G, 3);
2.197 +  checkGraphEdgeList(G, 2);
2.198 +  checkGraphArcList(G, 4);
2.199 +
2.200 +  checkGraphIncEdgeArcLists(G, n1, 2);
2.201 +  checkGraphIncEdgeArcLists(G, n2, 1);
2.202 +  checkGraphIncEdgeArcLists(G, n4, 1);
2.203 +
2.204 +  checkGraphConEdgeList(G, 2);
2.205 +  checkGraphConArcList(G, 4);
2.206 +}
2.207 +
2.208 +
2.209 +template <class Graph>
2.210 +void checkGraphSnapshot() {
2.211 +  TEMPLATE_GRAPH_TYPEDEFS(Graph);
2.212 +
2.213 +  Graph G;
2.216 +       e3 = G.addEdge(n2, n3);
2.217 +
2.218 +  checkGraphNodeList(G, 3);
2.219 +  checkGraphEdgeList(G, 3);
2.220 +  checkGraphArcList(G, 6);
2.221 +
2.222 +  typename Graph::Snapshot snapshot(G);
2.223 +
2.224 +  Node n = G.addNode();
2.228 +
2.229 +  checkGraphNodeList(G, 4);
2.230 +  checkGraphEdgeList(G, 6);
2.231 +  checkGraphArcList(G, 12);
2.232 +
2.233 +  snapshot.restore();
2.234 +
2.235 +  checkGraphNodeList(G, 3);
2.236 +  checkGraphEdgeList(G, 3);
2.237 +  checkGraphArcList(G, 6);
2.238 +
2.239 +  checkGraphIncEdgeArcLists(G, n1, 2);
2.240 +  checkGraphIncEdgeArcLists(G, n2, 3);
2.241 +  checkGraphIncEdgeArcLists(G, n3, 1);
2.242 +
2.243 +  checkGraphConEdgeList(G, 3);
2.244 +  checkGraphConArcList(G, 6);
2.245 +
2.246 +  checkNodeIds(G);
2.247 +  checkEdgeIds(G);
2.248 +  checkArcIds(G);
2.249 +  checkGraphNodeMap(G);
2.250 +  checkGraphEdgeMap(G);
2.251 +  checkGraphArcMap(G);
2.252 +
2.254 +  snapshot.save(G);
2.255 +
2.257 +
2.258 +  snapshot.restore();
2.259 +
2.260 +  checkGraphNodeList(G, 4);
2.261 +  checkGraphEdgeList(G, 3);
2.262 +  checkGraphArcList(G, 6);
2.263 +}
2.264 +
2.265  void checkConcepts() {
2.266    { // Checking graph components
2.267      checkConcept<BaseGraphComponent, BaseGraphComponent >();
2.268 @@ -234,11 +400,15 @@
2.269
2.270  void checkGraphs() {
2.271    { // Checking ListGraph
2.272 -    checkGraph<ListGraph>();
2.273 +    checkGraphBuild<ListGraph>();
2.274 +    checkGraphAlter<ListGraph>();
2.275 +    checkGraphErase<ListGraph>();
2.276 +    checkGraphSnapshot<ListGraph>();
2.277      checkGraphValidityErase<ListGraph>();
2.278    }
2.279    { // Checking SmartGraph
2.280 -    checkGraph<SmartGraph>();
2.281 +    checkGraphBuild<SmartGraph>();
2.282 +    checkGraphSnapshot<SmartGraph>();
2.283      checkGraphValidity<SmartGraph>();
2.284    }
2.285  //   { // Checking FullGraph
```
```     3.1 --- a/test/graph_test.h	Fri Nov 07 12:00:53 2008 +0100
3.2 +++ b/test/graph_test.h	Fri Nov 07 12:15:16 2008 +0100
3.3 @@ -117,6 +117,15 @@
3.4    }
3.5
3.6    template <class Graph>
3.7 +  void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
3.8 +                                 int cnt)
3.9 +  {
3.10 +    checkGraphIncEdgeList(G, n, cnt);
3.11 +    checkGraphOutArcList(G, n, cnt);
3.12 +    checkGraphInArcList(G, n, cnt);
3.13 +  }
3.14 +
3.15 +  template <class Graph>
3.16    void checkGraphConArcList(const Graph &G, int cnt) {
3.17      int i = 0;
3.18      for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
```