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:
↑ Collapse diff ↑
Ignore white space 32 line context
... ...
@@ -65,39 +65,45 @@
65 65
    typedef typename GR::InArcIt InArcIt;
66 66

	
67 67
    const GR &g;
68 68
    typename GR::template NodeMap<OutArcIt> nedge;
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();
100 106
      //This produces a warning.Strange.
101 107
      //std::list<Arc>::iterator next=euler.begin();
102 108
      typename std::list<Arc>::iterator next=euler.begin();
103 109
      while(nedge[s]!=INVALID) {
... ...
@@ -158,41 +164,47 @@
158 164

	
159 165
    const GR &g;
160 166
    typename GR::template NodeMap<OutArcIt> nedge;
161 167
    typename GR::template EdgeMap<bool> visited;
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

	
195 207
    ///Next arc of the tour
196 208
    EulerIt &operator++() {
197 209
      Node s=g.target(euler.front());
198 210
      euler.pop_front();
0 comments (0 inline)