24 #include<lemon/connectivity.h> |
24 #include<lemon/connectivity.h> |
25 #include <list> |
25 #include <list> |
26 |
26 |
27 /// \ingroup graph_properties |
27 /// \ingroup graph_properties |
28 /// \file |
28 /// \file |
29 /// \brief Euler tour |
29 /// \brief Euler tour iterators and a function for checking the \e Eulerian |
|
30 /// property. |
30 /// |
31 /// |
31 ///This file provides an Euler tour iterator and ways to check |
32 ///This file provides Euler tour iterators and a function to check |
32 ///if a digraph is euler. |
33 ///if a (di)graph is \e Eulerian. |
33 |
|
34 |
34 |
35 namespace lemon { |
35 namespace lemon { |
36 |
36 |
37 ///Euler iterator for digraphs. |
37 ///Euler tour iterator for digraphs. |
38 |
38 |
39 /// \ingroup graph_properties |
39 /// \ingroup graph_prop |
40 ///This iterator converts to the \c Arc type of the digraph and using |
40 ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed |
41 ///operator ++, it provides an Euler tour of a \e directed |
41 ///graph (if there exists) and it converts to the \c Arc type of the digraph. |
42 ///graph (if there exists). |
42 /// |
43 /// |
43 ///For example, if the given digraph has an Euler tour (i.e it has only one |
44 ///For example |
44 ///non-trivial component and the in-degree is equal to the out-degree |
45 ///if the given digraph is Euler (i.e it has only one nontrivial component |
45 ///for all nodes), then the following code will put the arcs of \c g |
46 ///and the in-degree is equal to the out-degree for all nodes), |
46 ///to the vector \c et according to an Euler tour of \c g. |
47 ///the following code will put the arcs of \c g |
|
48 ///to the vector \c et according to an |
|
49 ///Euler tour of \c g. |
|
50 ///\code |
47 ///\code |
51 /// std::vector<ListDigraph::Arc> et; |
48 /// std::vector<ListDigraph::Arc> et; |
52 /// for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e) |
49 /// for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e) |
53 /// et.push_back(e); |
50 /// et.push_back(e); |
54 ///\endcode |
51 ///\endcode |
55 ///If \c g is not Euler then the resulted tour will not be full or closed. |
52 ///If \c g has no Euler tour, then the resulted walk will not be closed |
|
53 ///or not contain all arcs. |
56 ///\sa EulerIt |
54 ///\sa EulerIt |
57 template<typename GR> |
55 template<typename GR> |
58 class DiEulerIt |
56 class DiEulerIt |
59 { |
57 { |
60 typedef typename GR::Node Node; |
58 typedef typename GR::Node Node; |
63 typedef typename GR::ArcIt ArcIt; |
61 typedef typename GR::ArcIt ArcIt; |
64 typedef typename GR::OutArcIt OutArcIt; |
62 typedef typename GR::OutArcIt OutArcIt; |
65 typedef typename GR::InArcIt InArcIt; |
63 typedef typename GR::InArcIt InArcIt; |
66 |
64 |
67 const GR &g; |
65 const GR &g; |
68 typename GR::template NodeMap<OutArcIt> nedge; |
66 typename GR::template NodeMap<OutArcIt> narc; |
69 std::list<Arc> euler; |
67 std::list<Arc> euler; |
70 |
68 |
71 public: |
69 public: |
72 |
70 |
73 ///Constructor |
71 ///Constructor |
74 |
72 |
|
73 ///Constructor. |
75 ///\param gr A digraph. |
74 ///\param gr A digraph. |
76 ///\param start The starting point of the tour. If it is not given |
75 ///\param start The starting point of the tour. If it is not given, |
77 /// the tour will start from the first node. |
76 ///the tour will start from the first node that has an outgoing arc. |
78 DiEulerIt(const GR &gr, typename GR::Node start = INVALID) |
77 DiEulerIt(const GR &gr, typename GR::Node start = INVALID) |
79 : g(gr), nedge(g) |
78 : g(gr), narc(g) |
80 { |
79 { |
81 if (start==INVALID) { |
80 if (start==INVALID) { |
82 NodeIt n(g); |
81 NodeIt n(g); |
83 while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; |
82 while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; |
84 start=n; |
83 start=n; |
85 } |
84 } |
86 if (start!=INVALID) { |
85 if (start!=INVALID) { |
87 for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n); |
86 for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n); |
88 while (nedge[start]!=INVALID) { |
87 while (narc[start]!=INVALID) { |
89 euler.push_back(nedge[start]); |
88 euler.push_back(narc[start]); |
90 Node next=g.target(nedge[start]); |
89 Node next=g.target(narc[start]); |
91 ++nedge[start]; |
90 ++narc[start]; |
92 start=next; |
91 start=next; |
93 } |
92 } |
94 } |
93 } |
95 } |
94 } |
96 |
95 |
97 ///Arc Conversion |
96 ///Arc conversion |
98 operator Arc() { return euler.empty()?INVALID:euler.front(); } |
97 operator Arc() { return euler.empty()?INVALID:euler.front(); } |
|
98 ///Compare with \c INVALID |
99 bool operator==(Invalid) { return euler.empty(); } |
99 bool operator==(Invalid) { return euler.empty(); } |
|
100 ///Compare with \c INVALID |
100 bool operator!=(Invalid) { return !euler.empty(); } |
101 bool operator!=(Invalid) { return !euler.empty(); } |
101 |
102 |
102 ///Next arc of the tour |
103 ///Next arc of the tour |
|
104 |
|
105 ///Next arc of the tour |
|
106 /// |
103 DiEulerIt &operator++() { |
107 DiEulerIt &operator++() { |
104 Node s=g.target(euler.front()); |
108 Node s=g.target(euler.front()); |
105 euler.pop_front(); |
109 euler.pop_front(); |
106 //This produces a warning.Strange. |
|
107 //std::list<Arc>::iterator next=euler.begin(); |
|
108 typename std::list<Arc>::iterator next=euler.begin(); |
110 typename std::list<Arc>::iterator next=euler.begin(); |
109 while(nedge[s]!=INVALID) { |
111 while(narc[s]!=INVALID) { |
110 euler.insert(next,nedge[s]); |
112 euler.insert(next,narc[s]); |
111 Node n=g.target(nedge[s]); |
113 Node n=g.target(narc[s]); |
112 ++nedge[s]; |
114 ++narc[s]; |
113 s=n; |
115 s=n; |
114 } |
116 } |
115 return *this; |
117 return *this; |
116 } |
118 } |
117 ///Postfix incrementation |
119 ///Postfix incrementation |
118 |
120 |
|
121 /// Postfix incrementation. |
|
122 /// |
119 ///\warning This incrementation |
123 ///\warning This incrementation |
120 ///returns an \c Arc, not an \ref DiEulerIt, as one may |
124 ///returns an \c Arc, not a \ref DiEulerIt, as one may |
121 ///expect. |
125 ///expect. |
122 Arc operator++(int) |
126 Arc operator++(int) |
123 { |
127 { |
124 Arc e=*this; |
128 Arc e=*this; |
125 ++(*this); |
129 ++(*this); |
126 return e; |
130 return e; |
127 } |
131 } |
128 }; |
132 }; |
129 |
133 |
130 ///Euler iterator for graphs. |
134 ///Euler tour iterator for graphs. |
131 |
135 |
132 /// \ingroup graph_properties |
136 /// \ingroup graph_properties |
133 ///This iterator converts to the \c Arc (or \c Edge) |
137 ///This iterator provides an Euler tour (Eulerian circuit) of an |
134 ///type of the digraph and using |
138 ///\e undirected graph (if there exists) and it converts to the \c Arc |
135 ///operator ++, it provides an Euler tour of an undirected |
139 ///and \c Edge types of the graph. |
136 ///digraph (if there exists). |
140 /// |
137 /// |
141 ///For example, if the given graph has an Euler tour (i.e it has only one |
138 ///For example |
142 ///non-trivial component and the degree of each node is even), |
139 ///if the given digraph if Euler (i.e it has only one nontrivial component |
|
140 ///and the degree of each node is even), |
|
141 ///the following code will print the arc IDs according to an |
143 ///the following code will print the arc IDs according to an |
142 ///Euler tour of \c g. |
144 ///Euler tour of \c g. |
143 ///\code |
145 ///\code |
144 /// for(EulerIt<ListGraph> e(g),e!=INVALID;++e) { |
146 /// for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) { |
145 /// std::cout << g.id(Edge(e)) << std::eol; |
147 /// std::cout << g.id(Edge(e)) << std::eol; |
146 /// } |
148 /// } |
147 ///\endcode |
149 ///\endcode |
148 ///Although the iterator provides an Euler tour of an graph, |
150 ///Although this iterator is for undirected graphs, it still returns |
149 ///it still returns Arcs in order to indicate the direction of the tour. |
151 ///arcs in order to indicate the direction of the tour. |
150 ///(But Arc will convert to Edges, of course). |
152 ///(But arcs convert to edges, of course.) |
151 /// |
153 /// |
152 ///If \c g is not Euler then the resulted tour will not be full or closed. |
154 ///If \c g has no Euler tour, then the resulted walk will not be closed |
153 ///\sa EulerIt |
155 ///or not contain all edges. |
154 template<typename GR> |
156 template<typename GR> |
155 class EulerIt |
157 class EulerIt |
156 { |
158 { |
157 typedef typename GR::Node Node; |
159 typedef typename GR::Node Node; |
158 typedef typename GR::NodeIt NodeIt; |
160 typedef typename GR::NodeIt NodeIt; |
161 typedef typename GR::ArcIt ArcIt; |
163 typedef typename GR::ArcIt ArcIt; |
162 typedef typename GR::OutArcIt OutArcIt; |
164 typedef typename GR::OutArcIt OutArcIt; |
163 typedef typename GR::InArcIt InArcIt; |
165 typedef typename GR::InArcIt InArcIt; |
164 |
166 |
165 const GR &g; |
167 const GR &g; |
166 typename GR::template NodeMap<OutArcIt> nedge; |
168 typename GR::template NodeMap<OutArcIt> narc; |
167 typename GR::template EdgeMap<bool> visited; |
169 typename GR::template EdgeMap<bool> visited; |
168 std::list<Arc> euler; |
170 std::list<Arc> euler; |
169 |
171 |
170 public: |
172 public: |
171 |
173 |
172 ///Constructor |
174 ///Constructor |
173 |
175 |
174 ///\param gr An graph. |
176 ///Constructor. |
175 ///\param start The starting point of the tour. If it is not given |
177 ///\param gr A graph. |
176 /// the tour will start from the first node. |
178 ///\param start The starting point of the tour. If it is not given, |
|
179 ///the tour will start from the first node that has an incident edge. |
177 EulerIt(const GR &gr, typename GR::Node start = INVALID) |
180 EulerIt(const GR &gr, typename GR::Node start = INVALID) |
178 : g(gr), nedge(g), visited(g, false) |
181 : g(gr), narc(g), visited(g, false) |
179 { |
182 { |
180 if (start==INVALID) { |
183 if (start==INVALID) { |
181 NodeIt n(g); |
184 NodeIt n(g); |
182 while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; |
185 while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; |
183 start=n; |
186 start=n; |
184 } |
187 } |
185 if (start!=INVALID) { |
188 if (start!=INVALID) { |
186 for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n); |
189 for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n); |
187 while(nedge[start]!=INVALID) { |
190 while(narc[start]!=INVALID) { |
188 euler.push_back(nedge[start]); |
191 euler.push_back(narc[start]); |
189 visited[nedge[start]]=true; |
192 visited[narc[start]]=true; |
190 Node next=g.target(nedge[start]); |
193 Node next=g.target(narc[start]); |
191 ++nedge[start]; |
194 ++narc[start]; |
192 start=next; |
195 start=next; |
193 while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; |
196 while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start]; |
194 } |
197 } |
195 } |
198 } |
196 } |
199 } |
197 |
200 |
198 ///Arc Conversion |
201 ///Arc conversion |
199 operator Arc() const { return euler.empty()?INVALID:euler.front(); } |
202 operator Arc() const { return euler.empty()?INVALID:euler.front(); } |
200 ///Arc Conversion |
203 ///Edge conversion |
201 operator Edge() const { return euler.empty()?INVALID:euler.front(); } |
204 operator Edge() const { return euler.empty()?INVALID:euler.front(); } |
202 ///\e |
205 ///Compare with \c INVALID |
203 bool operator==(Invalid) const { return euler.empty(); } |
206 bool operator==(Invalid) const { return euler.empty(); } |
204 ///\e |
207 ///Compare with \c INVALID |
205 bool operator!=(Invalid) const { return !euler.empty(); } |
208 bool operator!=(Invalid) const { return !euler.empty(); } |
206 |
209 |
207 ///Next arc of the tour |
210 ///Next arc of the tour |
|
211 |
|
212 ///Next arc of the tour |
|
213 /// |
208 EulerIt &operator++() { |
214 EulerIt &operator++() { |
209 Node s=g.target(euler.front()); |
215 Node s=g.target(euler.front()); |
210 euler.pop_front(); |
216 euler.pop_front(); |
211 typename std::list<Arc>::iterator next=euler.begin(); |
217 typename std::list<Arc>::iterator next=euler.begin(); |
212 |
218 while(narc[s]!=INVALID) { |
213 while(nedge[s]!=INVALID) { |
219 while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s]; |
214 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; |
220 if(narc[s]==INVALID) break; |
215 if(nedge[s]==INVALID) break; |
|
216 else { |
221 else { |
217 euler.insert(next,nedge[s]); |
222 euler.insert(next,narc[s]); |
218 visited[nedge[s]]=true; |
223 visited[narc[s]]=true; |
219 Node n=g.target(nedge[s]); |
224 Node n=g.target(narc[s]); |
220 ++nedge[s]; |
225 ++narc[s]; |
221 s=n; |
226 s=n; |
222 } |
227 } |
223 } |
228 } |
224 return *this; |
229 return *this; |
225 } |
230 } |
226 |
231 |
227 ///Postfix incrementation |
232 ///Postfix incrementation |
228 |
233 |
229 ///\warning This incrementation |
234 /// Postfix incrementation. |
230 ///returns an \c Arc, not an \ref EulerIt, as one may |
235 /// |
231 ///expect. |
236 ///\warning This incrementation returns an \c Arc (which converts to |
|
237 ///an \c Edge), not an \ref EulerIt, as one may expect. |
232 Arc operator++(int) |
238 Arc operator++(int) |
233 { |
239 { |
234 Arc e=*this; |
240 Arc e=*this; |
235 ++(*this); |
241 ++(*this); |
236 return e; |
242 return e; |
237 } |
243 } |
238 }; |
244 }; |
239 |
245 |
240 |
246 |
241 ///Checks if the graph is Eulerian |
247 ///Check if the given graph is \e Eulerian |
242 |
248 |
243 /// \ingroup graph_properties |
249 /// \ingroup graph_properties |
244 ///Checks if the graph is Eulerian. It works for both directed and undirected |
250 ///This function checks if the given graph is \e Eulerian. |
245 ///graphs. |
251 ///It works for both directed and undirected graphs. |
246 ///\note By definition, a digraph is called \e Eulerian if |
252 /// |
247 ///and only if it is connected and the number of its incoming and outgoing |
253 ///By definition, a digraph is called \e Eulerian if |
|
254 ///and only if it is connected and the number of incoming and outgoing |
248 ///arcs are the same for each node. |
255 ///arcs are the same for each node. |
249 ///Similarly, an undirected graph is called \e Eulerian if |
256 ///Similarly, an undirected graph is called \e Eulerian if |
250 ///and only if it is connected and the number of incident arcs is even |
257 ///and only if it is connected and the number of incident edges is even |
251 ///for each node. <em>Therefore, there are digraphs which are not Eulerian, |
258 ///for each node. |
252 ///but still have an Euler tour</em>. |
259 /// |
|
260 ///\note There are (di)graphs that are not Eulerian, but still have an |
|
261 /// Euler tour, since they may contain isolated nodes. |
|
262 /// |
|
263 ///\sa DiEulerIt, EulerIt |
253 template<typename GR> |
264 template<typename GR> |
254 #ifdef DOXYGEN |
265 #ifdef DOXYGEN |
255 bool |
266 bool |
256 #else |
267 #else |
257 typename enable_if<UndirectedTagIndicator<GR>,bool>::type |
268 typename enable_if<UndirectedTagIndicator<GR>,bool>::type |