COIN-OR::LEMON - Graph Library

source: lemon/lemon/euler.h @ 567:42d4b889903a

Last change on this file since 567:42d4b889903a was 567:42d4b889903a, checked in by Alpar Juttner <alpar@…>, 11 years ago

Port Euler walk tools from SVN -r3512 (#65)

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