COIN-OR::LEMON - Graph Library

source: lemon/lemon/euler.h @ 638:493533ead9df

Last change on this file since 638:493533ead9df was 638:493533ead9df, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Bug fix in the Euler iterators (#264)
Handle the case when the first node is isolated.

File size: 7.9 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_properties
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_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).
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<typename GR>
58  class DiEulerIt
59  {
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;
66
67    const GR &g;
68    typename GR::template NodeMap<OutArcIt> nedge;
69    std::list<Arc> euler;
70
71  public:
72
73    ///Constructor
74
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)
79      : g(gr), nedge(g)
80    {
81      if (start==INVALID) {
82        NodeIt n(g);
83        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
84        start=n;
85      }
86      if (start!=INVALID) {
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]);
91          ++nedge[start];
92          start=next;
93        }
94      }
95    }
96
97    ///Arc Conversion
98    operator Arc() { return euler.empty()?INVALID:euler.front(); }
99    bool operator==(Invalid) { return euler.empty(); }
100    bool operator!=(Invalid) { return !euler.empty(); }
101
102    ///Next arc of the tour
103    DiEulerIt &operator++() {
104      Node s=g.target(euler.front());
105      euler.pop_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]);
112        ++nedge[s];
113        s=n;
114      }
115      return *this;
116    }
117    ///Postfix incrementation
118
119    ///\warning This incrementation
120    ///returns an \c Arc, not an \ref DiEulerIt, as one may
121    ///expect.
122    Arc operator++(int)
123    {
124      Arc e=*this;
125      ++(*this);
126      return e;
127    }
128  };
129
130  ///Euler iterator for graphs.
131
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).
137  ///
138  ///For example
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.
143  ///\code
144  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
145  ///    std::cout << g.id(Edge(e)) << std::eol;
146  ///  }
147  ///\endcode
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).
151  ///
152  ///If \c g is not Euler then the resulted tour will not be full or closed.
153  ///\sa EulerIt
154  template<typename GR>
155  class EulerIt
156  {
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;
164
165    const GR &g;
166    typename GR::template NodeMap<OutArcIt> nedge;
167    typename GR::template EdgeMap<bool> visited;
168    std::list<Arc> euler;
169
170  public:
171
172    ///Constructor
173
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)
179    {
180      if (start==INVALID) {
181        NodeIt n(g);
182        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
183        start=n;
184      }
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]);
191          ++nedge[start];
192          start=next;
193          while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
194        }
195      }
196    }
197
198    ///Arc Conversion
199    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
200    ///Arc Conversion
201    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
202    ///\e
203    bool operator==(Invalid) const { return euler.empty(); }
204    ///\e
205    bool operator!=(Invalid) const { return !euler.empty(); }
206
207    ///Next arc of the tour
208    EulerIt &operator++() {
209      Node s=g.target(euler.front());
210      euler.pop_front();
211      typename std::list<Arc>::iterator next=euler.begin();
212
213      while(nedge[s]!=INVALID) {
214        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
215        if(nedge[s]==INVALID) break;
216        else {
217          euler.insert(next,nedge[s]);
218          visited[nedge[s]]=true;
219          Node n=g.target(nedge[s]);
220          ++nedge[s];
221          s=n;
222        }
223      }
224      return *this;
225    }
226
227    ///Postfix incrementation
228
229    ///\warning This incrementation
230    ///returns an \c Arc, not an \ref EulerIt, as one may
231    ///expect.
232    Arc operator++(int)
233    {
234      Arc e=*this;
235      ++(*this);
236      return e;
237    }
238  };
239
240
241  ///Checks if the graph is Eulerian
242
243  /// \ingroup graph_properties
244  ///Checks if the graph is Eulerian. It works for both directed and undirected
245  ///graphs.
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>
254#ifdef DOXYGEN
255  bool
256#else
257  typename enable_if<UndirectedTagIndicator<GR>,bool>::type
258  eulerian(const GR &g)
259  {
260    for(typename GR::NodeIt n(g);n!=INVALID;++n)
261      if(countIncEdges(g,n)%2) return false;
262    return connected(g);
263  }
264  template<class GR>
265  typename disable_if<UndirectedTagIndicator<GR>,bool>::type
266#endif
267  eulerian(const GR &g)
268  {
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));
272  }
273
274}
275
276#endif
Note: See TracBrowser for help on using the repository browser.