# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1226063662 0
# Node ID 2d87dbd7f8c8bd68b7953e4a619e9e6e8f7e1e38
# Parent  7b6466ed488a4bfad7f13d4ec9ef2d645bf8c8b7# Parent  49d9a36b3b84393f37e6ac641f8173696ea335f1
Merge

diff -r 7b6466ed488a -r 2d87dbd7f8c8 lemon/smart_graph.h
--- a/lemon/smart_graph.h	Fri Nov 07 13:04:54 2008 +0000
+++ b/lemon/smart_graph.h	Fri Nov 07 13:14:22 2008 +0000
@@ -737,8 +737,8 @@
         dir.push_back(arcFromId(n));
         dir.push_back(arcFromId(n-1));
         Parent::notifier(Arc()).erase(dir);
-        nodes[arcs[n].target].first_out=arcs[n].next_out;
-        nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
+        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
+        nodes[arcs[n].target].first_out=arcs[n-1].next_out;
         arcs.pop_back();
         arcs.pop_back();
       }
diff -r 7b6466ed488a -r 2d87dbd7f8c8 test/digraph_test.cc
--- a/test/digraph_test.cc	Fri Nov 07 13:04:54 2008 +0000
+++ b/test/digraph_test.cc	Fri Nov 07 13:14:22 2008 +0000
@@ -28,7 +28,7 @@
 using namespace lemon::concepts;
 
 template <class Digraph>
-void checkDigraph() {
+void checkDigraphBuild() {
   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   Digraph G;
 
@@ -57,7 +57,208 @@
 
   checkGraphConArcList(G, 1);
 
-  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
+  Arc a2 = G.addArc(n2, n1),
+      a3 = G.addArc(n2, n3),
+      a4 = G.addArc(n2, n3);
+
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 4);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 3);
+  checkGraphOutArcList(G, n3, 0);
+
+  checkGraphInArcList(G, n1, 1);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 2);
+
+  checkGraphConArcList(G, 4);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+}
+
+template <class Digraph>
+void checkDigraphSplit() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+  Digraph G;
+  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
+  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
+      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
+
+  Node n4 = G.split(n2);
+
+  check(G.target(OutArcIt(G, n2)) == n4 &&
+        G.source(InArcIt(G, n4)) == n2,
+        "Wrong split.");
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 5);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 1);
+  checkGraphOutArcList(G, n3, 0);
+  checkGraphOutArcList(G, n4, 3);
+
+  checkGraphInArcList(G, n1, 1);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 2);
+  checkGraphInArcList(G, n4, 1);
+
+  checkGraphConArcList(G, 5);
+}
+
+template <class Digraph>
+void checkDigraphAlter() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+  Digraph G;
+  Node n1 = G.addNode(), n2 = G.addNode(),
+       n3 = G.addNode(), n4 = G.addNode();
+  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
+      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
+      a5 = G.addArc(n2, n4);
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 5);
+
+  // Check changeSource() and changeTarget()
+  G.changeTarget(a4, n1);
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 5);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 1);
+  checkGraphOutArcList(G, n3, 0);
+  checkGraphOutArcList(G, n4, 3);
+
+  checkGraphInArcList(G, n1, 2);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 1);
+  checkGraphInArcList(G, n4, 1);
+
+  checkGraphConArcList(G, 5);
+
+  G.changeSource(a4, n3);
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 5);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 1);
+  checkGraphOutArcList(G, n3, 1);
+  checkGraphOutArcList(G, n4, 2);
+
+  checkGraphInArcList(G, n1, 2);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 1);
+  checkGraphInArcList(G, n4, 1);
+
+  checkGraphConArcList(G, 5);
+
+  // Check contract()
+  G.contract(n2, n4, false);
+
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 5);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 3);
+  checkGraphOutArcList(G, n3, 1);
+
+  checkGraphInArcList(G, n1, 2);
+  checkGraphInArcList(G, n2, 2);
+  checkGraphInArcList(G, n3, 1);
+
+  checkGraphConArcList(G, 5);
+
+  G.contract(n2, n1);
+
+  checkGraphNodeList(G, 2);
+  checkGraphArcList(G, 3);
+
+  checkGraphOutArcList(G, n2, 2);
+  checkGraphOutArcList(G, n3, 1);
+
+  checkGraphInArcList(G, n2, 2);
+  checkGraphInArcList(G, n3, 1);
+
+  checkGraphConArcList(G, 3);
+}
+
+template <class Digraph>
+void checkDigraphErase() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+  Digraph G;
+  Node n1 = G.addNode(), n2 = G.addNode(),
+       n3 = G.addNode(), n4 = G.addNode();
+  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
+      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
+      a5 = G.addArc(n2, n4);
+
+  // Check arc deletion
+  G.erase(a1);
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 4);
+
+  checkGraphOutArcList(G, n1, 0);
+  checkGraphOutArcList(G, n2, 1);
+  checkGraphOutArcList(G, n3, 1);
+  checkGraphOutArcList(G, n4, 2);
+
+  checkGraphInArcList(G, n1, 2);
+  checkGraphInArcList(G, n2, 0);
+  checkGraphInArcList(G, n3, 1);
+  checkGraphInArcList(G, n4, 1);
+
+  checkGraphConArcList(G, 4);
+
+  // Check node deletion
+  G.erase(n4);
+
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 1);
+
+  checkGraphOutArcList(G, n1, 0);
+  checkGraphOutArcList(G, n2, 0);
+  checkGraphOutArcList(G, n3, 1);
+  checkGraphOutArcList(G, n4, 0);
+
+  checkGraphInArcList(G, n1, 1);
+  checkGraphInArcList(G, n2, 0);
+  checkGraphInArcList(G, n3, 0);
+  checkGraphInArcList(G, n4, 0);
+
+  checkGraphConArcList(G, 1);
+}
+
+
+template <class Digraph>
+void checkDigraphSnapshot() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+  Digraph G;
+  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
+  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
+      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
+
+  typename Digraph::Snapshot snapshot(G);
+
+  Node n = G.addNode();
+  G.addArc(n3, n);
+  G.addArc(n, n3);
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 6);
+
+  snapshot.restore();
+
   checkGraphNodeList(G, 3);
   checkGraphArcList(G, 4);
 
@@ -76,39 +277,15 @@
   checkGraphNodeMap(G);
   checkGraphArcMap(G);
 
-}
+  G.addNode();
+  snapshot.save(G);
 
-void checkFullDigraph(int num) {
-  typedef FullDigraph Digraph;
-  DIGRAPH_TYPEDEFS(Digraph);
-  Digraph G(num);
+  G.addArc(G.addNode(), G.addNode());
 
-  checkGraphNodeList(G, num);
-  checkGraphArcList(G, num * num);
+  snapshot.restore();
 
-  for (NodeIt n(G); n != INVALID; ++n) {
-    checkGraphOutArcList(G, n, num);
-    checkGraphInArcList(G, n, num);
-  }
-
-  checkGraphConArcList(G, num * num);
-
-  checkNodeIds(G);
-  checkArcIds(G);
-  checkGraphNodeMap(G);
-  checkGraphArcMap(G);
-
-  for (int i = 0; i < G.nodeNum(); ++i) {
-    check(G.index(G(i)) == i, "Wrong index");
-  }
-
-  for (NodeIt s(G); s != INVALID; ++s) {
-    for (NodeIt t(G); t != INVALID; ++t) {
-      Arc a = G.arc(s, t);
-      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
-    }
-  }
-
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 4);
 }
 
 void checkConcepts() {
@@ -195,13 +372,51 @@
   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
 }
 
+void checkFullDigraph(int num) {
+  typedef FullDigraph Digraph;
+  DIGRAPH_TYPEDEFS(Digraph);
+  Digraph G(num);
+
+  checkGraphNodeList(G, num);
+  checkGraphArcList(G, num * num);
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    checkGraphOutArcList(G, n, num);
+    checkGraphInArcList(G, n, num);
+  }
+
+  checkGraphConArcList(G, num * num);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+
+  for (int i = 0; i < G.nodeNum(); ++i) {
+    check(G.index(G(i)) == i, "Wrong index");
+  }
+
+  for (NodeIt s(G); s != INVALID; ++s) {
+    for (NodeIt t(G); t != INVALID; ++t) {
+      Arc a = G.arc(s, t);
+      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
+    }
+  }
+}
+
 void checkDigraphs() {
   { // Checking ListDigraph
-    checkDigraph<ListDigraph>();
+    checkDigraphBuild<ListDigraph>();
+    checkDigraphSplit<ListDigraph>();
+    checkDigraphAlter<ListDigraph>();
+    checkDigraphErase<ListDigraph>();
+    checkDigraphSnapshot<ListDigraph>();
     checkDigraphValidityErase<ListDigraph>();
   }
   { // Checking SmartDigraph
-    checkDigraph<SmartDigraph>();
+    checkDigraphBuild<SmartDigraph>();
+    checkDigraphSplit<SmartDigraph>();
+    checkDigraphSnapshot<SmartDigraph>();
     checkDigraphValidity<SmartDigraph>();
   }
   { // Checking FullDigraph
diff -r 7b6466ed488a -r 2d87dbd7f8c8 test/graph_test.cc
--- a/test/graph_test.cc	Fri Nov 07 13:04:54 2008 +0000
+++ b/test/graph_test.cc	Fri Nov 07 13:14:22 2008 +0000
@@ -30,12 +30,13 @@
 using namespace lemon::concepts;
 
 template <class Graph>
-void checkGraph() {
+void checkGraphBuild() {
   TEMPLATE_GRAPH_TYPEDEFS(Graph);
 
   Graph G;
   checkGraphNodeList(G, 0);
   checkGraphEdgeList(G, 0);
+  checkGraphArcList(G, 0);
 
   Node
     n1 = G.addNode(),
@@ -43,48 +44,36 @@
     n3 = G.addNode();
   checkGraphNodeList(G, 3);
   checkGraphEdgeList(G, 0);
+  checkGraphArcList(G, 0);
 
   Edge e1 = G.addEdge(n1, n2);
   check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
         "Wrong edge");
+
   checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 1);
   checkGraphArcList(G, 2);
-  checkGraphEdgeList(G, 1);
 
-  checkGraphOutArcList(G, n1, 1);
-  checkGraphOutArcList(G, n2, 1);
-  checkGraphOutArcList(G, n3, 0);
+  checkGraphIncEdgeArcLists(G, n1, 1);
+  checkGraphIncEdgeArcLists(G, n2, 1);
+  checkGraphIncEdgeArcLists(G, n3, 0);
 
-  checkGraphInArcList(G, n1, 1);
-  checkGraphInArcList(G, n2, 1);
-  checkGraphInArcList(G, n3, 0);
+  checkGraphConEdgeList(G, 1);
+  checkGraphConArcList(G, 2);
 
-  checkGraphIncEdgeList(G, n1, 1);
-  checkGraphIncEdgeList(G, n2, 1);
-  checkGraphIncEdgeList(G, n3, 0);
+  Edge e2 = G.addEdge(n2, n1),
+       e3 = G.addEdge(n2, n3);
 
-  checkGraphConArcList(G, 2);
-  checkGraphConEdgeList(G, 1);
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 3);
+  checkGraphArcList(G, 6);
 
-  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
-  checkGraphNodeList(G, 3);
-  checkGraphArcList(G, 6);
-  checkGraphEdgeList(G, 3);
+  checkGraphIncEdgeArcLists(G, n1, 2);
+  checkGraphIncEdgeArcLists(G, n2, 3);
+  checkGraphIncEdgeArcLists(G, n3, 1);
 
-  checkGraphOutArcList(G, n1, 2);
-  checkGraphOutArcList(G, n2, 3);
-  checkGraphOutArcList(G, n3, 1);
-
-  checkGraphInArcList(G, n1, 2);
-  checkGraphInArcList(G, n2, 3);
-  checkGraphInArcList(G, n3, 1);
-
-  checkGraphIncEdgeList(G, n1, 2);
-  checkGraphIncEdgeList(G, n2, 3);
-  checkGraphIncEdgeList(G, n3, 1);
-
+  checkGraphConEdgeList(G, 3);
   checkGraphConArcList(G, 6);
-  checkGraphConEdgeList(G, 3);
 
   checkArcDirections(G);
 
@@ -96,6 +85,183 @@
   checkGraphEdgeMap(G);
 }
 
+template <class Graph>
+void checkGraphAlter() {
+  TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+  Graph G;
+  Node n1 = G.addNode(), n2 = G.addNode(),
+       n3 = G.addNode(), n4 = G.addNode();
+  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
+       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
+       e5 = G.addEdge(n4, n3);
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 5);
+  checkGraphArcList(G, 10);
+
+  // Check changeU() and changeV()
+  if (G.u(e2) == n2) {
+    G.changeU(e2, n3);
+  } else {
+    G.changeV(e2, n3);
+  }
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 5);
+  checkGraphArcList(G, 10);
+
+  checkGraphIncEdgeArcLists(G, n1, 3);
+  checkGraphIncEdgeArcLists(G, n2, 2);
+  checkGraphIncEdgeArcLists(G, n3, 3);
+  checkGraphIncEdgeArcLists(G, n4, 2);
+
+  checkGraphConEdgeList(G, 5);
+  checkGraphConArcList(G, 10);
+
+  if (G.u(e2) == n1) {
+    G.changeU(e2, n2);
+  } else {
+    G.changeV(e2, n2);
+  }
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 5);
+  checkGraphArcList(G, 10);
+
+  checkGraphIncEdgeArcLists(G, n1, 2);
+  checkGraphIncEdgeArcLists(G, n2, 3);
+  checkGraphIncEdgeArcLists(G, n3, 3);
+  checkGraphIncEdgeArcLists(G, n4, 2);
+
+  checkGraphConEdgeList(G, 5);
+  checkGraphConArcList(G, 10);
+
+  // Check contract()
+  G.contract(n1, n4, false);
+
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 5);
+  checkGraphArcList(G, 10);
+
+  checkGraphIncEdgeArcLists(G, n1, 4);
+  checkGraphIncEdgeArcLists(G, n2, 3);
+  checkGraphIncEdgeArcLists(G, n3, 3);
+
+  checkGraphConEdgeList(G, 5);
+  checkGraphConArcList(G, 10);
+
+  G.contract(n2, n3);
+
+  checkGraphNodeList(G, 2);
+  checkGraphEdgeList(G, 3);
+  checkGraphArcList(G, 6);
+
+  checkGraphIncEdgeArcLists(G, n1, 4);
+  checkGraphIncEdgeArcLists(G, n2, 2);
+
+  checkGraphConEdgeList(G, 3);
+  checkGraphConArcList(G, 6);
+}
+
+template <class Graph>
+void checkGraphErase() {
+  TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+  Graph G;
+  Node n1 = G.addNode(), n2 = G.addNode(),
+       n3 = G.addNode(), n4 = G.addNode();
+  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
+       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
+       e5 = G.addEdge(n4, n3);
+
+  // Check edge deletion
+  G.erase(e2);
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 4);
+  checkGraphArcList(G, 8);
+
+  checkGraphIncEdgeArcLists(G, n1, 2);
+  checkGraphIncEdgeArcLists(G, n2, 2);
+  checkGraphIncEdgeArcLists(G, n3, 2);
+  checkGraphIncEdgeArcLists(G, n4, 2);
+
+  checkGraphConEdgeList(G, 4);
+  checkGraphConArcList(G, 8);
+
+  // Check node deletion
+  G.erase(n3);
+
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 2);
+  checkGraphArcList(G, 4);
+
+  checkGraphIncEdgeArcLists(G, n1, 2);
+  checkGraphIncEdgeArcLists(G, n2, 1);
+  checkGraphIncEdgeArcLists(G, n4, 1);
+
+  checkGraphConEdgeList(G, 2);
+  checkGraphConArcList(G, 4);
+}
+
+
+template <class Graph>
+void checkGraphSnapshot() {
+  TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+  Graph G;
+  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
+  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
+       e3 = G.addEdge(n2, n3);
+
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 3);
+  checkGraphArcList(G, 6);
+
+  typename Graph::Snapshot snapshot(G);
+
+  Node n = G.addNode();
+  G.addEdge(n3, n);
+  G.addEdge(n, n3);
+  G.addEdge(n3, n2);
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 6);
+  checkGraphArcList(G, 12);
+
+  snapshot.restore();
+
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 3);
+  checkGraphArcList(G, 6);
+
+  checkGraphIncEdgeArcLists(G, n1, 2);
+  checkGraphIncEdgeArcLists(G, n2, 3);
+  checkGraphIncEdgeArcLists(G, n3, 1);
+
+  checkGraphConEdgeList(G, 3);
+  checkGraphConArcList(G, 6);
+
+  checkNodeIds(G);
+  checkEdgeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphEdgeMap(G);
+  checkGraphArcMap(G);
+
+  G.addNode();
+  snapshot.save(G);
+
+  G.addEdge(G.addNode(), G.addNode());
+
+  snapshot.restore();
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 3);
+  checkGraphArcList(G, 6);
+}
+
 void checkFullGraph(int num) {
   typedef FullGraph Graph;
   GRAPH_TYPEDEFS(Graph);
@@ -366,11 +532,15 @@
 
 void checkGraphs() {
   { // Checking ListGraph
-    checkGraph<ListGraph>();
+    checkGraphBuild<ListGraph>();
+    checkGraphAlter<ListGraph>();
+    checkGraphErase<ListGraph>();
+    checkGraphSnapshot<ListGraph>();
     checkGraphValidityErase<ListGraph>();
   }
   { // Checking SmartGraph
-    checkGraph<SmartGraph>();
+    checkGraphBuild<SmartGraph>();
+    checkGraphSnapshot<SmartGraph>();
     checkGraphValidity<SmartGraph>();
   }
   { // Checking FullGraph
diff -r 7b6466ed488a -r 2d87dbd7f8c8 test/graph_test.h
--- a/test/graph_test.h	Fri Nov 07 13:04:54 2008 +0000
+++ b/test/graph_test.h	Fri Nov 07 13:14:22 2008 +0000
@@ -117,6 +117,15 @@
   }
 
   template <class Graph>
+  void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
+                                 int cnt)
+  {
+    checkGraphIncEdgeList(G, n, cnt);
+    checkGraphOutArcList(G, n, cnt);
+    checkGraphInArcList(G, n, cnt);
+  }
+
+  template <class Graph>
   void checkGraphConArcList(const Graph &G, int cnt) {
     int i = 0;
     for (typename Graph::NodeIt u(G); u != INVALID; ++u) {