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