Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Fri, 07 Nov 2008 13:14:22 +0000
changeset 3752d87dbd7f8c8
parent 372 7b6466ed488a
parent 374 49d9a36b3b84
child 376 4b2382fd80ef
Merge
lemon/smart_graph.h
test/digraph_test.cc
test/graph_test.cc
     1.1 --- a/lemon/smart_graph.h	Fri Nov 07 13:04:54 2008 +0000
     1.2 +++ b/lemon/smart_graph.h	Fri Nov 07 13:14:22 2008 +0000
     1.3 @@ -737,8 +737,8 @@
     1.4          dir.push_back(arcFromId(n));
     1.5          dir.push_back(arcFromId(n-1));
     1.6          Parent::notifier(Arc()).erase(dir);
     1.7 -        nodes[arcs[n].target].first_out=arcs[n].next_out;
     1.8 -        nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
     1.9 +        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
    1.10 +        nodes[arcs[n].target].first_out=arcs[n-1].next_out;
    1.11          arcs.pop_back();
    1.12          arcs.pop_back();
    1.13        }
     2.1 --- a/test/digraph_test.cc	Fri Nov 07 13:04:54 2008 +0000
     2.2 +++ b/test/digraph_test.cc	Fri Nov 07 13:14:22 2008 +0000
     2.3 @@ -28,7 +28,7 @@
     2.4  using namespace lemon::concepts;
     2.5  
     2.6  template <class Digraph>
     2.7 -void checkDigraph() {
     2.8 +void checkDigraphBuild() {
     2.9    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    2.10    Digraph G;
    2.11  
    2.12 @@ -57,7 +57,208 @@
    2.13  
    2.14    checkGraphConArcList(G, 1);
    2.15  
    2.16 -  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    2.17 +  Arc a2 = G.addArc(n2, n1),
    2.18 +      a3 = G.addArc(n2, n3),
    2.19 +      a4 = G.addArc(n2, n3);
    2.20 +
    2.21 +  checkGraphNodeList(G, 3);
    2.22 +  checkGraphArcList(G, 4);
    2.23 +
    2.24 +  checkGraphOutArcList(G, n1, 1);
    2.25 +  checkGraphOutArcList(G, n2, 3);
    2.26 +  checkGraphOutArcList(G, n3, 0);
    2.27 +
    2.28 +  checkGraphInArcList(G, n1, 1);
    2.29 +  checkGraphInArcList(G, n2, 1);
    2.30 +  checkGraphInArcList(G, n3, 2);
    2.31 +
    2.32 +  checkGraphConArcList(G, 4);
    2.33 +
    2.34 +  checkNodeIds(G);
    2.35 +  checkArcIds(G);
    2.36 +  checkGraphNodeMap(G);
    2.37 +  checkGraphArcMap(G);
    2.38 +}
    2.39 +
    2.40 +template <class Digraph>
    2.41 +void checkDigraphSplit() {
    2.42 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    2.43 +
    2.44 +  Digraph G;
    2.45 +  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    2.46 +  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    2.47 +      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    2.48 +
    2.49 +  Node n4 = G.split(n2);
    2.50 +
    2.51 +  check(G.target(OutArcIt(G, n2)) == n4 &&
    2.52 +        G.source(InArcIt(G, n4)) == n2,
    2.53 +        "Wrong split.");
    2.54 +
    2.55 +  checkGraphNodeList(G, 4);
    2.56 +  checkGraphArcList(G, 5);
    2.57 +
    2.58 +  checkGraphOutArcList(G, n1, 1);
    2.59 +  checkGraphOutArcList(G, n2, 1);
    2.60 +  checkGraphOutArcList(G, n3, 0);
    2.61 +  checkGraphOutArcList(G, n4, 3);
    2.62 +
    2.63 +  checkGraphInArcList(G, n1, 1);
    2.64 +  checkGraphInArcList(G, n2, 1);
    2.65 +  checkGraphInArcList(G, n3, 2);
    2.66 +  checkGraphInArcList(G, n4, 1);
    2.67 +
    2.68 +  checkGraphConArcList(G, 5);
    2.69 +}
    2.70 +
    2.71 +template <class Digraph>
    2.72 +void checkDigraphAlter() {
    2.73 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    2.74 +
    2.75 +  Digraph G;
    2.76 +  Node n1 = G.addNode(), n2 = G.addNode(),
    2.77 +       n3 = G.addNode(), n4 = G.addNode();
    2.78 +  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
    2.79 +      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
    2.80 +      a5 = G.addArc(n2, n4);
    2.81 +
    2.82 +  checkGraphNodeList(G, 4);
    2.83 +  checkGraphArcList(G, 5);
    2.84 +
    2.85 +  // Check changeSource() and changeTarget()
    2.86 +  G.changeTarget(a4, n1);
    2.87 +
    2.88 +  checkGraphNodeList(G, 4);
    2.89 +  checkGraphArcList(G, 5);
    2.90 +
    2.91 +  checkGraphOutArcList(G, n1, 1);
    2.92 +  checkGraphOutArcList(G, n2, 1);
    2.93 +  checkGraphOutArcList(G, n3, 0);
    2.94 +  checkGraphOutArcList(G, n4, 3);
    2.95 +
    2.96 +  checkGraphInArcList(G, n1, 2);
    2.97 +  checkGraphInArcList(G, n2, 1);
    2.98 +  checkGraphInArcList(G, n3, 1);
    2.99 +  checkGraphInArcList(G, n4, 1);
   2.100 +
   2.101 +  checkGraphConArcList(G, 5);
   2.102 +
   2.103 +  G.changeSource(a4, n3);
   2.104 +
   2.105 +  checkGraphNodeList(G, 4);
   2.106 +  checkGraphArcList(G, 5);
   2.107 +
   2.108 +  checkGraphOutArcList(G, n1, 1);
   2.109 +  checkGraphOutArcList(G, n2, 1);
   2.110 +  checkGraphOutArcList(G, n3, 1);
   2.111 +  checkGraphOutArcList(G, n4, 2);
   2.112 +
   2.113 +  checkGraphInArcList(G, n1, 2);
   2.114 +  checkGraphInArcList(G, n2, 1);
   2.115 +  checkGraphInArcList(G, n3, 1);
   2.116 +  checkGraphInArcList(G, n4, 1);
   2.117 +
   2.118 +  checkGraphConArcList(G, 5);
   2.119 +
   2.120 +  // Check contract()
   2.121 +  G.contract(n2, n4, false);
   2.122 +
   2.123 +  checkGraphNodeList(G, 3);
   2.124 +  checkGraphArcList(G, 5);
   2.125 +
   2.126 +  checkGraphOutArcList(G, n1, 1);
   2.127 +  checkGraphOutArcList(G, n2, 3);
   2.128 +  checkGraphOutArcList(G, n3, 1);
   2.129 +
   2.130 +  checkGraphInArcList(G, n1, 2);
   2.131 +  checkGraphInArcList(G, n2, 2);
   2.132 +  checkGraphInArcList(G, n3, 1);
   2.133 +
   2.134 +  checkGraphConArcList(G, 5);
   2.135 +
   2.136 +  G.contract(n2, n1);
   2.137 +
   2.138 +  checkGraphNodeList(G, 2);
   2.139 +  checkGraphArcList(G, 3);
   2.140 +
   2.141 +  checkGraphOutArcList(G, n2, 2);
   2.142 +  checkGraphOutArcList(G, n3, 1);
   2.143 +
   2.144 +  checkGraphInArcList(G, n2, 2);
   2.145 +  checkGraphInArcList(G, n3, 1);
   2.146 +
   2.147 +  checkGraphConArcList(G, 3);
   2.148 +}
   2.149 +
   2.150 +template <class Digraph>
   2.151 +void checkDigraphErase() {
   2.152 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   2.153 +
   2.154 +  Digraph G;
   2.155 +  Node n1 = G.addNode(), n2 = G.addNode(),
   2.156 +       n3 = G.addNode(), n4 = G.addNode();
   2.157 +  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
   2.158 +      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
   2.159 +      a5 = G.addArc(n2, n4);
   2.160 +
   2.161 +  // Check arc deletion
   2.162 +  G.erase(a1);
   2.163 +
   2.164 +  checkGraphNodeList(G, 4);
   2.165 +  checkGraphArcList(G, 4);
   2.166 +
   2.167 +  checkGraphOutArcList(G, n1, 0);
   2.168 +  checkGraphOutArcList(G, n2, 1);
   2.169 +  checkGraphOutArcList(G, n3, 1);
   2.170 +  checkGraphOutArcList(G, n4, 2);
   2.171 +
   2.172 +  checkGraphInArcList(G, n1, 2);
   2.173 +  checkGraphInArcList(G, n2, 0);
   2.174 +  checkGraphInArcList(G, n3, 1);
   2.175 +  checkGraphInArcList(G, n4, 1);
   2.176 +
   2.177 +  checkGraphConArcList(G, 4);
   2.178 +
   2.179 +  // Check node deletion
   2.180 +  G.erase(n4);
   2.181 +
   2.182 +  checkGraphNodeList(G, 3);
   2.183 +  checkGraphArcList(G, 1);
   2.184 +
   2.185 +  checkGraphOutArcList(G, n1, 0);
   2.186 +  checkGraphOutArcList(G, n2, 0);
   2.187 +  checkGraphOutArcList(G, n3, 1);
   2.188 +  checkGraphOutArcList(G, n4, 0);
   2.189 +
   2.190 +  checkGraphInArcList(G, n1, 1);
   2.191 +  checkGraphInArcList(G, n2, 0);
   2.192 +  checkGraphInArcList(G, n3, 0);
   2.193 +  checkGraphInArcList(G, n4, 0);
   2.194 +
   2.195 +  checkGraphConArcList(G, 1);
   2.196 +}
   2.197 +
   2.198 +
   2.199 +template <class Digraph>
   2.200 +void checkDigraphSnapshot() {
   2.201 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   2.202 +
   2.203 +  Digraph G;
   2.204 +  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
   2.205 +  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
   2.206 +      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
   2.207 +
   2.208 +  typename Digraph::Snapshot snapshot(G);
   2.209 +
   2.210 +  Node n = G.addNode();
   2.211 +  G.addArc(n3, n);
   2.212 +  G.addArc(n, n3);
   2.213 +
   2.214 +  checkGraphNodeList(G, 4);
   2.215 +  checkGraphArcList(G, 6);
   2.216 +
   2.217 +  snapshot.restore();
   2.218 +
   2.219    checkGraphNodeList(G, 3);
   2.220    checkGraphArcList(G, 4);
   2.221  
   2.222 @@ -76,39 +277,15 @@
   2.223    checkGraphNodeMap(G);
   2.224    checkGraphArcMap(G);
   2.225  
   2.226 -}
   2.227 +  G.addNode();
   2.228 +  snapshot.save(G);
   2.229  
   2.230 -void checkFullDigraph(int num) {
   2.231 -  typedef FullDigraph Digraph;
   2.232 -  DIGRAPH_TYPEDEFS(Digraph);
   2.233 -  Digraph G(num);
   2.234 +  G.addArc(G.addNode(), G.addNode());
   2.235  
   2.236 -  checkGraphNodeList(G, num);
   2.237 -  checkGraphArcList(G, num * num);
   2.238 +  snapshot.restore();
   2.239  
   2.240 -  for (NodeIt n(G); n != INVALID; ++n) {
   2.241 -    checkGraphOutArcList(G, n, num);
   2.242 -    checkGraphInArcList(G, n, num);
   2.243 -  }
   2.244 -
   2.245 -  checkGraphConArcList(G, num * num);
   2.246 -
   2.247 -  checkNodeIds(G);
   2.248 -  checkArcIds(G);
   2.249 -  checkGraphNodeMap(G);
   2.250 -  checkGraphArcMap(G);
   2.251 -
   2.252 -  for (int i = 0; i < G.nodeNum(); ++i) {
   2.253 -    check(G.index(G(i)) == i, "Wrong index");
   2.254 -  }
   2.255 -
   2.256 -  for (NodeIt s(G); s != INVALID; ++s) {
   2.257 -    for (NodeIt t(G); t != INVALID; ++t) {
   2.258 -      Arc a = G.arc(s, t);
   2.259 -      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
   2.260 -    }
   2.261 -  }
   2.262 -
   2.263 +  checkGraphNodeList(G, 4);
   2.264 +  checkGraphArcList(G, 4);
   2.265  }
   2.266  
   2.267  void checkConcepts() {
   2.268 @@ -195,13 +372,51 @@
   2.269    check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   2.270  }
   2.271  
   2.272 +void checkFullDigraph(int num) {
   2.273 +  typedef FullDigraph Digraph;
   2.274 +  DIGRAPH_TYPEDEFS(Digraph);
   2.275 +  Digraph G(num);
   2.276 +
   2.277 +  checkGraphNodeList(G, num);
   2.278 +  checkGraphArcList(G, num * num);
   2.279 +
   2.280 +  for (NodeIt n(G); n != INVALID; ++n) {
   2.281 +    checkGraphOutArcList(G, n, num);
   2.282 +    checkGraphInArcList(G, n, num);
   2.283 +  }
   2.284 +
   2.285 +  checkGraphConArcList(G, num * num);
   2.286 +
   2.287 +  checkNodeIds(G);
   2.288 +  checkArcIds(G);
   2.289 +  checkGraphNodeMap(G);
   2.290 +  checkGraphArcMap(G);
   2.291 +
   2.292 +  for (int i = 0; i < G.nodeNum(); ++i) {
   2.293 +    check(G.index(G(i)) == i, "Wrong index");
   2.294 +  }
   2.295 +
   2.296 +  for (NodeIt s(G); s != INVALID; ++s) {
   2.297 +    for (NodeIt t(G); t != INVALID; ++t) {
   2.298 +      Arc a = G.arc(s, t);
   2.299 +      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
   2.300 +    }
   2.301 +  }
   2.302 +}
   2.303 +
   2.304  void checkDigraphs() {
   2.305    { // Checking ListDigraph
   2.306 -    checkDigraph<ListDigraph>();
   2.307 +    checkDigraphBuild<ListDigraph>();
   2.308 +    checkDigraphSplit<ListDigraph>();
   2.309 +    checkDigraphAlter<ListDigraph>();
   2.310 +    checkDigraphErase<ListDigraph>();
   2.311 +    checkDigraphSnapshot<ListDigraph>();
   2.312      checkDigraphValidityErase<ListDigraph>();
   2.313    }
   2.314    { // Checking SmartDigraph
   2.315 -    checkDigraph<SmartDigraph>();
   2.316 +    checkDigraphBuild<SmartDigraph>();
   2.317 +    checkDigraphSplit<SmartDigraph>();
   2.318 +    checkDigraphSnapshot<SmartDigraph>();
   2.319      checkDigraphValidity<SmartDigraph>();
   2.320    }
   2.321    { // Checking FullDigraph
     3.1 --- a/test/graph_test.cc	Fri Nov 07 13:04:54 2008 +0000
     3.2 +++ b/test/graph_test.cc	Fri Nov 07 13:14:22 2008 +0000
     3.3 @@ -30,12 +30,13 @@
     3.4  using namespace lemon::concepts;
     3.5  
     3.6  template <class Graph>
     3.7 -void checkGraph() {
     3.8 +void checkGraphBuild() {
     3.9    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3.10  
    3.11    Graph G;
    3.12    checkGraphNodeList(G, 0);
    3.13    checkGraphEdgeList(G, 0);
    3.14 +  checkGraphArcList(G, 0);
    3.15  
    3.16    Node
    3.17      n1 = G.addNode(),
    3.18 @@ -43,48 +44,36 @@
    3.19      n3 = G.addNode();
    3.20    checkGraphNodeList(G, 3);
    3.21    checkGraphEdgeList(G, 0);
    3.22 +  checkGraphArcList(G, 0);
    3.23  
    3.24    Edge e1 = G.addEdge(n1, n2);
    3.25    check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    3.26          "Wrong edge");
    3.27 +
    3.28    checkGraphNodeList(G, 3);
    3.29 +  checkGraphEdgeList(G, 1);
    3.30    checkGraphArcList(G, 2);
    3.31 -  checkGraphEdgeList(G, 1);
    3.32  
    3.33 -  checkGraphOutArcList(G, n1, 1);
    3.34 -  checkGraphOutArcList(G, n2, 1);
    3.35 -  checkGraphOutArcList(G, n3, 0);
    3.36 +  checkGraphIncEdgeArcLists(G, n1, 1);
    3.37 +  checkGraphIncEdgeArcLists(G, n2, 1);
    3.38 +  checkGraphIncEdgeArcLists(G, n3, 0);
    3.39  
    3.40 -  checkGraphInArcList(G, n1, 1);
    3.41 -  checkGraphInArcList(G, n2, 1);
    3.42 -  checkGraphInArcList(G, n3, 0);
    3.43 +  checkGraphConEdgeList(G, 1);
    3.44 +  checkGraphConArcList(G, 2);
    3.45  
    3.46 -  checkGraphIncEdgeList(G, n1, 1);
    3.47 -  checkGraphIncEdgeList(G, n2, 1);
    3.48 -  checkGraphIncEdgeList(G, n3, 0);
    3.49 +  Edge e2 = G.addEdge(n2, n1),
    3.50 +       e3 = G.addEdge(n2, n3);
    3.51  
    3.52 -  checkGraphConArcList(G, 2);
    3.53 -  checkGraphConEdgeList(G, 1);
    3.54 +  checkGraphNodeList(G, 3);
    3.55 +  checkGraphEdgeList(G, 3);
    3.56 +  checkGraphArcList(G, 6);
    3.57  
    3.58 -  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    3.59 -  checkGraphNodeList(G, 3);
    3.60 -  checkGraphArcList(G, 6);
    3.61 -  checkGraphEdgeList(G, 3);
    3.62 +  checkGraphIncEdgeArcLists(G, n1, 2);
    3.63 +  checkGraphIncEdgeArcLists(G, n2, 3);
    3.64 +  checkGraphIncEdgeArcLists(G, n3, 1);
    3.65  
    3.66 -  checkGraphOutArcList(G, n1, 2);
    3.67 -  checkGraphOutArcList(G, n2, 3);
    3.68 -  checkGraphOutArcList(G, n3, 1);
    3.69 -
    3.70 -  checkGraphInArcList(G, n1, 2);
    3.71 -  checkGraphInArcList(G, n2, 3);
    3.72 -  checkGraphInArcList(G, n3, 1);
    3.73 -
    3.74 -  checkGraphIncEdgeList(G, n1, 2);
    3.75 -  checkGraphIncEdgeList(G, n2, 3);
    3.76 -  checkGraphIncEdgeList(G, n3, 1);
    3.77 -
    3.78 +  checkGraphConEdgeList(G, 3);
    3.79    checkGraphConArcList(G, 6);
    3.80 -  checkGraphConEdgeList(G, 3);
    3.81  
    3.82    checkArcDirections(G);
    3.83  
    3.84 @@ -96,6 +85,183 @@
    3.85    checkGraphEdgeMap(G);
    3.86  }
    3.87  
    3.88 +template <class Graph>
    3.89 +void checkGraphAlter() {
    3.90 +  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3.91 +
    3.92 +  Graph G;
    3.93 +  Node n1 = G.addNode(), n2 = G.addNode(),
    3.94 +       n3 = G.addNode(), n4 = G.addNode();
    3.95 +  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    3.96 +       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
    3.97 +       e5 = G.addEdge(n4, n3);
    3.98 +
    3.99 +  checkGraphNodeList(G, 4);
   3.100 +  checkGraphEdgeList(G, 5);
   3.101 +  checkGraphArcList(G, 10);
   3.102 +
   3.103 +  // Check changeU() and changeV()
   3.104 +  if (G.u(e2) == n2) {
   3.105 +    G.changeU(e2, n3);
   3.106 +  } else {
   3.107 +    G.changeV(e2, n3);
   3.108 +  }
   3.109 +
   3.110 +  checkGraphNodeList(G, 4);
   3.111 +  checkGraphEdgeList(G, 5);
   3.112 +  checkGraphArcList(G, 10);
   3.113 +
   3.114 +  checkGraphIncEdgeArcLists(G, n1, 3);
   3.115 +  checkGraphIncEdgeArcLists(G, n2, 2);
   3.116 +  checkGraphIncEdgeArcLists(G, n3, 3);
   3.117 +  checkGraphIncEdgeArcLists(G, n4, 2);
   3.118 +
   3.119 +  checkGraphConEdgeList(G, 5);
   3.120 +  checkGraphConArcList(G, 10);
   3.121 +
   3.122 +  if (G.u(e2) == n1) {
   3.123 +    G.changeU(e2, n2);
   3.124 +  } else {
   3.125 +    G.changeV(e2, n2);
   3.126 +  }
   3.127 +
   3.128 +  checkGraphNodeList(G, 4);
   3.129 +  checkGraphEdgeList(G, 5);
   3.130 +  checkGraphArcList(G, 10);
   3.131 +
   3.132 +  checkGraphIncEdgeArcLists(G, n1, 2);
   3.133 +  checkGraphIncEdgeArcLists(G, n2, 3);
   3.134 +  checkGraphIncEdgeArcLists(G, n3, 3);
   3.135 +  checkGraphIncEdgeArcLists(G, n4, 2);
   3.136 +
   3.137 +  checkGraphConEdgeList(G, 5);
   3.138 +  checkGraphConArcList(G, 10);
   3.139 +
   3.140 +  // Check contract()
   3.141 +  G.contract(n1, n4, false);
   3.142 +
   3.143 +  checkGraphNodeList(G, 3);
   3.144 +  checkGraphEdgeList(G, 5);
   3.145 +  checkGraphArcList(G, 10);
   3.146 +
   3.147 +  checkGraphIncEdgeArcLists(G, n1, 4);
   3.148 +  checkGraphIncEdgeArcLists(G, n2, 3);
   3.149 +  checkGraphIncEdgeArcLists(G, n3, 3);
   3.150 +
   3.151 +  checkGraphConEdgeList(G, 5);
   3.152 +  checkGraphConArcList(G, 10);
   3.153 +
   3.154 +  G.contract(n2, n3);
   3.155 +
   3.156 +  checkGraphNodeList(G, 2);
   3.157 +  checkGraphEdgeList(G, 3);
   3.158 +  checkGraphArcList(G, 6);
   3.159 +
   3.160 +  checkGraphIncEdgeArcLists(G, n1, 4);
   3.161 +  checkGraphIncEdgeArcLists(G, n2, 2);
   3.162 +
   3.163 +  checkGraphConEdgeList(G, 3);
   3.164 +  checkGraphConArcList(G, 6);
   3.165 +}
   3.166 +
   3.167 +template <class Graph>
   3.168 +void checkGraphErase() {
   3.169 +  TEMPLATE_GRAPH_TYPEDEFS(Graph);
   3.170 +
   3.171 +  Graph G;
   3.172 +  Node n1 = G.addNode(), n2 = G.addNode(),
   3.173 +       n3 = G.addNode(), n4 = G.addNode();
   3.174 +  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
   3.175 +       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
   3.176 +       e5 = G.addEdge(n4, n3);
   3.177 +
   3.178 +  // Check edge deletion
   3.179 +  G.erase(e2);
   3.180 +
   3.181 +  checkGraphNodeList(G, 4);
   3.182 +  checkGraphEdgeList(G, 4);
   3.183 +  checkGraphArcList(G, 8);
   3.184 +
   3.185 +  checkGraphIncEdgeArcLists(G, n1, 2);
   3.186 +  checkGraphIncEdgeArcLists(G, n2, 2);
   3.187 +  checkGraphIncEdgeArcLists(G, n3, 2);
   3.188 +  checkGraphIncEdgeArcLists(G, n4, 2);
   3.189 +
   3.190 +  checkGraphConEdgeList(G, 4);
   3.191 +  checkGraphConArcList(G, 8);
   3.192 +
   3.193 +  // Check node deletion
   3.194 +  G.erase(n3);
   3.195 +
   3.196 +  checkGraphNodeList(G, 3);
   3.197 +  checkGraphEdgeList(G, 2);
   3.198 +  checkGraphArcList(G, 4);
   3.199 +
   3.200 +  checkGraphIncEdgeArcLists(G, n1, 2);
   3.201 +  checkGraphIncEdgeArcLists(G, n2, 1);
   3.202 +  checkGraphIncEdgeArcLists(G, n4, 1);
   3.203 +
   3.204 +  checkGraphConEdgeList(G, 2);
   3.205 +  checkGraphConArcList(G, 4);
   3.206 +}
   3.207 +
   3.208 +
   3.209 +template <class Graph>
   3.210 +void checkGraphSnapshot() {
   3.211 +  TEMPLATE_GRAPH_TYPEDEFS(Graph);
   3.212 +
   3.213 +  Graph G;
   3.214 +  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
   3.215 +  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
   3.216 +       e3 = G.addEdge(n2, n3);
   3.217 +
   3.218 +  checkGraphNodeList(G, 3);
   3.219 +  checkGraphEdgeList(G, 3);
   3.220 +  checkGraphArcList(G, 6);
   3.221 +
   3.222 +  typename Graph::Snapshot snapshot(G);
   3.223 +
   3.224 +  Node n = G.addNode();
   3.225 +  G.addEdge(n3, n);
   3.226 +  G.addEdge(n, n3);
   3.227 +  G.addEdge(n3, n2);
   3.228 +
   3.229 +  checkGraphNodeList(G, 4);
   3.230 +  checkGraphEdgeList(G, 6);
   3.231 +  checkGraphArcList(G, 12);
   3.232 +
   3.233 +  snapshot.restore();
   3.234 +
   3.235 +  checkGraphNodeList(G, 3);
   3.236 +  checkGraphEdgeList(G, 3);
   3.237 +  checkGraphArcList(G, 6);
   3.238 +
   3.239 +  checkGraphIncEdgeArcLists(G, n1, 2);
   3.240 +  checkGraphIncEdgeArcLists(G, n2, 3);
   3.241 +  checkGraphIncEdgeArcLists(G, n3, 1);
   3.242 +
   3.243 +  checkGraphConEdgeList(G, 3);
   3.244 +  checkGraphConArcList(G, 6);
   3.245 +
   3.246 +  checkNodeIds(G);
   3.247 +  checkEdgeIds(G);
   3.248 +  checkArcIds(G);
   3.249 +  checkGraphNodeMap(G);
   3.250 +  checkGraphEdgeMap(G);
   3.251 +  checkGraphArcMap(G);
   3.252 +
   3.253 +  G.addNode();
   3.254 +  snapshot.save(G);
   3.255 +
   3.256 +  G.addEdge(G.addNode(), G.addNode());
   3.257 +
   3.258 +  snapshot.restore();
   3.259 +
   3.260 +  checkGraphNodeList(G, 4);
   3.261 +  checkGraphEdgeList(G, 3);
   3.262 +  checkGraphArcList(G, 6);
   3.263 +}
   3.264 +
   3.265  void checkFullGraph(int num) {
   3.266    typedef FullGraph Graph;
   3.267    GRAPH_TYPEDEFS(Graph);
   3.268 @@ -366,11 +532,15 @@
   3.269  
   3.270  void checkGraphs() {
   3.271    { // Checking ListGraph
   3.272 -    checkGraph<ListGraph>();
   3.273 +    checkGraphBuild<ListGraph>();
   3.274 +    checkGraphAlter<ListGraph>();
   3.275 +    checkGraphErase<ListGraph>();
   3.276 +    checkGraphSnapshot<ListGraph>();
   3.277      checkGraphValidityErase<ListGraph>();
   3.278    }
   3.279    { // Checking SmartGraph
   3.280 -    checkGraph<SmartGraph>();
   3.281 +    checkGraphBuild<SmartGraph>();
   3.282 +    checkGraphSnapshot<SmartGraph>();
   3.283      checkGraphValidity<SmartGraph>();
   3.284    }
   3.285    { // Checking FullGraph
     4.1 --- a/test/graph_test.h	Fri Nov 07 13:04:54 2008 +0000
     4.2 +++ b/test/graph_test.h	Fri Nov 07 13:14:22 2008 +0000
     4.3 @@ -117,6 +117,15 @@
     4.4    }
     4.5  
     4.6    template <class Graph>
     4.7 +  void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
     4.8 +                                 int cnt)
     4.9 +  {
    4.10 +    checkGraphIncEdgeList(G, n, cnt);
    4.11 +    checkGraphOutArcList(G, n, cnt);
    4.12 +    checkGraphInArcList(G, n, cnt);
    4.13 +  }
    4.14 +
    4.15 +  template <class Graph>
    4.16    void checkGraphConArcList(const Graph &G, int cnt) {
    4.17      int i = 0;
    4.18      for (typename Graph::NodeIt u(G); u != INVALID; ++u) {