52 /// for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e) |
52 /// for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e) |
53 /// et.push_back(e); |
53 /// et.push_back(e); |
54 ///\endcode |
54 ///\endcode |
55 ///If \c g is not Euler then the resulted tour will not be full or closed. |
55 ///If \c g is not Euler then the resulted tour will not be full or closed. |
56 ///\sa EulerIt |
56 ///\sa EulerIt |
57 template<class Digraph> |
57 template<typename GR> |
58 class DiEulerIt |
58 class DiEulerIt |
59 { |
59 { |
60 typedef typename Digraph::Node Node; |
60 typedef typename GR::Node Node; |
61 typedef typename Digraph::NodeIt NodeIt; |
61 typedef typename GR::NodeIt NodeIt; |
62 typedef typename Digraph::Arc Arc; |
62 typedef typename GR::Arc Arc; |
63 typedef typename Digraph::ArcIt ArcIt; |
63 typedef typename GR::ArcIt ArcIt; |
64 typedef typename Digraph::OutArcIt OutArcIt; |
64 typedef typename GR::OutArcIt OutArcIt; |
65 typedef typename Digraph::InArcIt InArcIt; |
65 typedef typename GR::InArcIt InArcIt; |
66 |
66 |
67 const Digraph &g; |
67 const GR &g; |
68 typename Digraph::template NodeMap<OutArcIt> nedge; |
68 typename GR::template NodeMap<OutArcIt> nedge; |
69 std::list<Arc> euler; |
69 std::list<Arc> euler; |
70 |
70 |
71 public: |
71 public: |
72 |
72 |
73 ///Constructor |
73 ///Constructor |
74 |
74 |
75 ///\param _g A digraph. |
75 ///\param gr A digraph. |
76 ///\param start The starting point of the tour. If it is not given |
76 ///\param start The starting point of the tour. If it is not given |
77 /// the tour will start from the first node. |
77 /// the tour will start from the first node. |
78 DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID) |
78 DiEulerIt(const GR &gr, typename GR::Node start = INVALID) |
79 : g(_g), nedge(g) |
79 : g(gr), nedge(g) |
80 { |
80 { |
81 if(start==INVALID) start=NodeIt(g); |
81 if(start==INVALID) start=NodeIt(g); |
82 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); |
82 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); |
83 while(nedge[start]!=INVALID) { |
83 while(nedge[start]!=INVALID) { |
84 euler.push_back(nedge[start]); |
84 euler.push_back(nedge[start]); |
143 ///it still returns Arcs in order to indicate the direction of the tour. |
143 ///it still returns Arcs in order to indicate the direction of the tour. |
144 ///(But Arc will convert to Edges, of course). |
144 ///(But Arc will convert to Edges, of course). |
145 /// |
145 /// |
146 ///If \c g is not Euler then the resulted tour will not be full or closed. |
146 ///If \c g is not Euler then the resulted tour will not be full or closed. |
147 ///\sa EulerIt |
147 ///\sa EulerIt |
148 template<class Digraph> |
148 template<typename GR> |
149 class EulerIt |
149 class EulerIt |
150 { |
150 { |
151 typedef typename Digraph::Node Node; |
151 typedef typename GR::Node Node; |
152 typedef typename Digraph::NodeIt NodeIt; |
152 typedef typename GR::NodeIt NodeIt; |
153 typedef typename Digraph::Arc Arc; |
153 typedef typename GR::Arc Arc; |
154 typedef typename Digraph::Edge Edge; |
154 typedef typename GR::Edge Edge; |
155 typedef typename Digraph::ArcIt ArcIt; |
155 typedef typename GR::ArcIt ArcIt; |
156 typedef typename Digraph::OutArcIt OutArcIt; |
156 typedef typename GR::OutArcIt OutArcIt; |
157 typedef typename Digraph::InArcIt InArcIt; |
157 typedef typename GR::InArcIt InArcIt; |
158 |
158 |
159 const Digraph &g; |
159 const GR &g; |
160 typename Digraph::template NodeMap<OutArcIt> nedge; |
160 typename GR::template NodeMap<OutArcIt> nedge; |
161 typename Digraph::template EdgeMap<bool> visited; |
161 typename GR::template EdgeMap<bool> visited; |
162 std::list<Arc> euler; |
162 std::list<Arc> euler; |
163 |
163 |
164 public: |
164 public: |
165 |
165 |
166 ///Constructor |
166 ///Constructor |
167 |
167 |
168 ///\param _g An graph. |
168 ///\param gr An graph. |
169 ///\param start The starting point of the tour. If it is not given |
169 ///\param start The starting point of the tour. If it is not given |
170 /// the tour will start from the first node. |
170 /// the tour will start from the first node. |
171 EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID) |
171 EulerIt(const GR &gr, typename GR::Node start = INVALID) |
172 : g(_g), nedge(g), visited(g,false) |
172 : g(gr), nedge(g), visited(g, false) |
173 { |
173 { |
174 if(start==INVALID) start=NodeIt(g); |
174 if(start==INVALID) start=NodeIt(g); |
175 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); |
175 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); |
176 while(nedge[start]!=INVALID) { |
176 while(nedge[start]!=INVALID) { |
177 euler.push_back(nedge[start]); |
177 euler.push_back(nedge[start]); |
236 ///arcs are the same for each node. |
236 ///arcs are the same for each node. |
237 ///Similarly, an undirected graph is called \e Eulerian if |
237 ///Similarly, an undirected graph is called \e Eulerian if |
238 ///and only if it is connected and the number of incident arcs is even |
238 ///and only if it is connected and the number of incident arcs is even |
239 ///for each node. <em>Therefore, there are digraphs which are not Eulerian, |
239 ///for each node. <em>Therefore, there are digraphs which are not Eulerian, |
240 ///but still have an Euler tour</em>. |
240 ///but still have an Euler tour</em>. |
241 template<class Digraph> |
241 template<typename GR> |
242 #ifdef DOXYGEN |
242 #ifdef DOXYGEN |
243 bool |
243 bool |
244 #else |
244 #else |
245 typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type |
245 typename enable_if<UndirectedTagIndicator<GR>,bool>::type |
246 eulerian(const Digraph &g) |
246 eulerian(const GR &g) |
247 { |
247 { |
248 for(typename Digraph::NodeIt n(g);n!=INVALID;++n) |
248 for(typename GR::NodeIt n(g);n!=INVALID;++n) |
249 if(countIncEdges(g,n)%2) return false; |
249 if(countIncEdges(g,n)%2) return false; |
250 return connected(g); |
250 return connected(g); |
251 } |
251 } |
252 template<class Digraph> |
252 template<class GR> |
253 typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type |
253 typename disable_if<UndirectedTagIndicator<GR>,bool>::type |
254 #endif |
254 #endif |
255 eulerian(const Digraph &g) |
255 eulerian(const GR &g) |
256 { |
256 { |
257 for(typename Digraph::NodeIt n(g);n!=INVALID;++n) |
257 for(typename GR::NodeIt n(g);n!=INVALID;++n) |
258 if(countInArcs(g,n)!=countOutArcs(g,n)) return false; |
258 if(countInArcs(g,n)!=countOutArcs(g,n)) return false; |
259 return connected(Undirector<const Digraph>(g)); |
259 return connected(Undirector<const GR>(g)); |
260 } |
260 } |
261 |
261 |
262 } |
262 } |
263 |
263 |
264 #endif |
264 #endif |