COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/euler.h @ 2229:4dbb6dd2dd4b

Last change on this file since 2229:4dbb6dd2dd4b was 1993:2115143eceea, checked in by Balazs Dezso, 18 years ago

utility, invalid and traits moved to bits

File size: 7.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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#include<lemon/bits/invalid.h>
20#include<lemon/topology.h>
21#include <list>
22
23/// \ingroup topology
24/// \file
25/// \brief Euler tour
26///
27///This file provides an Euler tour iterator and ways to check
28///if a graph is euler.
29
30
31namespace lemon {
32
33  ///Euler iterator for directed graphs.
34
35  /// \ingroup topology
36  ///This iterator converts to the \c Edge type of the graph and using
37  ///operator ++ it provides an Euler tour of a \e directed
38  ///graph (if there exists).
39  ///
40  ///For example
41  ///if the given graph if Euler (i.e it has only one nontrivial component
42  ///and the in-degree is equal to the out-degree for all nodes),
43  ///the following code will put the edges of \c g
44  ///to the vector \c et according to an
45  ///Euler tour of \c g.
46  ///\code
47  ///  std::vector<ListGraph::Edge> et;
48  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e)
49  ///    et.push_back(e);
50  ///\endcode
51  ///If \c g is not Euler then the resulted tour will not be full or closed.
52  ///\sa UEulerIt
53  ///\todo Test required
54  template<class Graph>
55  class EulerIt
56  {
57    typedef typename Graph::Node Node;
58    typedef typename Graph::NodeIt NodeIt;
59    typedef typename Graph::Edge Edge;
60    typedef typename Graph::EdgeIt EdgeIt;
61    typedef typename Graph::OutEdgeIt OutEdgeIt;
62    typedef typename Graph::InEdgeIt InEdgeIt;
63   
64    const Graph &g;
65    typename Graph::NodeMap<OutEdgeIt> nedge;
66    std::list<Edge> euler;
67
68  public:
69   
70    ///Constructor
71
72    ///\param _g A directed graph.
73    ///\param start The starting point of the tour. If it is not given
74    ///       the tour will start from the first node.
75    EulerIt(const Graph &_g,typename Graph::Node start=INVALID)
76      : g(_g), nedge(g)
77    {
78      if(start==INVALID) start=NodeIt(g);
79      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
80      while(nedge[start]!=INVALID) {
81        euler.push_back(nedge[start]);
82        Node next=g.target(nedge[start]);
83        ++nedge[start];
84        start=next;
85      }
86    }
87   
88    ///Edge Conversion
89    operator Edge() { return euler.empty()?INVALID:euler.front(); }
90    bool operator==(Invalid) { return euler.empty(); }
91    bool operator!=(Invalid) { return !euler.empty(); }
92   
93    ///Next edge of the tour
94    EulerIt &operator++() {
95      Node s=g.target(euler.front());
96      euler.pop_front();
97      //This produces a warning.Strange.
98      //std::list<Edge>::iterator next=euler.begin();
99      typename std::list<Edge>::iterator next=euler.begin();
100      while(nedge[s]!=INVALID) {
101        euler.insert(next,nedge[s]);
102        Node n=g.target(nedge[s]);
103        ++nedge[s];
104        s=n;
105      }
106      return *this;
107    }
108    ///Postfix incrementation
109   
110    ///\warning This incrementation
111    ///returns an \c Edge, not an \ref EulerIt, as one may
112    ///expect.
113    Edge operator++(int)
114    {
115      Edge e=*this;
116      ++(*this);
117      return e;
118    }
119  };
120
121  ///Euler iterator for undirected graphs.
122
123  /// \ingroup topology
124  ///This iterator converts to the \c Edge (or \cUEdge)
125  ///type of the graph and using
126  ///operator ++ it provides an Euler tour of an \undirected
127  ///graph (if there exists).
128  ///
129  ///For example
130  ///if the given graph if Euler (i.e it has only one nontrivial component
131  ///and the degree of each node is even),
132  ///the following code will print the edge IDs according to an
133  ///Euler tour of \c g.
134  ///\code
135  ///  for(UEulerIt<ListUGraph> e(g),e!=INVALID;++e) {
136  ///    std::cout << g.id(UEdge(e)) << std::eol;
137  ///  }
138  ///\endcode
139  ///Although the iterator provides an Euler tour of an undirected graph,
140  ///in order to indicate the direction of the tour, UEulerIt
141  ///returns directed edges (that convert to the undirected ones, of course).
142  ///
143  ///If \c g is not Euler then the resulted tour will not be full or closed.
144  ///\sa EulerIt
145  ///\todo Test required
146  template<class Graph>
147  class UEulerIt
148  {
149    typedef typename Graph::Node Node;
150    typedef typename Graph::NodeIt NodeIt;
151    typedef typename Graph::Edge Edge;
152    typedef typename Graph::EdgeIt EdgeIt;
153    typedef typename Graph::OutEdgeIt OutEdgeIt;
154    typedef typename Graph::InEdgeIt InEdgeIt;
155   
156    const Graph &g;
157    typename Graph::NodeMap<OutEdgeIt> nedge;
158    typename Graph::UEdgeMap<bool> visited;
159    std::list<Edge> euler;
160
161  public:
162   
163    ///Constructor
164
165    ///\param _g An undirected graph.
166    ///\param start The starting point of the tour. If it is not given
167    ///       the tour will start from the first node.
168    UEulerIt(const Graph &_g,typename Graph::Node start=INVALID)
169      : g(_g), nedge(g), visited(g,false)
170    {
171      if(start==INVALID) start=NodeIt(g);
172      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
173      while(nedge[start]!=INVALID) {
174        euler.push_back(nedge[start]);
175        Node next=g.target(nedge[start]);
176        ++nedge[start];
177        start=next;     while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
178      }
179    }
180   
181    ///Edge Conversion
182    operator Edge() { return euler.empty()?INVALID:euler.front(); }
183    bool operator==(Invalid) { return euler.empty(); }
184    bool operator!=(Invalid) { return !euler.empty(); }
185   
186    ///Next edge of the tour
187    UEulerIt &operator++() {
188      Node s=g.target(euler.front());
189      euler.pop_front();
190      typename std::list<Edge>::iterator next=euler.begin();
191
192      while(nedge[s]!=INVALID) {
193        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
194        if(nedge[s]==INVALID) break;
195        else {
196          euler.insert(next,nedge[s]);
197          Node n=g.target(nedge[s]);
198          ++nedge[s];
199          s=n;
200        }
201      }
202      return *this;
203    }
204   
205    ///Postfix incrementation
206   
207    ///\warning This incrementation
208    ///returns an \c Edge, not an \ref UEulerIt, as one may
209    ///expect.
210    Edge operator++(int)
211    {
212      Edge e=*this;
213      ++(*this);
214      return e;
215    }
216  };
217
218
219  ///Checks if the graph is Euler
220
221  /// \ingroup topology
222  ///Checks if the graph is Euler. It works for both directed and
223  ///undirected graphs.
224  ///\note By definition, a directed graph is called \e Euler if
225  ///and only if connected and the number of it is incoming and outgoing edges
226  ///are the same for each node.
227  ///Similarly, an undirected graph is called \e Euler if
228  ///and only if it is connected and the number of incident edges is even
229  ///for each node. <em>Therefore, there are graphs which are not Euler, but
230  ///still have an Euler tour</em>.
231  ///\todo Test required
232  template<class Graph>
233#ifdef DOXYGEN
234  bool
235#else
236  typename enable_if<UndirectedTagIndicator<Graph>,bool>::type
237  euler(const Graph &g)
238  {
239    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
240      if(countIncEdges(g,n)%2) return false;
241    return connected(g);
242  }
243  template<class Graph>
244  typename disable_if<UndirectedTagIndicator<Graph>,bool>::type
245#endif
246  euler(const Graph &g)
247  {
248    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
249      if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
250    return connected(g);
251  }
252 
253}
Note: See TracBrowser for help on using the repository browser.