COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/euler.h @ 540:9db62975c32b

Last change on this file since 540:9db62975c32b was 522:22f932bbb305, checked in by Akos Ladanyi <ladanyi@…>, 15 years ago

Test for euler.h (#65)

File size: 7.7 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_EULER_H
20#define LEMON_EULER_H
21
22#include<lemon/core.h>
23#include<lemon/adaptors.h>
24#include<lemon/connectivity.h>
25#include <list>
26
27/// \ingroup graph_prop
28/// \file
29/// \brief Euler tour
30///
31///This file provides an Euler tour iterator and ways to check
32///if a digraph is euler.
33
34
35namespace lemon {
36
37  ///Euler iterator for digraphs.
38
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).
43  ///
44  ///For example
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.
50  ///\code
51  ///  std::vector<ListDigraph::Arc> et;
52  ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
53  ///    et.push_back(e);
54  ///\endcode
55  ///If \c g is not Euler then the resulted tour will not be full or closed.
56  ///\sa EulerIt
57  template<class Digraph>
58  class DiEulerIt
59  {
60    typedef typename Digraph::Node Node;
61    typedef typename Digraph::NodeIt NodeIt;
62    typedef typename Digraph::Arc Arc;
63    typedef typename Digraph::ArcIt ArcIt;
64    typedef typename Digraph::OutArcIt OutArcIt;
65    typedef typename Digraph::InArcIt InArcIt;
66
67    const Digraph &g;
68    typename Digraph::template NodeMap<OutArcIt> nedge;
69    std::list<Arc> euler;
70
71  public:
72
73    ///Constructor
74
75    ///\param _g 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 Digraph &_g,typename Digraph::Node start=INVALID)
79      : g(_g), nedge(g)
80    {
81      if(start==INVALID) start=NodeIt(g);
82      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
83      while(nedge[start]!=INVALID) {
84        euler.push_back(nedge[start]);
85        Node next=g.target(nedge[start]);
86        ++nedge[start];
87        start=next;
88      }
89    }
90
91    ///Arc Conversion
92    operator Arc() { return euler.empty()?INVALID:euler.front(); }
93    bool operator==(Invalid) { return euler.empty(); }
94    bool operator!=(Invalid) { return !euler.empty(); }
95
96    ///Next arc of the tour
97    DiEulerIt &operator++() {
98      Node s=g.target(euler.front());
99      euler.pop_front();
100      //This produces a warning.Strange.
101      //std::list<Arc>::iterator next=euler.begin();
102      typename std::list<Arc>::iterator next=euler.begin();
103      while(nedge[s]!=INVALID) {
104        euler.insert(next,nedge[s]);
105        Node n=g.target(nedge[s]);
106        ++nedge[s];
107        s=n;
108      }
109      return *this;
110    }
111    ///Postfix incrementation
112
113    ///\warning This incrementation
114    ///returns an \c Arc, not an \ref DiEulerIt, as one may
115    ///expect.
116    Arc operator++(int)
117    {
118      Arc e=*this;
119      ++(*this);
120      return e;
121    }
122  };
123
124  ///Euler iterator for graphs.
125
126  /// \ingroup graph_prop
127  ///This iterator converts to the \c Arc (or \c Edge)
128  ///type of the digraph and using
129  ///operator ++, it provides an Euler tour of an undirected
130  ///digraph (if there exists).
131  ///
132  ///For example
133  ///if the given digraph if Euler (i.e it has only one nontrivial component
134  ///and the degree of each node is even),
135  ///the following code will print the arc IDs according to an
136  ///Euler tour of \c g.
137  ///\code
138  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
139  ///    std::cout << g.id(Edge(e)) << std::eol;
140  ///  }
141  ///\endcode
142  ///Although the iterator provides an Euler tour of an graph,
143  ///it still returns Arcs in order to indicate the direction of the tour.
144  ///(But Arc will convert to Edges, of course).
145  ///
146  ///If \c g is not Euler then the resulted tour will not be full or closed.
147  ///\sa EulerIt
148  template<class Digraph>
149  class EulerIt
150  {
151    typedef typename Digraph::Node Node;
152    typedef typename Digraph::NodeIt NodeIt;
153    typedef typename Digraph::Arc Arc;
154    typedef typename Digraph::Edge Edge;
155    typedef typename Digraph::ArcIt ArcIt;
156    typedef typename Digraph::OutArcIt OutArcIt;
157    typedef typename Digraph::InArcIt InArcIt;
158
159    const Digraph &g;
160    typename Digraph::template NodeMap<OutArcIt> nedge;
161    typename Digraph::template EdgeMap<bool> visited;
162    std::list<Arc> euler;
163
164  public:
165
166    ///Constructor
167
168    ///\param _g An graph.
169    ///\param start The starting point of the tour. If it is not given
170    ///       the tour will start from the first node.
171    EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
172      : g(_g), nedge(g), visited(g,false)
173    {
174      if(start==INVALID) start=NodeIt(g);
175      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
176      while(nedge[start]!=INVALID) {
177        euler.push_back(nedge[start]);
178        visited[nedge[start]]=true;
179        Node next=g.target(nedge[start]);
180        ++nedge[start];
181        start=next;
182        while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
183      }
184    }
185
186    ///Arc Conversion
187    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
188    ///Arc Conversion
189    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
190    ///\e
191    bool operator==(Invalid) const { return euler.empty(); }
192    ///\e
193    bool operator!=(Invalid) const { return !euler.empty(); }
194
195    ///Next arc of the tour
196    EulerIt &operator++() {
197      Node s=g.target(euler.front());
198      euler.pop_front();
199      typename std::list<Arc>::iterator next=euler.begin();
200
201      while(nedge[s]!=INVALID) {
202        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
203        if(nedge[s]==INVALID) break;
204        else {
205          euler.insert(next,nedge[s]);
206          visited[nedge[s]]=true;
207          Node n=g.target(nedge[s]);
208          ++nedge[s];
209          s=n;
210        }
211      }
212      return *this;
213    }
214
215    ///Postfix incrementation
216
217    ///\warning This incrementation
218    ///returns an \c Arc, not an \ref EulerIt, as one may
219    ///expect.
220    Arc operator++(int)
221    {
222      Arc e=*this;
223      ++(*this);
224      return e;
225    }
226  };
227
228
229  ///Checks if the graph is Eulerian
230
231  /// \ingroup graph_prop
232  ///Checks if the graph is Eulerian. It works for both directed and undirected
233  ///graphs.
234  ///\note By definition, a digraph is called \e Eulerian if
235  ///and only if it is connected and the number of its incoming and outgoing
236  ///arcs are the same for each node.
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
239  ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
240  ///but still have an Euler tour</em>.
241  template<class Digraph>
242#ifdef DOXYGEN
243  bool
244#else
245  typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
246  eulerian(const Digraph &g)
247  {
248    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
249      if(countIncEdges(g,n)%2) return false;
250    return connected(g);
251  }
252  template<class Digraph>
253  typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
254#endif
255  eulerian(const Digraph &g)
256  {
257    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
258      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
259    return connected(Undirector<const Digraph>(g));
260  }
261
262}
263
264#endif
Note: See TracBrowser for help on using the repository browser.