Changeset 738:456fa5bc3256 in lemon-1.2 for lemon

Timestamp:

08/23/09 11:13:21 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

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.

File:

• lemon/list_graph.h (modified) (5 diffs)

lemon/list_graph.h

@@ -33 +33 @@
 namespace lemon {
 
+  class ListDigraph;
+
   class ListDigraphBase {
 
@@ -63 +65 @@
     class Node {
       friend class ListDigraphBase;
+      friend class ListDigraph;
     protected:
 
@@ -78 +81 @@
     class Arc {
       friend class ListDigraphBase;
+      friend class ListDigraph;
     protected:
 
@@ -468 +472 @@
     ///\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
@@ -475 +478 @@
     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);