147 class UEulerIt |
147 class UEulerIt |
148 { |
148 { |
149 typedef typename Graph::Node Node; |
149 typedef typename Graph::Node Node; |
150 typedef typename Graph::NodeIt NodeIt; |
150 typedef typename Graph::NodeIt NodeIt; |
151 typedef typename Graph::Edge Edge; |
151 typedef typename Graph::Edge Edge; |
|
152 typedef typename Graph::UEdge UEdge; |
152 typedef typename Graph::EdgeIt EdgeIt; |
153 typedef typename Graph::EdgeIt EdgeIt; |
153 typedef typename Graph::OutEdgeIt OutEdgeIt; |
154 typedef typename Graph::OutEdgeIt OutEdgeIt; |
154 typedef typename Graph::InEdgeIt InEdgeIt; |
155 typedef typename Graph::InEdgeIt InEdgeIt; |
155 |
156 |
156 const Graph &g; |
157 const Graph &g; |
170 { |
171 { |
171 if(start==INVALID) start=NodeIt(g); |
172 if(start==INVALID) start=NodeIt(g); |
172 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n); |
173 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n); |
173 while(nedge[start]!=INVALID) { |
174 while(nedge[start]!=INVALID) { |
174 euler.push_back(nedge[start]); |
175 euler.push_back(nedge[start]); |
|
176 visited[nedge[start]]=true; |
175 Node next=g.target(nedge[start]); |
177 Node next=g.target(nedge[start]); |
176 ++nedge[start]; |
178 ++nedge[start]; |
177 start=next; while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; |
179 start=next; |
|
180 while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; |
178 } |
181 } |
179 } |
182 } |
180 |
183 |
181 ///Edge Conversion |
184 ///Edge Conversion |
182 operator Edge() { return euler.empty()?INVALID:euler.front(); } |
185 operator Edge() const { return euler.empty()?INVALID:euler.front(); } |
183 bool operator==(Invalid) { return euler.empty(); } |
186 ///Edge Conversion |
184 bool operator!=(Invalid) { return !euler.empty(); } |
187 operator UEdge() const { return euler.empty()?INVALID:euler.front(); } |
|
188 ///\e |
|
189 bool operator==(Invalid) const { return euler.empty(); } |
|
190 ///\e |
|
191 bool operator!=(Invalid) const { return !euler.empty(); } |
185 |
192 |
186 ///Next edge of the tour |
193 ///Next edge of the tour |
187 UEulerIt &operator++() { |
194 UEulerIt &operator++() { |
188 Node s=g.target(euler.front()); |
195 Node s=g.target(euler.front()); |
189 euler.pop_front(); |
196 euler.pop_front(); |
192 while(nedge[s]!=INVALID) { |
199 while(nedge[s]!=INVALID) { |
193 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; |
200 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; |
194 if(nedge[s]==INVALID) break; |
201 if(nedge[s]==INVALID) break; |
195 else { |
202 else { |
196 euler.insert(next,nedge[s]); |
203 euler.insert(next,nedge[s]); |
|
204 visited[nedge[s]]=true; |
197 Node n=g.target(nedge[s]); |
205 Node n=g.target(nedge[s]); |
198 ++nedge[s]; |
206 ++nedge[s]; |
199 s=n; |
207 s=n; |
200 } |
208 } |
201 } |
209 } |