r521:3af83b6be1df
Mon, 23 Feb 2009 12:30:15
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -207,61 +207,61 @@ |
| 207 | 207 |
euler.insert(next,nedge[s]); |
| 208 | 208 |
visited[nedge[s]]=true; |
| 209 | 209 |
Node n=g.target(nedge[s]); |
| 210 | 210 |
++nedge[s]; |
| 211 | 211 |
s=n; |
| 212 | 212 |
} |
| 213 | 213 |
} |
| 214 | 214 |
return *this; |
| 215 | 215 |
} |
| 216 | 216 |
|
| 217 | 217 |
///Postfix incrementation |
| 218 | 218 |
|
| 219 | 219 |
///\warning This incrementation |
| 220 | 220 |
///returns an \c Arc, not an \ref EulerIt, as one may |
| 221 | 221 |
///expect. |
| 222 | 222 |
Arc operator++(int) |
| 223 | 223 |
{
|
| 224 | 224 |
Arc e=*this; |
| 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 |
|
| 265 | 265 |
} |
| 266 | 266 |
|
| 267 | 267 |
#endif |
0 comments (0 inline)