Bug fix in the Euler iterators (#264)
authorPeter Kovacs <kpeter@inf.elte.hu>
Wed, 15 Apr 2009 11:41:25 +0200
changeset 638493533ead9df
parent 636 630c4898c548
child 639 2ebfdb89ec66
Bug fix in the Euler iterators (#264)
Handle the case when the first node is isolated.
lemon/euler.h
     1.1 --- a/lemon/euler.h	Wed Apr 15 07:13:30 2009 +0100
     1.2 +++ b/lemon/euler.h	Wed Apr 15 11:41:25 2009 +0200
     1.3 @@ -78,13 +78,19 @@
     1.4      DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
     1.5        : g(gr), nedge(g)
     1.6      {
     1.7 -      if(start==INVALID) start=NodeIt(g);
     1.8 -      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
     1.9 -      while(nedge[start]!=INVALID) {
    1.10 -        euler.push_back(nedge[start]);
    1.11 -        Node next=g.target(nedge[start]);
    1.12 -        ++nedge[start];
    1.13 -        start=next;
    1.14 +      if (start==INVALID) {
    1.15 +        NodeIt n(g);
    1.16 +        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
    1.17 +        start=n;
    1.18 +      }
    1.19 +      if (start!=INVALID) {
    1.20 +        for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
    1.21 +        while (nedge[start]!=INVALID) {
    1.22 +          euler.push_back(nedge[start]);
    1.23 +          Node next=g.target(nedge[start]);
    1.24 +          ++nedge[start];
    1.25 +          start=next;
    1.26 +        }
    1.27        }
    1.28      }
    1.29  
    1.30 @@ -171,15 +177,21 @@
    1.31      EulerIt(const GR &gr, typename GR::Node start = INVALID)
    1.32        : g(gr), nedge(g), visited(g, false)
    1.33      {
    1.34 -      if(start==INVALID) start=NodeIt(g);
    1.35 -      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
    1.36 -      while(nedge[start]!=INVALID) {
    1.37 -        euler.push_back(nedge[start]);
    1.38 -        visited[nedge[start]]=true;
    1.39 -        Node next=g.target(nedge[start]);
    1.40 -        ++nedge[start];
    1.41 -        start=next;
    1.42 -        while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
    1.43 +      if (start==INVALID) {
    1.44 +        NodeIt n(g);
    1.45 +        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
    1.46 +        start=n;
    1.47 +      }
    1.48 +      if (start!=INVALID) {
    1.49 +        for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
    1.50 +        while(nedge[start]!=INVALID) {
    1.51 +          euler.push_back(nedge[start]);
    1.52 +          visited[nedge[start]]=true;
    1.53 +          Node next=g.target(nedge[start]);
    1.54 +          ++nedge[start];
    1.55 +          start=next;
    1.56 +          while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
    1.57 +        }
    1.58        }
    1.59      }
    1.60