122 ///if the given graph if Euler (i.e it has only one nontrivial component |
122 ///if the given graph if Euler (i.e it has only one nontrivial component |
123 ///and the degree of each node is even), |
123 ///and the degree of each node is even), |
124 ///the following code will print the edge IDs according to an |
124 ///the following code will print the edge IDs according to an |
125 ///Euler tour of \c g. |
125 ///Euler tour of \c g. |
126 ///\code |
126 ///\code |
127 /// for(UndirEulerIt<UndirListGraph> e(g),e!=INVALID;++e) { |
127 /// for(UEulerIt<ListUGraph> e(g),e!=INVALID;++e) { |
128 /// std::cout << g.id(UndirEdge(e)) << std::eol; |
128 /// std::cout << g.id(UEdge(e)) << std::eol; |
129 /// } |
129 /// } |
130 ///\endcode |
130 ///\endcode |
131 ///Although the iterator provides an Euler tour of an undirected graph, |
131 ///Although the iterator provides an Euler tour of an undirected graph, |
132 ///in order to indicate the direction of the tour, UndirEulerIt |
132 ///in order to indicate the direction of the tour, UEulerIt |
133 ///returns directed edges (that convert to the undirected ones, of course). |
133 ///returns directed edges (that convert to the undirected ones, of course). |
134 /// |
134 /// |
135 ///If \c g is not Euler then the resulted tour will not be full or closed. |
135 ///If \c g is not Euler then the resulted tour will not be full or closed. |
136 ///\todo Test required |
136 ///\todo Test required |
137 template<class Graph> |
137 template<class Graph> |
138 class UndirEulerIt |
138 class UEulerIt |
139 { |
139 { |
140 typedef typename Graph::Node Node; |
140 typedef typename Graph::Node Node; |
141 typedef typename Graph::NodeIt NodeIt; |
141 typedef typename Graph::NodeIt NodeIt; |
142 typedef typename Graph::Edge Edge; |
142 typedef typename Graph::Edge Edge; |
143 typedef typename Graph::EdgeIt EdgeIt; |
143 typedef typename Graph::EdgeIt EdgeIt; |
144 typedef typename Graph::OutEdgeIt OutEdgeIt; |
144 typedef typename Graph::OutEdgeIt OutEdgeIt; |
145 typedef typename Graph::InEdgeIt InEdgeIt; |
145 typedef typename Graph::InEdgeIt InEdgeIt; |
146 |
146 |
147 const Graph &g; |
147 const Graph &g; |
148 typename Graph::NodeMap<OutEdgeIt> nedge; |
148 typename Graph::NodeMap<OutEdgeIt> nedge; |
149 typename Graph::UndirEdgeMap<bool> visited; |
149 typename Graph::UEdgeMap<bool> visited; |
150 std::list<Edge> euler; |
150 std::list<Edge> euler; |
151 |
151 |
152 public: |
152 public: |
153 |
153 |
154 ///Constructor |
154 ///Constructor |
155 |
155 |
156 ///\param _g An undirected graph. |
156 ///\param _g An undirected graph. |
157 ///\param start The starting point of the tour. If it is not given |
157 ///\param start The starting point of the tour. If it is not given |
158 /// the tour will start from the first node. |
158 /// the tour will start from the first node. |
159 UndirEulerIt(const Graph &_g,typename Graph::Node start=INVALID) |
159 UEulerIt(const Graph &_g,typename Graph::Node start=INVALID) |
160 : g(_g), nedge(g), visited(g,false) |
160 : g(_g), nedge(g), visited(g,false) |
161 { |
161 { |
162 if(start==INVALID) start=NodeIt(g); |
162 if(start==INVALID) start=NodeIt(g); |
163 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n); |
163 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n); |
164 while(nedge[start]!=INVALID) { |
164 while(nedge[start]!=INVALID) { |
173 operator Edge() { return euler.empty()?INVALID:euler.front(); } |
173 operator Edge() { return euler.empty()?INVALID:euler.front(); } |
174 bool operator==(Invalid) { return euler.empty(); } |
174 bool operator==(Invalid) { return euler.empty(); } |
175 bool operator!=(Invalid) { return !euler.empty(); } |
175 bool operator!=(Invalid) { return !euler.empty(); } |
176 |
176 |
177 ///Next edge of the tour |
177 ///Next edge of the tour |
178 UndirEulerIt &operator++() { |
178 UEulerIt &operator++() { |
179 Node s=g.target(euler.front()); |
179 Node s=g.target(euler.front()); |
180 euler.pop_front(); |
180 euler.pop_front(); |
181 typename std::list<Edge>::iterator next=euler.begin(); |
181 typename std::list<Edge>::iterator next=euler.begin(); |
182 |
182 |
183 while(nedge[s]!=INVALID) { |
183 while(nedge[s]!=INVALID) { |
222 ///\todo Test required |
222 ///\todo Test required |
223 template<class Graph> |
223 template<class Graph> |
224 #ifdef DOXYGEN |
224 #ifdef DOXYGEN |
225 bool |
225 bool |
226 #else |
226 #else |
227 typename enable_if<typename Graph::UndirTag,bool>::type |
227 typename enable_if<typename Graph::UTag,bool>::type |
228 euler(const Graph &g) |
228 euler(const Graph &g) |
229 { |
229 { |
230 for(typename Graph::NodeIt n(g);n!=INVALID;++n) |
230 for(typename Graph::NodeIt n(g);n!=INVALID;++n) |
231 if(countIncEdges(g,n)%2) return false; |
231 if(countIncEdges(g,n)%2) return false; |
232 return connected(g); |
232 return connected(g); |
233 } |
233 } |
234 template<class Graph> |
234 template<class Graph> |
235 typename disable_if<typename Graph::UndirTag,bool>::type |
235 typename disable_if<typename Graph::UTag,bool>::type |
236 #endif |
236 #endif |
237 euler(const Graph &g) |
237 euler(const Graph &g) |
238 { |
238 { |
239 for(typename Graph::NodeIt n(g);n!=INVALID;++n) |
239 for(typename Graph::NodeIt n(g);n!=INVALID;++n) |
240 if(countInEdges(g,n)!=countOutEdges(g,n)) return false; |
240 if(countInEdges(g,n)!=countOutEdges(g,n)) return false; |