226 return e; |
226 return e; |
227 } |
227 } |
228 }; |
228 }; |
229 |
229 |
230 |
230 |
231 ///Checks if the graph is Euler |
231 ///Checks if the graph is Eulerian |
232 |
232 |
233 /// \ingroup graph_prop |
233 /// \ingroup graph_prop |
234 ///Checks if the graph is Euler. It works for both directed and undirected |
234 ///Checks if the graph is Eulerian. It works for both directed and undirected |
235 ///graphs. |
235 ///graphs. |
236 ///\note By definition, a digraph is called \e Euler if |
236 ///\note By definition, a digraph is called \e Eulerian if |
237 ///and only if it is connected and the number of its incoming and outgoing |
237 ///and only if it is connected and the number of its incoming and outgoing |
238 ///arcs are the same for each node. |
238 ///arcs are the same for each node. |
239 ///Similarly, an undirected graph is called \e Euler if |
239 ///Similarly, an undirected graph is called \e Eulerian if |
240 ///and only if it is connected and the number of incident arcs is even |
240 ///and only if it is connected and the number of incident arcs is even |
241 ///for each node. <em>Therefore, there are digraphs which are not Euler, but |
241 ///for each node. <em>Therefore, there are digraphs which are not Eulerian, |
242 ///still have an Euler tour</em>. |
242 ///but still have an Euler tour</em>. |
243 ///\todo Test required |
243 ///\todo Test required |
244 template<class Digraph> |
244 template<class Digraph> |
245 #ifdef DOXYGEN |
245 #ifdef DOXYGEN |
246 bool |
246 bool |
247 #else |
247 #else |
248 typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type |
248 typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type |
249 euler(const Digraph &g) |
249 eulerian(const Digraph &g) |
250 { |
250 { |
251 for(typename Digraph::NodeIt n(g);n!=INVALID;++n) |
251 for(typename Digraph::NodeIt n(g);n!=INVALID;++n) |
252 if(countIncEdges(g,n)%2) return false; |
252 if(countIncEdges(g,n)%2) return false; |
253 return connected(g); |
253 return connected(g); |
254 } |
254 } |
255 template<class Digraph> |
255 template<class Digraph> |
256 typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type |
256 typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type |
257 #endif |
257 #endif |
258 euler(const Digraph &g) |
258 eulerian(const Digraph &g) |
259 { |
259 { |
260 for(typename Digraph::NodeIt n(g);n!=INVALID;++n) |
260 for(typename Digraph::NodeIt n(g);n!=INVALID;++n) |
261 if(countInArcs(g,n)!=countOutArcs(g,n)) return false; |
261 if(countInArcs(g,n)!=countOutArcs(g,n)) return false; |
262 return connected(Undirector<const Digraph>(g)); |
262 return connected(Undirector<const Digraph>(g)); |
263 } |
263 } |