# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1251018801 -7200
# Node ID 456fa5bc32569263c32886a2f1ebbc62b50e2500
# Parent  9d6c3e8b242116ee952bd8b070c797e9bdafa3d6
Much better implementation for node splitting (#311)
in ListDigraph. This solution is the same as the one that
is used in SmartDigraph. It is much faster and does not
invalidate any iterator like the former implementation.

diff -r 9d6c3e8b2421 -r 456fa5bc3256 lemon/list_graph.h
--- a/lemon/list_graph.h	Sun Aug 23 11:11:49 2009 +0200
+++ b/lemon/list_graph.h	Sun Aug 23 11:13:21 2009 +0200
@@ -32,6 +32,8 @@
 
 namespace lemon {
 
+  class ListDigraph;
+
   class ListDigraphBase {
 
   protected:
@@ -62,6 +64,7 @@
 
     class Node {
       friend class ListDigraphBase;
+      friend class ListDigraph;
     protected:
 
       int id;
@@ -77,6 +80,7 @@
 
     class Arc {
       friend class ListDigraphBase;
+      friend class ListDigraph;
     protected:
 
       int id;
@@ -467,18 +471,16 @@
     ///is also added.
     ///\return The newly created node.
     ///
-    ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing
-    ///arcs of node \c n are invalidated. Other iterators remain valid.
+    ///\note All iterators remain valid.
     ///
     ///\warning This functionality cannot be used together with the
     ///Snapshot feature.
     Node split(Node n, bool connect = true) {
       Node b = addNode();
-      for(OutArcIt e(*this,n);e!=INVALID;) {
-        OutArcIt f=e;
-        ++f;
-        changeSource(e,b);
-        e=f;
+      nodes[b.id].first_out=nodes[n.id].first_out;
+      nodes[n.id].first_out=-1;
+      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
+        arcs[i].source=b.id;
       }
       if (connect) addArc(n,b);
       return b;