Changeset - r638:493533ead9df
« 636:630c48
639:2ebfdb »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Bug fix in the Euler iterators (#264) Handle the case when the first node is isolated.
0 1 0
default
1 file changed with 28 insertions and 16 deletions:
lemon/euler.h
28
16
↑ Collapse diff ↑
lemon/euler.h
Ignore white space 24 line context
... ... 
@@ -69,31 +69,37 @@
69 69 
    std::list<Arc> euler;
70 70 

			




	71
	71
	
		
  public:


			




	72
	72
	
		

			




	73
	73
	
		
    ///Constructor


			




	74
	74
	
		

			




	75
	75
	
		
    ///\param gr A digraph.


			




	76
	76
	
		
    ///\param start The starting point of the tour. If it is not given


			




	77
	77
	
		
    ///       the tour will start from the first node.


			




	78
	78
	
		
    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)


			




	79
	79
	
		
      : g(gr), nedge(g)


			




	80
	80
	
		
    {


			




	81
	
	
		
      if(start==INVALID) start=NodeIt(g);


			




	82
	
	
		
      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);


			




	83
	
	
		
      while(nedge[start]!=INVALID) {


			




	84
	
	
		
        euler.push_back(nedge[start]);


			




	85
	
	
		
        Node next=g.target(nedge[start]);


			




	86
	
	
		
        ++nedge[start];


			




	87
	
	
		
        start=next;


			




	
	81
	
		
      if (start==INVALID) {


			




	
	82
	
		
        NodeIt n(g);


			




	
	83
	
		
        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;


			




	
	84
	
		
        start=n;


			




	
	85
	
		
      }


			




	
	86
	
		
      if (start!=INVALID) {


			




	
	87
	
		
        for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);


			




	
	88
	
		
        while (nedge[start]!=INVALID) {


			




	
	89
	
		
          euler.push_back(nedge[start]);


			




	
	90
	
		
          Node next=g.target(nedge[start]);


			




	
	91
	
		
          ++nedge[start];


			




	
	92
	
		
          start=next;


			




	
	93
	
		
        }


			




	88
	94
	
		
      }


			




	89
	95
	
		
    }


			




	90
	96
	
		

			




	91
	97
	
		
    ///Arc Conversion


			




	92
	98
	
		
    operator Arc() { return euler.empty()?INVALID:euler.front(); }


			




	93
	99
	
		
    bool operator==(Invalid) { return euler.empty(); }


			




	94
	100
	
		
    bool operator!=(Invalid) { return !euler.empty(); }


			




	95
	101
	
		

			




	96
	102
	
		
    ///Next arc of the tour


			




	97
	103
	
		
    DiEulerIt &operator++() {


			




	98
	104
	
		
      Node s=g.target(euler.front());


			




	99
	105
	
		
      euler.pop_front();


			




	...
	...
	
		
@@ -162,33 +168,39 @@


			




	162
	168
	
		
    std::list<Arc> euler;


			




	163
	169
	
		

			




	164
	170
	
		
  public:


			




	165
	171
	
		

			




	166
	172
	
		
    ///Constructor


			




	167
	173
	
		

			




	168
	174
	
		
    ///\param gr An graph.


			




	169
	175
	
		
    ///\param start The starting point of the tour. If it is not given


			




	170
	176
	
		
    ///       the tour will start from the first node.


			




	171
	177
	
		
    EulerIt(const GR &gr, typename GR::Node start = INVALID)


			




	172
	178
	
		
      : g(gr), nedge(g), visited(g, false)


			




	173
	179
	
		
    {


			




	174
	
	
		
      if(start==INVALID) start=NodeIt(g);


			




	175
	
	
		
      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);


			




	176
	
	
		
      while(nedge[start]!=INVALID) {


			




	177
	
	
		
        euler.push_back(nedge[start]);


			




	178
	
	
		
        visited[nedge[start]]=true;


			




	179
	
	
		
        Node next=g.target(nedge[start]);


			




	180
	
	
		
        ++nedge[start];


			




	181
	
	
		
        start=next;


			




	182
	
	
		
        while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];


			




	
	180
	
		
      if (start==INVALID) {


			




	
	181
	
		
        NodeIt n(g);


			




	
	182
	
		
        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;


			




	
	183
	
		
        start=n;


			




	
	184
	
		
      }


			




	
	185
	
		
      if (start!=INVALID) {


			




	
	186
	
		
        for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);


			




	
	187
	
		
        while(nedge[start]!=INVALID) {


			




	
	188
	
		
          euler.push_back(nedge[start]);


			




	
	189
	
		
          visited[nedge[start]]=true;


			




	
	190
	
		
          Node next=g.target(nedge[start]);


			




	
	191
	
		
          ++nedge[start];


			




	
	192
	
		
          start=next;


			




	
	193
	
		
          while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];


			




	
	194
	
		
        }


			




	183
	195
	
		
      }


			




	184
	196
	
		
    }


			




	185
	197
	
		

			




	186
	198
	
		
    ///Arc Conversion


			




	187
	199
	
		
    operator Arc() const { return euler.empty()?INVALID:euler.front(); }


			




	188
	200
	
		
    ///Arc Conversion


			




	189
	201
	
		
    operator Edge() const { return euler.empty()?INVALID:euler.front(); }


			




	190
	202
	
		
    ///\e


			




	191
	203
	
		
    bool operator==(Invalid) const { return euler.empty(); }


			




	192
	204
	
		
    ///\e


			




	193
	205
	
		
    bool operator!=(Invalid) const { return !euler.empty(); }


			




	194
	206
	
		

			




        

    






    
    



    


    

     
    
0 comments (0 inline)