1.1 --- a/lemon/euler.h Wed Apr 15 11:41:25 2009 +0200
1.2 +++ b/lemon/euler.h Wed Apr 15 11:47:19 2009 +0200
1.3 @@ -26,33 +26,31 @@
1.4
1.5 /// \ingroup graph_properties
1.6 /// \file
1.7 -/// \brief Euler tour
1.8 +/// \brief Euler tour iterators and a function for checking the \e Eulerian
1.9 +/// property.
1.10 ///
1.11 -///This file provides an Euler tour iterator and ways to check
1.12 -///if a digraph is euler.
1.13 -
1.14 +///This file provides Euler tour iterators and a function to check
1.15 +///if a (di)graph is \e Eulerian.
1.16
1.17 namespace lemon {
1.18
1.19 - ///Euler iterator for digraphs.
1.20 + ///Euler tour iterator for digraphs.
1.21
1.22 - /// \ingroup graph_properties
1.23 - ///This iterator converts to the \c Arc type of the digraph and using
1.24 - ///operator ++, it provides an Euler tour of a \e directed
1.25 - ///graph (if there exists).
1.26 + /// \ingroup graph_prop
1.27 + ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
1.28 + ///graph (if there exists) and it converts to the \c Arc type of the digraph.
1.29 ///
1.30 - ///For example
1.31 - ///if the given digraph is Euler (i.e it has only one nontrivial component
1.32 - ///and the in-degree is equal to the out-degree for all nodes),
1.33 - ///the following code will put the arcs of \c g
1.34 - ///to the vector \c et according to an
1.35 - ///Euler tour of \c g.
1.36 + ///For example, if the given digraph has an Euler tour (i.e it has only one
1.37 + ///non-trivial component and the in-degree is equal to the out-degree
1.38 + ///for all nodes), then the following code will put the arcs of \c g
1.39 + ///to the vector \c et according to an Euler tour of \c g.
1.40 ///\code
1.41 /// std::vector<ListDigraph::Arc> et;
1.42 - /// for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
1.43 + /// for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
1.44 /// et.push_back(e);
1.45 ///\endcode
1.46 - ///If \c g is not Euler then the resulted tour will not be full or closed.
1.47 + ///If \c g has no Euler tour, then the resulted walk will not be closed
1.48 + ///or not contain all arcs.
1.49 ///\sa EulerIt
1.50 template<typename GR>
1.51 class DiEulerIt
1.52 @@ -65,18 +63,19 @@
1.53 typedef typename GR::InArcIt InArcIt;
1.54
1.55 const GR &g;
1.56 - typename GR::template NodeMap<OutArcIt> nedge;
1.57 + typename GR::template NodeMap<OutArcIt> narc;
1.58 std::list<Arc> euler;
1.59
1.60 public:
1.61
1.62 ///Constructor
1.63
1.64 + ///Constructor.
1.65 ///\param gr A digraph.
1.66 - ///\param start The starting point of the tour. If it is not given
1.67 - /// the tour will start from the first node.
1.68 + ///\param start The starting point of the tour. If it is not given,
1.69 + ///the tour will start from the first node that has an outgoing arc.
1.70 DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
1.71 - : g(gr), nedge(g)
1.72 + : g(gr), narc(g)
1.73 {
1.74 if (start==INVALID) {
1.75 NodeIt n(g);
1.76 @@ -84,40 +83,45 @@
1.77 start=n;
1.78 }
1.79 if (start!=INVALID) {
1.80 - for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
1.81 - while (nedge[start]!=INVALID) {
1.82 - euler.push_back(nedge[start]);
1.83 - Node next=g.target(nedge[start]);
1.84 - ++nedge[start];
1.85 + for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
1.86 + while (narc[start]!=INVALID) {
1.87 + euler.push_back(narc[start]);
1.88 + Node next=g.target(narc[start]);
1.89 + ++narc[start];
1.90 start=next;
1.91 }
1.92 }
1.93 }
1.94
1.95 - ///Arc Conversion
1.96 + ///Arc conversion
1.97 operator Arc() { return euler.empty()?INVALID:euler.front(); }
1.98 + ///Compare with \c INVALID
1.99 bool operator==(Invalid) { return euler.empty(); }
1.100 + ///Compare with \c INVALID
1.101 bool operator!=(Invalid) { return !euler.empty(); }
1.102
1.103 ///Next arc of the tour
1.104 +
1.105 + ///Next arc of the tour
1.106 + ///
1.107 DiEulerIt &operator++() {
1.108 Node s=g.target(euler.front());
1.109 euler.pop_front();
1.110 - //This produces a warning.Strange.
1.111 - //std::list<Arc>::iterator next=euler.begin();
1.112 typename std::list<Arc>::iterator next=euler.begin();
1.113 - while(nedge[s]!=INVALID) {
1.114 - euler.insert(next,nedge[s]);
1.115 - Node n=g.target(nedge[s]);
1.116 - ++nedge[s];
1.117 + while(narc[s]!=INVALID) {
1.118 + euler.insert(next,narc[s]);
1.119 + Node n=g.target(narc[s]);
1.120 + ++narc[s];
1.121 s=n;
1.122 }
1.123 return *this;
1.124 }
1.125 ///Postfix incrementation
1.126
1.127 + /// Postfix incrementation.
1.128 + ///
1.129 ///\warning This incrementation
1.130 - ///returns an \c Arc, not an \ref DiEulerIt, as one may
1.131 + ///returns an \c Arc, not a \ref DiEulerIt, as one may
1.132 ///expect.
1.133 Arc operator++(int)
1.134 {
1.135 @@ -127,30 +131,28 @@
1.136 }
1.137 };
1.138
1.139 - ///Euler iterator for graphs.
1.140 + ///Euler tour iterator for graphs.
1.141
1.142 /// \ingroup graph_properties
1.143 - ///This iterator converts to the \c Arc (or \c Edge)
1.144 - ///type of the digraph and using
1.145 - ///operator ++, it provides an Euler tour of an undirected
1.146 - ///digraph (if there exists).
1.147 + ///This iterator provides an Euler tour (Eulerian circuit) of an
1.148 + ///\e undirected graph (if there exists) and it converts to the \c Arc
1.149 + ///and \c Edge types of the graph.
1.150 ///
1.151 - ///For example
1.152 - ///if the given digraph if Euler (i.e it has only one nontrivial component
1.153 - ///and the degree of each node is even),
1.154 + ///For example, if the given graph has an Euler tour (i.e it has only one
1.155 + ///non-trivial component and the degree of each node is even),
1.156 ///the following code will print the arc IDs according to an
1.157 ///Euler tour of \c g.
1.158 ///\code
1.159 - /// for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
1.160 + /// for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
1.161 /// std::cout << g.id(Edge(e)) << std::eol;
1.162 /// }
1.163 ///\endcode
1.164 - ///Although the iterator provides an Euler tour of an graph,
1.165 - ///it still returns Arcs in order to indicate the direction of the tour.
1.166 - ///(But Arc will convert to Edges, of course).
1.167 + ///Although this iterator is for undirected graphs, it still returns
1.168 + ///arcs in order to indicate the direction of the tour.
1.169 + ///(But arcs convert to edges, of course.)
1.170 ///
1.171 - ///If \c g is not Euler then the resulted tour will not be full or closed.
1.172 - ///\sa EulerIt
1.173 + ///If \c g has no Euler tour, then the resulted walk will not be closed
1.174 + ///or not contain all edges.
1.175 template<typename GR>
1.176 class EulerIt
1.177 {
1.178 @@ -163,7 +165,7 @@
1.179 typedef typename GR::InArcIt InArcIt;
1.180
1.181 const GR &g;
1.182 - typename GR::template NodeMap<OutArcIt> nedge;
1.183 + typename GR::template NodeMap<OutArcIt> narc;
1.184 typename GR::template EdgeMap<bool> visited;
1.185 std::list<Arc> euler;
1.186
1.187 @@ -171,11 +173,12 @@
1.188
1.189 ///Constructor
1.190
1.191 - ///\param gr An graph.
1.192 - ///\param start The starting point of the tour. If it is not given
1.193 - /// the tour will start from the first node.
1.194 + ///Constructor.
1.195 + ///\param gr A graph.
1.196 + ///\param start The starting point of the tour. If it is not given,
1.197 + ///the tour will start from the first node that has an incident edge.
1.198 EulerIt(const GR &gr, typename GR::Node start = INVALID)
1.199 - : g(gr), nedge(g), visited(g, false)
1.200 + : g(gr), narc(g), visited(g, false)
1.201 {
1.202 if (start==INVALID) {
1.203 NodeIt n(g);
1.204 @@ -183,41 +186,43 @@
1.205 start=n;
1.206 }
1.207 if (start!=INVALID) {
1.208 - for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
1.209 - while(nedge[start]!=INVALID) {
1.210 - euler.push_back(nedge[start]);
1.211 - visited[nedge[start]]=true;
1.212 - Node next=g.target(nedge[start]);
1.213 - ++nedge[start];
1.214 + for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
1.215 + while(narc[start]!=INVALID) {
1.216 + euler.push_back(narc[start]);
1.217 + visited[narc[start]]=true;
1.218 + Node next=g.target(narc[start]);
1.219 + ++narc[start];
1.220 start=next;
1.221 - while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
1.222 + while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
1.223 }
1.224 }
1.225 }
1.226
1.227 - ///Arc Conversion
1.228 + ///Arc conversion
1.229 operator Arc() const { return euler.empty()?INVALID:euler.front(); }
1.230 - ///Arc Conversion
1.231 + ///Edge conversion
1.232 operator Edge() const { return euler.empty()?INVALID:euler.front(); }
1.233 - ///\e
1.234 + ///Compare with \c INVALID
1.235 bool operator==(Invalid) const { return euler.empty(); }
1.236 - ///\e
1.237 + ///Compare with \c INVALID
1.238 bool operator!=(Invalid) const { return !euler.empty(); }
1.239
1.240 ///Next arc of the tour
1.241 +
1.242 + ///Next arc of the tour
1.243 + ///
1.244 EulerIt &operator++() {
1.245 Node s=g.target(euler.front());
1.246 euler.pop_front();
1.247 typename std::list<Arc>::iterator next=euler.begin();
1.248 -
1.249 - while(nedge[s]!=INVALID) {
1.250 - while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
1.251 - if(nedge[s]==INVALID) break;
1.252 + while(narc[s]!=INVALID) {
1.253 + while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
1.254 + if(narc[s]==INVALID) break;
1.255 else {
1.256 - euler.insert(next,nedge[s]);
1.257 - visited[nedge[s]]=true;
1.258 - Node n=g.target(nedge[s]);
1.259 - ++nedge[s];
1.260 + euler.insert(next,narc[s]);
1.261 + visited[narc[s]]=true;
1.262 + Node n=g.target(narc[s]);
1.263 + ++narc[s];
1.264 s=n;
1.265 }
1.266 }
1.267 @@ -226,9 +231,10 @@
1.268
1.269 ///Postfix incrementation
1.270
1.271 - ///\warning This incrementation
1.272 - ///returns an \c Arc, not an \ref EulerIt, as one may
1.273 - ///expect.
1.274 + /// Postfix incrementation.
1.275 + ///
1.276 + ///\warning This incrementation returns an \c Arc (which converts to
1.277 + ///an \c Edge), not an \ref EulerIt, as one may expect.
1.278 Arc operator++(int)
1.279 {
1.280 Arc e=*this;
1.281 @@ -238,18 +244,23 @@
1.282 };
1.283
1.284
1.285 - ///Checks if the graph is Eulerian
1.286 + ///Check if the given graph is \e Eulerian
1.287
1.288 /// \ingroup graph_properties
1.289 - ///Checks if the graph is Eulerian. It works for both directed and undirected
1.290 - ///graphs.
1.291 - ///\note By definition, a digraph is called \e Eulerian if
1.292 - ///and only if it is connected and the number of its incoming and outgoing
1.293 + ///This function checks if the given graph is \e Eulerian.
1.294 + ///It works for both directed and undirected graphs.
1.295 + ///
1.296 + ///By definition, a digraph is called \e Eulerian if
1.297 + ///and only if it is connected and the number of incoming and outgoing
1.298 ///arcs are the same for each node.
1.299 ///Similarly, an undirected graph is called \e Eulerian if
1.300 - ///and only if it is connected and the number of incident arcs is even
1.301 - ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
1.302 - ///but still have an Euler tour</em>.
1.303 + ///and only if it is connected and the number of incident edges is even
1.304 + ///for each node.
1.305 + ///
1.306 + ///\note There are (di)graphs that are not Eulerian, but still have an
1.307 + /// Euler tour, since they may contain isolated nodes.
1.308 + ///
1.309 + ///\sa DiEulerIt, EulerIt
1.310 template<typename GR>
1.311 #ifdef DOXYGEN
1.312 bool
1.313 @@ -268,7 +279,7 @@
1.314 {
1.315 for(typename GR::NodeIt n(g);n!=INVALID;++n)
1.316 if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
1.317 - return connected(Undirector<const GR>(g));
1.318 + return connected(undirector(g));
1.319 }
1.320
1.321 }