COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/euler.h @ 2529:93de38566e6c

Last change on this file since 2529:93de38566e6c was 2445:aaf5787f4d5d, checked in by Alpar Juttner, 13 years ago
  • Fix a serious bug in UEulerIt
  • Add a conversion to UEdge
  • Make some member funtions to be 'const'
File size: 7.6 KB
RevLine 
[1738]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
[2391]5 * Copyright (C) 2003-2007
[1956]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1738]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 */
[1956]18
[1993]19#include<lemon/bits/invalid.h>
[1818]20#include<lemon/topology.h>
[1738]21#include <list>
22
[2429]23/// \ingroup graph_prop
[1738]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
[1818]33  ///Euler iterator for directed graphs.
[1738]34
[2429]35  /// \ingroup graph_prop
[1738]36  ///This iterator converts to the \c Edge type of the graph and using
[1970]37  ///operator ++ it provides an Euler tour of a \e directed
38  ///graph (if there exists).
[1738]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),
[1970]43  ///the following code will put the edges of \c g
44  ///to the vector \c et according to an
[1738]45  ///Euler tour of \c g.
46  ///\code
[1970]47  ///  std::vector<ListGraph::Edge> et;
48  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e)
49  ///    et.push_back(e);
[1738]50  ///\endcode
51  ///If \c g is not Euler then the resulted tour will not be full or closed.
[1970]52  ///\sa UEulerIt
[1738]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;
[2405]65    typename Graph::template NodeMap<OutEdgeIt> nedge;
[1738]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
[1803]74    ///       the tour will start from the first node.
[1738]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   
[1803]110    ///\warning This incrementation
111    ///returns an \c Edge, not an \ref EulerIt, as one may
112    ///expect.
[1738]113    Edge operator++(int)
114    {
115      Edge e=*this;
116      ++(*this);
117      return e;
118    }
119  };
120
[1818]121  ///Euler iterator for undirected graphs.
122
[2429]123  /// \ingroup graph_prop
[2350]124  ///This iterator converts to the \c Edge (or \c UEdge)
[1970]125  ///type of the graph and using
[2350]126  ///operator ++ it provides an Euler tour of an undirected
[1970]127  ///graph (if there exists).
[1818]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
[1909]135  ///  for(UEulerIt<ListUGraph> e(g),e!=INVALID;++e) {
136  ///    std::cout << g.id(UEdge(e)) << std::eol;
[1818]137  ///  }
138  ///\endcode
139  ///Although the iterator provides an Euler tour of an undirected graph,
[1909]140  ///in order to indicate the direction of the tour, UEulerIt
[1818]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.
[1970]144  ///\sa EulerIt
[1818]145  ///\todo Test required
146  template<class Graph>
[1909]147  class UEulerIt
[1818]148  {
149    typedef typename Graph::Node Node;
150    typedef typename Graph::NodeIt NodeIt;
151    typedef typename Graph::Edge Edge;
[2445]152    typedef typename Graph::UEdge UEdge;
[1818]153    typedef typename Graph::EdgeIt EdgeIt;
154    typedef typename Graph::OutEdgeIt OutEdgeIt;
155    typedef typename Graph::InEdgeIt InEdgeIt;
156   
157    const Graph &g;
[2405]158    typename Graph::template NodeMap<OutEdgeIt> nedge;
159    typename Graph::template UEdgeMap<bool> visited;
[1818]160    std::list<Edge> euler;
161
162  public:
163   
164    ///Constructor
165
166    ///\param _g An undirected graph.
167    ///\param start The starting point of the tour. If it is not given
168    ///       the tour will start from the first node.
[1909]169    UEulerIt(const Graph &_g,typename Graph::Node start=INVALID)
[1818]170      : g(_g), nedge(g), visited(g,false)
171    {
172      if(start==INVALID) start=NodeIt(g);
173      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
174      while(nedge[start]!=INVALID) {
175        euler.push_back(nedge[start]);
[2445]176        visited[nedge[start]]=true;
[1818]177        Node next=g.target(nedge[start]);
178        ++nedge[start];
[2445]179        start=next;
180        while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
[1818]181      }
182    }
183   
184    ///Edge Conversion
[2445]185    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
186    ///Edge Conversion
187    operator UEdge() const { return euler.empty()?INVALID:euler.front(); }
188    ///\e
189    bool operator==(Invalid) const { return euler.empty(); }
190    ///\e
191    bool operator!=(Invalid) const { return !euler.empty(); }
[1818]192   
193    ///Next edge of the tour
[1909]194    UEulerIt &operator++() {
[1818]195      Node s=g.target(euler.front());
196      euler.pop_front();
197      typename std::list<Edge>::iterator next=euler.begin();
198
199      while(nedge[s]!=INVALID) {
200        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
201        if(nedge[s]==INVALID) break;
202        else {
203          euler.insert(next,nedge[s]);
[2445]204          visited[nedge[s]]=true;
[1818]205          Node n=g.target(nedge[s]);
206          ++nedge[s];
207          s=n;
208        }
209      }
210      return *this;
211    }
212   
213    ///Postfix incrementation
214   
215    ///\warning This incrementation
[1909]216    ///returns an \c Edge, not an \ref UEulerIt, as one may
[1818]217    ///expect.
218    Edge operator++(int)
219    {
220      Edge e=*this;
221      ++(*this);
222      return e;
223    }
224  };
225
226
[1738]227  ///Checks if the graph is Euler
228
[2429]229  /// \ingroup graph_prop
[1738]230  ///Checks if the graph is Euler. It works for both directed and
231  ///undirected graphs.
[1818]232  ///\note By definition, a directed graph is called \e Euler if
233  ///and only if connected and the number of it is incoming and outgoing edges
234  ///are the same for each node.
235  ///Similarly, an undirected graph is called \e Euler if
236  ///and only if it is connected and the number of incident edges is even
237  ///for each node. <em>Therefore, there are graphs which are not Euler, but
238  ///still have an Euler tour</em>.
[1738]239  ///\todo Test required
240  template<class Graph>
241#ifdef DOXYGEN
242  bool
243#else
[1979]244  typename enable_if<UndirectedTagIndicator<Graph>,bool>::type
[1818]245  euler(const Graph &g)
246  {
247    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
248      if(countIncEdges(g,n)%2) return false;
249    return connected(g);
250  }
251  template<class Graph>
[1979]252  typename disable_if<UndirectedTagIndicator<Graph>,bool>::type
[1738]253#endif
254  euler(const Graph &g)
255  {
256    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
257      if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
[1818]258    return connected(g);
[1738]259  }
260 
261}
Note: See TracBrowser for help on using the repository browser.