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_properties
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_properties
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.
60 typedef typename GR::Node Node;
61 typedef typename GR::NodeIt NodeIt;
62 typedef typename GR::Arc Arc;
63 typedef typename GR::ArcIt ArcIt;
64 typedef typename GR::OutArcIt OutArcIt;
65 typedef typename GR::InArcIt InArcIt;
68 typename GR::template NodeMap<OutArcIt> nedge;
75 ///\param gr A digraph.
76 ///\param start The starting point of the tour. If it is not given
77 /// the tour will start from the first node.
78 DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
83 while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
87 for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
88 while (nedge[start]!=INVALID) {
89 euler.push_back(nedge[start]);
90 Node next=g.target(nedge[start]);
98 operator Arc() { return euler.empty()?INVALID:euler.front(); }
99 bool operator==(Invalid) { return euler.empty(); }
100 bool operator!=(Invalid) { return !euler.empty(); }
102 ///Next arc of the tour
103 DiEulerIt &operator++() {
104 Node s=g.target(euler.front());
106 //This produces a warning.Strange.
107 //std::list<Arc>::iterator next=euler.begin();
108 typename std::list<Arc>::iterator next=euler.begin();
109 while(nedge[s]!=INVALID) {
110 euler.insert(next,nedge[s]);
111 Node n=g.target(nedge[s]);
117 ///Postfix incrementation
119 ///\warning This incrementation
120 ///returns an \c Arc, not an \ref DiEulerIt, as one may
130 ///Euler iterator for graphs.
132 /// \ingroup graph_properties
133 ///This iterator converts to the \c Arc (or \c Edge)
134 ///type of the digraph and using
135 ///operator ++, it provides an Euler tour of an undirected
136 ///digraph (if there exists).
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
142 ///Euler tour of \c g.
144 /// for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
145 /// std::cout << g.id(Edge(e)) << std::eol;
148 ///Although the iterator provides an Euler tour of an graph,
149 ///it still returns Arcs in order to indicate the direction of the tour.
150 ///(But Arc will convert to Edges, of course).
152 ///If \c g is not Euler then the resulted tour will not be full or closed.
154 template<typename GR>
157 typedef typename GR::Node Node;
158 typedef typename GR::NodeIt NodeIt;
159 typedef typename GR::Arc Arc;
160 typedef typename GR::Edge Edge;
161 typedef typename GR::ArcIt ArcIt;
162 typedef typename GR::OutArcIt OutArcIt;
163 typedef typename GR::InArcIt InArcIt;
166 typename GR::template NodeMap<OutArcIt> nedge;
167 typename GR::template EdgeMap<bool> visited;
168 std::list<Arc> euler;
174 ///\param gr An graph.
175 ///\param start The starting point of the tour. If it is not given
176 /// the tour will start from the first node.
177 EulerIt(const GR &gr, typename GR::Node start = INVALID)
178 : g(gr), nedge(g), visited(g, false)
180 if (start==INVALID) {
182 while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
185 if (start!=INVALID) {
186 for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
187 while(nedge[start]!=INVALID) {
188 euler.push_back(nedge[start]);
189 visited[nedge[start]]=true;
190 Node next=g.target(nedge[start]);
193 while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
199 operator Arc() const { return euler.empty()?INVALID:euler.front(); }
201 operator Edge() const { return euler.empty()?INVALID:euler.front(); }
203 bool operator==(Invalid) const { return euler.empty(); }
205 bool operator!=(Invalid) const { return !euler.empty(); }
207 ///Next arc of the tour
208 EulerIt &operator++() {
209 Node s=g.target(euler.front());
211 typename std::list<Arc>::iterator next=euler.begin();
213 while(nedge[s]!=INVALID) {
214 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
215 if(nedge[s]==INVALID) break;
217 euler.insert(next,nedge[s]);
218 visited[nedge[s]]=true;
219 Node n=g.target(nedge[s]);
227 ///Postfix incrementation
229 ///\warning This incrementation
230 ///returns an \c Arc, not an \ref EulerIt, as one may
241 ///Checks if the graph is Eulerian
243 /// \ingroup graph_properties
244 ///Checks if the graph is Eulerian. It works for both directed and undirected
246 ///\note By definition, a digraph is called \e Eulerian if
247 ///and only if it is connected and the number of its incoming and outgoing
248 ///arcs are the same for each node.
249 ///Similarly, an undirected graph is called \e Eulerian if
250 ///and only if it is connected and the number of incident arcs is even
251 ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
252 ///but still have an Euler tour</em>.
253 template<typename GR>
257 typename enable_if<UndirectedTagIndicator<GR>,bool>::type
258 eulerian(const GR &g)
260 for(typename GR::NodeIt n(g);n!=INVALID;++n)
261 if(countIncEdges(g,n)%2) return false;
265 typename disable_if<UndirectedTagIndicator<GR>,bool>::type
267 eulerian(const GR &g)
269 for(typename GR::NodeIt n(g);n!=INVALID;++n)
270 if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
271 return connected(Undirector<const GR>(g));