1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
22 #include<lemon/core.h>
23 #include<lemon/adaptors.h>
24 #include<lemon/connectivity.h>
27 /// \ingroup graph_prop
31 ///This file provides an Euler tour iterator and ways to check
32 ///if a digraph is euler.
37 ///Euler iterator for digraphs.
39 /// \ingroup graph_prop
40 ///This iterator converts to the \c Arc type of the digraph and using
41 ///operator ++, it provides an Euler tour of a \e directed
42 ///graph (if there exists).
45 ///if the given digraph is Euler (i.e it has only one nontrivial component
46 ///and the in-degree is equal to the out-degree for all nodes),
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.
51 /// std::vector<ListDigraph::Arc> et;
52 /// for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
55 ///If \c g is not Euler then the resulted tour will not be full or closed.
57 ///\todo Test required
58 template<class Digraph>
61 typedef typename Digraph::Node Node;
62 typedef typename Digraph::NodeIt NodeIt;
63 typedef typename Digraph::Arc Arc;
64 typedef typename Digraph::ArcIt ArcIt;
65 typedef typename Digraph::OutArcIt OutArcIt;
66 typedef typename Digraph::InArcIt InArcIt;
69 typename Digraph::template NodeMap<OutArcIt> nedge;
76 ///\param _g A digraph.
77 ///\param start The starting point of the tour. If it is not given
78 /// the tour will start from the first node.
79 DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
82 if(start==INVALID) start=NodeIt(g);
83 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
84 while(nedge[start]!=INVALID) {
85 euler.push_back(nedge[start]);
86 Node next=g.target(nedge[start]);
93 operator Arc() { return euler.empty()?INVALID:euler.front(); }
94 bool operator==(Invalid) { return euler.empty(); }
95 bool operator!=(Invalid) { return !euler.empty(); }
97 ///Next arc of the tour
98 DiEulerIt &operator++() {
99 Node s=g.target(euler.front());
101 //This produces a warning.Strange.
102 //std::list<Arc>::iterator next=euler.begin();
103 typename std::list<Arc>::iterator next=euler.begin();
104 while(nedge[s]!=INVALID) {
105 euler.insert(next,nedge[s]);
106 Node n=g.target(nedge[s]);
112 ///Postfix incrementation
114 ///\warning This incrementation
115 ///returns an \c Arc, not an \ref DiEulerIt, as one may
125 ///Euler iterator for graphs.
127 /// \ingroup graph_prop
128 ///This iterator converts to the \c Arc (or \c Edge)
129 ///type of the digraph and using
130 ///operator ++, it provides an Euler tour of an undirected
131 ///digraph (if there exists).
134 ///if the given digraph if Euler (i.e it has only one nontrivial component
135 ///and the degree of each node is even),
136 ///the following code will print the arc IDs according to an
137 ///Euler tour of \c g.
139 /// for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
140 /// std::cout << g.id(Edge(e)) << std::eol;
143 ///Although the iterator provides an Euler tour of an graph,
144 ///it still returns Arcs in order to indicate the direction of the tour.
145 ///(But Arc will convert to Edges, of course).
147 ///If \c g is not Euler then the resulted tour will not be full or closed.
149 ///\todo Test required
150 template<class Digraph>
153 typedef typename Digraph::Node Node;
154 typedef typename Digraph::NodeIt NodeIt;
155 typedef typename Digraph::Arc Arc;
156 typedef typename Digraph::Edge Edge;
157 typedef typename Digraph::ArcIt ArcIt;
158 typedef typename Digraph::OutArcIt OutArcIt;
159 typedef typename Digraph::InArcIt InArcIt;
162 typename Digraph::template NodeMap<OutArcIt> nedge;
163 typename Digraph::template EdgeMap<bool> visited;
164 std::list<Arc> euler;
170 ///\param _g An graph.
171 ///\param start The starting point of the tour. If it is not given
172 /// the tour will start from the first node.
173 EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
174 : g(_g), nedge(g), visited(g,false)
176 if(start==INVALID) start=NodeIt(g);
177 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
178 while(nedge[start]!=INVALID) {
179 euler.push_back(nedge[start]);
180 visited[nedge[start]]=true;
181 Node next=g.target(nedge[start]);
184 while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
189 operator Arc() const { return euler.empty()?INVALID:euler.front(); }
191 operator Edge() const { return euler.empty()?INVALID:euler.front(); }
193 bool operator==(Invalid) const { return euler.empty(); }
195 bool operator!=(Invalid) const { return !euler.empty(); }
197 ///Next arc of the tour
198 EulerIt &operator++() {
199 Node s=g.target(euler.front());
201 typename std::list<Arc>::iterator next=euler.begin();
203 while(nedge[s]!=INVALID) {
204 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
205 if(nedge[s]==INVALID) break;
207 euler.insert(next,nedge[s]);
208 visited[nedge[s]]=true;
209 Node n=g.target(nedge[s]);
217 ///Postfix incrementation
219 ///\warning This incrementation
220 ///returns an \c Arc, not an \ref EulerIt, as one may
231 ///Checks if the graph is Eulerian
233 /// \ingroup graph_prop
234 ///Checks if the graph is Eulerian. It works for both directed and undirected
236 ///\note By definition, a digraph is called \e Eulerian if
237 ///and only if it is connected and the number of its incoming and outgoing
238 ///arcs are the same for each node.
239 ///Similarly, an undirected graph is called \e Eulerian if
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 Eulerian,
242 ///but still have an Euler tour</em>.
243 ///\todo Test required
244 template<class Digraph>
248 typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
249 eulerian(const Digraph &g)
251 for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
252 if(countIncEdges(g,n)%2) return false;
255 template<class Digraph>
256 typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
258 eulerian(const Digraph &g)
260 for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
261 if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
262 return connected(Undirector<const Digraph>(g));