76 ///\param start The starting point of the tour. If it is not given |
76 ///\param start The starting point of the tour. If it is not given |
77 /// the tour will start from the first node. |
77 /// the tour will start from the first node. |
78 DiEulerIt(const GR &gr, typename GR::Node start = INVALID) |
78 DiEulerIt(const GR &gr, typename GR::Node start = INVALID) |
79 : g(gr), nedge(g) |
79 : g(gr), nedge(g) |
80 { |
80 { |
81 if(start==INVALID) start=NodeIt(g); |
81 if (start==INVALID) { |
82 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); |
82 NodeIt n(g); |
83 while(nedge[start]!=INVALID) { |
83 while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; |
84 euler.push_back(nedge[start]); |
84 start=n; |
85 Node next=g.target(nedge[start]); |
85 } |
86 ++nedge[start]; |
86 if (start!=INVALID) { |
87 start=next; |
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 ///Arc Conversion |
97 ///Arc Conversion |
92 operator Arc() { return euler.empty()?INVALID:euler.front(); } |
98 operator Arc() { return euler.empty()?INVALID:euler.front(); } |
169 ///\param start The starting point of the tour. If it is not given |
175 ///\param start The starting point of the tour. If it is not given |
170 /// the tour will start from the first node. |
176 /// the tour will start from the first node. |
171 EulerIt(const GR &gr, typename GR::Node start = INVALID) |
177 EulerIt(const GR &gr, typename GR::Node start = INVALID) |
172 : g(gr), nedge(g), visited(g, false) |
178 : g(gr), nedge(g), visited(g, false) |
173 { |
179 { |
174 if(start==INVALID) start=NodeIt(g); |
180 if (start==INVALID) { |
175 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); |
181 NodeIt n(g); |
176 while(nedge[start]!=INVALID) { |
182 while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; |
177 euler.push_back(nedge[start]); |
183 start=n; |
178 visited[nedge[start]]=true; |
184 } |
179 Node next=g.target(nedge[start]); |
185 if (start!=INVALID) { |
180 ++nedge[start]; |
186 for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n); |
181 start=next; |
187 while(nedge[start]!=INVALID) { |
182 while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; |
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 ///Arc Conversion |
198 ///Arc Conversion |
187 operator Arc() const { return euler.empty()?INVALID:euler.front(); } |
199 operator Arc() const { return euler.empty()?INVALID:euler.front(); } |