Much better implementation for node splitting (#311)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sun, 23 Aug 2009 11:13:21 +0200
changeset 738456fa5bc3256
parent 737 9d6c3e8b2421
child 740 819ca5b50de0
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.
lemon/list_graph.h
     1.1 --- a/lemon/list_graph.h	Sun Aug 23 11:11:49 2009 +0200
     1.2 +++ b/lemon/list_graph.h	Sun Aug 23 11:13:21 2009 +0200
     1.3 @@ -32,6 +32,8 @@
     1.4  
     1.5  namespace lemon {
     1.6  
     1.7 +  class ListDigraph;
     1.8 +
     1.9    class ListDigraphBase {
    1.10  
    1.11    protected:
    1.12 @@ -62,6 +64,7 @@
    1.13  
    1.14      class Node {
    1.15        friend class ListDigraphBase;
    1.16 +      friend class ListDigraph;
    1.17      protected:
    1.18  
    1.19        int id;
    1.20 @@ -77,6 +80,7 @@
    1.21  
    1.22      class Arc {
    1.23        friend class ListDigraphBase;
    1.24 +      friend class ListDigraph;
    1.25      protected:
    1.26  
    1.27        int id;
    1.28 @@ -467,18 +471,16 @@
    1.29      ///is also added.
    1.30      ///\return The newly created node.
    1.31      ///
    1.32 -    ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing
    1.33 -    ///arcs of node \c n are invalidated. Other iterators remain valid.
    1.34 +    ///\note All iterators remain valid.
    1.35      ///
    1.36      ///\warning This functionality cannot be used together with the
    1.37      ///Snapshot feature.
    1.38      Node split(Node n, bool connect = true) {
    1.39        Node b = addNode();
    1.40 -      for(OutArcIt e(*this,n);e!=INVALID;) {
    1.41 -        OutArcIt f=e;
    1.42 -        ++f;
    1.43 -        changeSource(e,b);
    1.44 -        e=f;
    1.45 +      nodes[b.id].first_out=nodes[n.id].first_out;
    1.46 +      nodes[n.id].first_out=-1;
    1.47 +      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
    1.48 +        arcs[i].source=b.id;
    1.49        }
    1.50        if (connect) addArc(n,b);
    1.51        return b;