COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/euler.h @ 1874:396831fa7012

Last change on this file since 1874:396831fa7012 was 1818:8f9905c4e1c1, checked in by Alpar Juttner, 14 years ago

UndirEulerIt? added

File size: 7.2 KB
Line 
1/* -*- C++ -*-
2 * lemon/euler.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
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.
10 *
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
13 * purpose.
14 *
15 */
16#include<lemon/invalid.h>
17#include<lemon/topology.h>
18#include <list>
19
20/// \ingroup topology
21/// \file
22/// \brief Euler tour
23///
24///This file provides an Euler tour iterator and ways to check
25///if a graph is euler.
26
27
28namespace lemon {
29
30  ///Euler iterator for directed graphs.
31
32  /// \ingroup topology
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).
35  ///
36  ///For example
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.
41  ///\code
42  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
43  ///    std::cout << g.id(e) << std::eol;
44  ///  }
45  ///\endcode
46  ///If \c g is not Euler then the resulted tour will not be full or closed.
47  ///\todo Test required
48  template<class Graph>
49  class EulerIt
50  {
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;
57   
58    const Graph &g;
59    typename Graph::NodeMap<OutEdgeIt> nedge;
60    std::list<Edge> euler;
61
62  public:
63   
64    ///Constructor
65
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)
70      : g(_g), nedge(g)
71    {
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]);
77        ++nedge[start];
78        start=next;
79      }
80    }
81   
82    ///Edge Conversion
83    operator Edge() { return euler.empty()?INVALID:euler.front(); }
84    bool operator==(Invalid) { return euler.empty(); }
85    bool operator!=(Invalid) { return !euler.empty(); }
86   
87    ///Next edge of the tour
88    EulerIt &operator++() {
89      Node s=g.target(euler.front());
90      euler.pop_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]);
97        ++nedge[s];
98        s=n;
99      }
100      return *this;
101    }
102    ///Postfix incrementation
103   
104    ///\warning This incrementation
105    ///returns an \c Edge, not an \ref EulerIt, as one may
106    ///expect.
107    Edge operator++(int)
108    {
109      Edge e=*this;
110      ++(*this);
111      return e;
112    }
113  };
114
115  ///Euler iterator for undirected graphs.
116
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).
120  ///
121  ///For example
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.
126  ///\code
127  ///  for(UndirEulerIt<UndirListGraph> e(g),e!=INVALID;++e) {
128  ///    std::cout << g.id(UndirEdge(e)) << std::eol;
129  ///  }
130  ///\endcode
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).
134  ///
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>
138  class UndirEulerIt
139  {
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;
146   
147    const Graph &g;
148    typename Graph::NodeMap<OutEdgeIt> nedge;
149    typename Graph::UndirEdgeMap<bool> visited;
150    std::list<Edge> euler;
151
152  public:
153   
154    ///Constructor
155
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)
161    {
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]);
167        ++nedge[start];
168        start=next;     while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
169      }
170    }
171   
172    ///Edge Conversion
173    operator Edge() { return euler.empty()?INVALID:euler.front(); }
174    bool operator==(Invalid) { return euler.empty(); }
175    bool operator!=(Invalid) { return !euler.empty(); }
176   
177    ///Next edge of the tour
178    UndirEulerIt &operator++() {
179      Node s=g.target(euler.front());
180      euler.pop_front();
181      typename std::list<Edge>::iterator next=euler.begin();
182
183      while(nedge[s]!=INVALID) {
184        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
185        if(nedge[s]==INVALID) break;
186        else {
187          euler.insert(next,nedge[s]);
188          Node n=g.target(nedge[s]);
189          ++nedge[s];
190          s=n;
191        }
192      }
193      return *this;
194    }
195   
196    ///Postfix incrementation
197   
198    ///\warning This incrementation
199    ///returns an \c Edge, not an \ref UndirEulerIt, as one may
200    ///expect.
201    Edge operator++(int)
202    {
203      Edge e=*this;
204      ++(*this);
205      return e;
206    }
207  };
208
209
210  ///Checks if the graph is Euler
211
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>
224#ifdef DOXYGEN
225  bool
226#else
227  typename enable_if<typename Graph::UndirTag,bool>::type
228  euler(const Graph &g)
229  {
230    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
231      if(countIncEdges(g,n)%2) return false;
232    return connected(g);
233  }
234  template<class Graph>
235  typename disable_if<typename Graph::UndirTag,bool>::type
236#endif
237  euler(const Graph &g)
238  {
239    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
240      if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
241    return connected(g);
242  }
243 
244}
Note: See TracBrowser for help on using the repository browser.