MALE and FEMALE node shape added.
2 * lemon/euler.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
16 #include<lemon/invalid.h>
17 #include<lemon/topology.h>
24 ///This file provides an Euler tour iterator and ways to check
25 ///if a graph is euler.
30 ///Euler iterator for directed graphs.
33 ///This iterator converts to the \c Edge type of the graph and using
34 ///operator ++ it provides an Euler tour of the graph (if there exists).
37 ///if the given graph if Euler (i.e it has only one nontrivial component
38 ///and the in-degree is equal to the out-degree for all nodes),
39 ///the following code will print the edge IDs according to an
40 ///Euler tour of \c g.
42 /// for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
43 /// std::cout << g.id(e) << std::eol;
46 ///If \c g is not Euler then the resulted tour will not be full or closed.
47 ///\todo Test required
51 typedef typename Graph::Node Node;
52 typedef typename Graph::NodeIt NodeIt;
53 typedef typename Graph::Edge Edge;
54 typedef typename Graph::EdgeIt EdgeIt;
55 typedef typename Graph::OutEdgeIt OutEdgeIt;
56 typedef typename Graph::InEdgeIt InEdgeIt;
59 typename Graph::NodeMap<OutEdgeIt> nedge;
60 std::list<Edge> euler;
66 ///\param _g A directed graph.
67 ///\param start The starting point of the tour. If it is not given
68 /// the tour will start from the first node.
69 EulerIt(const Graph &_g,typename Graph::Node start=INVALID)
72 if(start==INVALID) start=NodeIt(g);
73 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
74 while(nedge[start]!=INVALID) {
75 euler.push_back(nedge[start]);
76 Node next=g.target(nedge[start]);
83 operator Edge() { return euler.empty()?INVALID:euler.front(); }
84 bool operator==(Invalid) { return euler.empty(); }
85 bool operator!=(Invalid) { return !euler.empty(); }
87 ///Next edge of the tour
88 EulerIt &operator++() {
89 Node s=g.target(euler.front());
91 //This produces a warning.Strange.
92 //std::list<Edge>::iterator next=euler.begin();
93 typename std::list<Edge>::iterator next=euler.begin();
94 while(nedge[s]!=INVALID) {
95 euler.insert(next,nedge[s]);
96 Node n=g.target(nedge[s]);
102 ///Postfix incrementation
104 ///\warning This incrementation
105 ///returns an \c Edge, not an \ref EulerIt, as one may
115 ///Euler iterator for undirected graphs.
117 /// \ingroup topology
118 ///This iterator converts to the \c Edge type of the graph and using
119 ///operator ++ it provides an Euler tour of the graph (if there exists).
122 ///if the given graph if Euler (i.e it has only one nontrivial component
123 ///and the degree of each node is even),
124 ///the following code will print the edge IDs according to an
125 ///Euler tour of \c g.
127 /// for(UndirEulerIt<UndirListGraph> e(g),e!=INVALID;++e) {
128 /// std::cout << g.id(UndirEdge(e)) << std::eol;
131 ///Although the iterator provides an Euler tour of an undirected graph,
132 ///in order to indicate the direction of the tour, UndirEulerIt
133 ///returns directed edges (that convert to the undirected ones, of course).
135 ///If \c g is not Euler then the resulted tour will not be full or closed.
136 ///\todo Test required
137 template<class Graph>
140 typedef typename Graph::Node Node;
141 typedef typename Graph::NodeIt NodeIt;
142 typedef typename Graph::Edge Edge;
143 typedef typename Graph::EdgeIt EdgeIt;
144 typedef typename Graph::OutEdgeIt OutEdgeIt;
145 typedef typename Graph::InEdgeIt InEdgeIt;
148 typename Graph::NodeMap<OutEdgeIt> nedge;
149 typename Graph::UndirEdgeMap<bool> visited;
150 std::list<Edge> euler;
156 ///\param _g An undirected graph.
157 ///\param start The starting point of the tour. If it is not given
158 /// the tour will start from the first node.
159 UndirEulerIt(const Graph &_g,typename Graph::Node start=INVALID)
160 : g(_g), nedge(g), visited(g,false)
162 if(start==INVALID) start=NodeIt(g);
163 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
164 while(nedge[start]!=INVALID) {
165 euler.push_back(nedge[start]);
166 Node next=g.target(nedge[start]);
168 start=next; while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
173 operator Edge() { return euler.empty()?INVALID:euler.front(); }
174 bool operator==(Invalid) { return euler.empty(); }
175 bool operator!=(Invalid) { return !euler.empty(); }
177 ///Next edge of the tour
178 UndirEulerIt &operator++() {
179 Node s=g.target(euler.front());
181 typename std::list<Edge>::iterator next=euler.begin();
183 while(nedge[s]!=INVALID) {
184 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
185 if(nedge[s]==INVALID) break;
187 euler.insert(next,nedge[s]);
188 Node n=g.target(nedge[s]);
196 ///Postfix incrementation
198 ///\warning This incrementation
199 ///returns an \c Edge, not an \ref UndirEulerIt, as one may
210 ///Checks if the graph is Euler
212 /// \ingroup topology
213 ///Checks if the graph is Euler. It works for both directed and
214 ///undirected graphs.
215 ///\note By definition, a directed graph is called \e Euler if
216 ///and only if connected and the number of it is incoming and outgoing edges
217 ///are the same for each node.
218 ///Similarly, an undirected graph is called \e Euler if
219 ///and only if it is connected and the number of incident edges is even
220 ///for each node. <em>Therefore, there are graphs which are not Euler, but
221 ///still have an Euler tour</em>.
222 ///\todo Test required
223 template<class Graph>
227 typename enable_if<typename Graph::UndirTag,bool>::type
228 euler(const Graph &g)
230 for(typename Graph::NodeIt n(g);n!=INVALID;++n)
231 if(countIncEdges(g,n)%2) return false;
234 template<class Graph>
235 typename disable_if<typename Graph::UndirTag,bool>::type
237 euler(const Graph &g)
239 for(typename Graph::NodeIt n(g);n!=INVALID;++n)
240 if(countInEdges(g,n)!=countOutEdges(g,n)) return false;