1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2009 |
5 * Copyright (C) 2003-2010 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
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 iterators and a function for checking the \e Eulerian |
29 /// \brief Euler tour iterators and a function for checking the \e Eulerian |
30 /// property. |
30 /// property. |
31 /// |
31 /// |
32 ///This file provides Euler tour iterators and a function to check |
32 ///This file provides Euler tour iterators and a function to check |
33 ///if a (di)graph is \e Eulerian. |
33 ///if a (di)graph is \e Eulerian. |
34 |
34 |
39 /// \ingroup graph_prop |
39 /// \ingroup graph_prop |
40 ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed |
40 ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed |
41 ///graph (if there exists) and it converts to the \c Arc type of the digraph. |
41 ///graph (if there exists) and it converts to the \c Arc type of the digraph. |
42 /// |
42 /// |
43 ///For example, if the given digraph has an Euler tour (i.e it has only one |
43 ///For example, if the given digraph has an Euler tour (i.e it has only one |
44 ///non-trivial component and the in-degree is equal to the out-degree |
44 ///non-trivial component and the in-degree is equal to the out-degree |
45 ///for all nodes), then the following code will put the arcs of \c g |
45 ///for all nodes), then the following code will put the arcs of \c g |
46 ///to the vector \c et according to an Euler tour of \c g. |
46 ///to the vector \c et according to an Euler tour of \c g. |
47 ///\code |
47 ///\code |
48 /// std::vector<ListDigraph::Arc> et; |
48 /// std::vector<ListDigraph::Arc> et; |
49 /// for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e) |
49 /// for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e) |
136 /// \ingroup graph_properties |
136 /// \ingroup graph_properties |
137 ///This iterator provides an Euler tour (Eulerian circuit) of an |
137 ///This iterator provides an Euler tour (Eulerian circuit) of an |
138 ///\e undirected graph (if there exists) and it converts to the \c Arc |
138 ///\e undirected graph (if there exists) and it converts to the \c Arc |
139 ///and \c Edge types of the graph. |
139 ///and \c Edge types of the graph. |
140 /// |
140 /// |
141 ///For example, if the given graph has an Euler tour (i.e it has only one |
141 ///For example, if the given graph has an Euler tour (i.e it has only one |
142 ///non-trivial component and the degree of each node is even), |
142 ///non-trivial component and the degree of each node is even), |
143 ///the following code will print the arc IDs according to an |
143 ///the following code will print the arc IDs according to an |
144 ///Euler tour of \c g. |
144 ///Euler tour of \c g. |
145 ///\code |
145 ///\code |
146 /// for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) { |
146 /// for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) { |
147 /// std::cout << g.id(Edge(e)) << std::eol; |
147 /// std::cout << g.id(Edge(e)) << std::eol; |
148 /// } |
148 /// } |
149 ///\endcode |
149 ///\endcode |
150 ///Although this iterator is for undirected graphs, it still returns |
150 ///Although this iterator is for undirected graphs, it still returns |
151 ///arcs in order to indicate the direction of the tour. |
151 ///arcs in order to indicate the direction of the tour. |
152 ///(But arcs convert to edges, of course.) |
152 ///(But arcs convert to edges, of course.) |
153 /// |
153 /// |
154 ///If \c g has no Euler tour, then the resulted walk will not be closed |
154 ///If \c g has no Euler tour, then the resulted walk will not be closed |
155 ///or not contain all edges. |
155 ///or not contain all edges. |
231 |
231 |
232 ///Postfix incrementation |
232 ///Postfix incrementation |
233 |
233 |
234 /// Postfix incrementation. |
234 /// Postfix incrementation. |
235 /// |
235 /// |
236 ///\warning This incrementation returns an \c Arc (which converts to |
236 ///\warning This incrementation returns an \c Arc (which converts to |
237 ///an \c Edge), not an \ref EulerIt, as one may expect. |
237 ///an \c Edge), not an \ref EulerIt, as one may expect. |
238 Arc operator++(int) |
238 Arc operator++(int) |
239 { |
239 { |
240 Arc e=*this; |
240 Arc e=*this; |
241 ++(*this); |
241 ++(*this); |