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
Ignore white space 24 line context
... ... 
@@ -23,24 +23,26 @@
23 23 
///\file
24 24 
///\brief ListDigraph and ListGraph classes.
25 25 

			




	26
	26
	
		
#include <lemon/core.h>


			




	27
	27
	
		
#include <lemon/error.h>


			




	28
	28
	
		
#include <lemon/bits/graph_extender.h>


			




	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;


			




	41
	43
	
		
    };


			




	42
	44
	
		

			




	43
	45
	
		
    struct ArcT {


			




	44
	46
	
		
      int target, source;


			




	45
	47
	
		
      int prev_in, prev_out;


			




	46
	48
	
		
      int next_in, next_out;


			




	...
	...
	
		
@@ -53,39 +55,41 @@


			




	53
	55
	
		
    int first_free_node;


			




	54
	56
	
		

			




	55
	57
	
		
    std::vector<ArcT> arcs;


			




	56
	58
	
		

			




	57
	59
	
		
    int first_free_arc;


			




	58
	60
	
		

			




	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:


			




	71
	74
	
		
      Node() {}


			




	72
	75
	
		
      Node (Invalid) { id = -1; }


			




	73
	76
	
		
      bool operator==(const Node& node) const {return id == node.id;}


			




	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:


			




	86
	90
	
		
      Arc() {}


			




	87
	91
	
		
      Arc (Invalid) { id = -1; }


			




	88
	92
	
		
      bool operator==(const Arc& arc) const {return id == arc.id;}


			




	89
	93
	
		
      bool operator!=(const Arc& arc) const {return id != arc.id;}


			




	90
	94
	
		
      bool operator<(const Arc& arc) const {return id < arc.id;}


			




	91
	95
	
		
    };


			




	...
	...
	
		
@@ -458,36 +462,34 @@


			




	458
	462
	
		
    }


			




	459
	463
	
		

			




	460
	464
	
		
    ///Split a node.


			




	461
	465
	
		

			




	462
	466
	
		
    ///This function splits the given node. First, a new node is added


			




	463
	467
	
		
    ///to the digraph, then the source of each outgoing arc of node \c n


			




	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.


			




	488
	490
	
		

			




	489
	491
	
		
    ///This function splits the given arc. First, a new node \c v is


			




	490
	492
	
		
    ///added to the digraph, then the target node of the original arc


			




	491
	493
	
		
    ///is set to \c v. Finally, an arc from \c v to the original target


			




	492
	494
	
		
    ///is added.


			




	493
	495
	
		
    ///\return The newly created node.


			




        

    






    
    



    


    

     
    
0 comments (0 inline)