Changeset - r738:456fa5bc3256
« 737:9d6c3e
740:819ca5 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
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.
0 1 0
default
1 file changed with 9 insertions and 7 deletions:
lemon/list_graph.h
9
7
↑ Collapse diff ↑
lemon/list_graph.h
Show white space 12 line context
... ... 
@@ -29,12 +29,14 @@
29 29 

			




	30
	30
	
		
#include <vector>


			




	31
	31
	
		
#include <list>


			




	32
	32
	
		

			




	33
	33
	
		
namespace lemon {


			




	34
	34
	
		

			




	
	35
	
		
  class ListDigraph;


			




	
	36
	
		

			




	35
	37
	
		
  class ListDigraphBase {


			




	36
	38
	
		

			




	37
	39
	
		
  protected:


			




	38
	40
	
		
    struct NodeT {


			




	39
	41
	
		
      int first_in, first_out;


			




	40
	42
	
		
      int prev, next;


			




	...
	...
	
		
@@ -59,12 +61,13 @@


			




	59
	61
	
		
  public:


			




	60
	62
	
		

			




	61
	63
	
		
    typedef ListDigraphBase Digraph;


			




	62
	64
	
		

			




	63
	65
	
		
    class Node {


			




	64
	66
	
		
      friend class ListDigraphBase;


			




	
	67
	
		
      friend class ListDigraph;


			




	65
	68
	
		
    protected:


			




	66
	69
	
		

			




	67
	70
	
		
      int id;


			




	68
	71
	
		
      explicit Node(int pid) { id = pid;}


			




	69
	72
	
		

			




	70
	73
	
		
    public:


			




	...
	...
	
		
@@ -74,12 +77,13 @@


			




	74
	77
	
		
      bool operator!=(const Node& node) const {return id != node.id;}


			




	75
	78
	
		
      bool operator<(const Node& node) const {return id < node.id;}


			




	76
	79
	
		
    };


			




	77
	80
	
		

			




	78
	81
	
		
    class Arc {


			




	79
	82
	
		
      friend class ListDigraphBase;


			




	
	83
	
		
      friend class ListDigraph;


			




	80
	84
	
		
    protected:


			




	81
	85
	
		

			




	82
	86
	
		
      int id;


			




	83
	87
	
		
      explicit Arc(int pid) { id = pid;}


			




	84
	88
	
		

			




	85
	89
	
		
    public:


			




	...
	...
	
		
@@ -464,24 +468,22 @@


			




	464
	468
	
		
    ///is moved to this new node.


			




	465
	469
	
		
    ///If the second parameter \c connect is \c true (this is the default


			




	466
	470
	
		
    ///value), then a new arc from node \c n to the newly created node


			




	467
	471
	
		
    ///is also added.


			




	468
	472
	
		
    ///\return The newly created node.


			




	469
	473
	
		
    ///


			




	470
	
	
		
    ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing


			




	471
	
	
		
    ///arcs of node \c n are invalidated. Other iterators remain valid.


			




	
	474
	
		
    ///\note All iterators remain valid.


			




	472
	475
	
		
    ///


			




	473
	476
	
		
    ///\warning This functionality cannot be used together with the


			




	474
	477
	
		
    ///Snapshot feature.


			




	475
	478
	
		
    Node split(Node n, bool connect = true) {


			




	476
	479
	
		
      Node b = addNode();


			




	477
	
	
		
      for(OutArcIt e(*this,n);e!=INVALID;) {


			




	478
	
	
		
        OutArcIt f=e;


			




	479
	
	
		
        ++f;


			




	480
	
	
		
        changeSource(e,b);


			




	481
	
	
		
        e=f;


			




	
	480
	
		
      nodes[b.id].first_out=nodes[n.id].first_out;


			




	
	481
	
		
      nodes[n.id].first_out=-1;


			




	
	482
	
		
      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {


			




	
	483
	
		
        arcs[i].source=b.id;


			




	482
	484
	
		
      }


			




	483
	485
	
		
      if (connect) addArc(n,b);


			




	484
	486
	
		
      return b;


			




	485
	487
	
		
    }


			




	486
	488
	
		

			




	487
	489
	
		
    ///Split an arc.


			




        

    






    
    



    


    

     
    
0 comments (0 inline)