Changeset - r785:456fa5bc3256
« 784:9d6c3e
787: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
Ignore white space 6 line context
... ... 
@@ -32,6 +32,8 @@
32 32 

			




	33
	33
	
		
namespace lemon {


			




	34
	34
	
		

			




	
	35
	
		
  class ListDigraph;


			




	
	36
	
		

			




	35
	37
	
		
  class ListDigraphBase {


			




	36
	38
	
		

			




	37
	39
	
		
  protected:


			




	...
	...
	
		
@@ -62,6 +64,7 @@


			




	62
	64
	
		

			




	63
	65
	
		
    class Node {


			




	64
	66
	
		
      friend class ListDigraphBase;


			




	
	67
	
		
      friend class ListDigraph;


			




	65
	68
	
		
    protected:


			




	66
	69
	
		

			




	67
	70
	
		
      int id;


			




	...
	...
	
		
@@ -77,6 +80,7 @@


			




	77
	80
	
		

			




	78
	81
	
		
    class Arc {


			




	79
	82
	
		
      friend class ListDigraphBase;


			




	
	83
	
		
      friend class ListDigraph;


			




	80
	84
	
		
    protected:


			




	81
	85
	
		

			




	82
	86
	
		
      int id;


			




	...
	...
	
		
@@ -467,18 +471,16 @@


			




	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;


			




        

    






    
    



    


    

     
    
0 comments (0 inline)