COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/euler.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

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