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 12 line context
... ... 
@@ -75,19 +75,25 @@
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(); }


			




	...
	...
	
		
@@ -168,21 +174,27 @@


			




	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


			




        

    






    
    



    


    

     
    
0 comments (0 inline)