COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/euler.h @ 877:141f9c0db4a3

Last change on this file since 877:141f9c0db4a3 was 877:141f9c0db4a3, checked in by Alpar Juttner <alpar@…>, 14 years ago

Unify the sources (#339)

File size: 8.3 KB
RevLine 
[520]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
[877]5 * Copyright (C) 2003-2010
[520]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
[586]27/// \ingroup graph_properties
[520]28/// \file
[877]29/// \brief Euler tour iterators and a function for checking the \e Eulerian
[592]30/// property.
[520]31///
[592]32///This file provides Euler tour iterators and a function to check
33///if a (di)graph is \e Eulerian.
[520]34
35namespace lemon {
36
[592]37  ///Euler tour iterator for digraphs.
[520]38
[592]39  /// \ingroup graph_prop
40  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
41  ///graph (if there exists) and it converts to the \c Arc type of the digraph.
[520]42  ///
[592]43  ///For example, if the given digraph has an Euler tour (i.e it has only one
[877]44  ///non-trivial component and the in-degree is equal to the out-degree
[592]45  ///for all nodes), then the following code will put the arcs of \c g
46  ///to the vector \c et according to an Euler tour of \c g.
[520]47  ///\code
48  ///  std::vector<ListDigraph::Arc> et;
[592]49  ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
[520]50  ///    et.push_back(e);
51  ///\endcode
[592]52  ///If \c g has no Euler tour, then the resulted walk will not be closed
53  ///or not contain all arcs.
[520]54  ///\sa EulerIt
[559]55  template<typename GR>
[520]56  class DiEulerIt
57  {
[559]58    typedef typename GR::Node Node;
59    typedef typename GR::NodeIt NodeIt;
60    typedef typename GR::Arc Arc;
61    typedef typename GR::ArcIt ArcIt;
62    typedef typename GR::OutArcIt OutArcIt;
63    typedef typename GR::InArcIt InArcIt;
[520]64
[559]65    const GR &g;
[592]66    typename GR::template NodeMap<OutArcIt> narc;
[520]67    std::list<Arc> euler;
68
69  public:
70
71    ///Constructor
72
[592]73    ///Constructor.
[559]74    ///\param gr A digraph.
[592]75    ///\param start The starting point of the tour. If it is not given,
76    ///the tour will start from the first node that has an outgoing arc.
[559]77    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
[592]78      : g(gr), narc(g)
[520]79    {
[591]80      if (start==INVALID) {
81        NodeIt n(g);
82        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
83        start=n;
84      }
85      if (start!=INVALID) {
[592]86        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
87        while (narc[start]!=INVALID) {
88          euler.push_back(narc[start]);
89          Node next=g.target(narc[start]);
90          ++narc[start];
[591]91          start=next;
92        }
[520]93      }
94    }
95
[592]96    ///Arc conversion
[520]97    operator Arc() { return euler.empty()?INVALID:euler.front(); }
[592]98    ///Compare with \c INVALID
[520]99    bool operator==(Invalid) { return euler.empty(); }
[592]100    ///Compare with \c INVALID
[520]101    bool operator!=(Invalid) { return !euler.empty(); }
102
103    ///Next arc of the tour
[592]104
105    ///Next arc of the tour
106    ///
[520]107    DiEulerIt &operator++() {
108      Node s=g.target(euler.front());
109      euler.pop_front();
110      typename std::list<Arc>::iterator next=euler.begin();
[592]111      while(narc[s]!=INVALID) {
112        euler.insert(next,narc[s]);
113        Node n=g.target(narc[s]);
114        ++narc[s];
[520]115        s=n;
116      }
117      return *this;
118    }
119    ///Postfix incrementation
120
[592]121    /// Postfix incrementation.
122    ///
[520]123    ///\warning This incrementation
[592]124    ///returns an \c Arc, not a \ref DiEulerIt, as one may
[520]125    ///expect.
126    Arc operator++(int)
127    {
128      Arc e=*this;
129      ++(*this);
130      return e;
131    }
132  };
133
[592]134  ///Euler tour iterator for graphs.
[520]135
[586]136  /// \ingroup graph_properties
[592]137  ///This iterator provides an Euler tour (Eulerian circuit) of an
138  ///\e undirected graph (if there exists) and it converts to the \c Arc
139  ///and \c Edge types of the graph.
[520]140  ///
[877]141  ///For example, if the given graph has an Euler tour (i.e it has only one
[592]142  ///non-trivial component and the degree of each node is even),
[520]143  ///the following code will print the arc IDs according to an
144  ///Euler tour of \c g.
145  ///\code
[592]146  ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
[520]147  ///    std::cout << g.id(Edge(e)) << std::eol;
148  ///  }
149  ///\endcode
[877]150  ///Although this iterator is for undirected graphs, it still returns
[592]151  ///arcs in order to indicate the direction of the tour.
152  ///(But arcs convert to edges, of course.)
[520]153  ///
[592]154  ///If \c g has no Euler tour, then the resulted walk will not be closed
155  ///or not contain all edges.
[559]156  template<typename GR>
[520]157  class EulerIt
158  {
[559]159    typedef typename GR::Node Node;
160    typedef typename GR::NodeIt NodeIt;
161    typedef typename GR::Arc Arc;
162    typedef typename GR::Edge Edge;
163    typedef typename GR::ArcIt ArcIt;
164    typedef typename GR::OutArcIt OutArcIt;
165    typedef typename GR::InArcIt InArcIt;
[520]166
[559]167    const GR &g;
[592]168    typename GR::template NodeMap<OutArcIt> narc;
[559]169    typename GR::template EdgeMap<bool> visited;
[520]170    std::list<Arc> euler;
171
172  public:
173
174    ///Constructor
175
[592]176    ///Constructor.
177    ///\param gr A graph.
178    ///\param start The starting point of the tour. If it is not given,
179    ///the tour will start from the first node that has an incident edge.
[559]180    EulerIt(const GR &gr, typename GR::Node start = INVALID)
[592]181      : g(gr), narc(g), visited(g, false)
[520]182    {
[591]183      if (start==INVALID) {
184        NodeIt n(g);
185        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
186        start=n;
187      }
188      if (start!=INVALID) {
[592]189        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
190        while(narc[start]!=INVALID) {
191          euler.push_back(narc[start]);
192          visited[narc[start]]=true;
193          Node next=g.target(narc[start]);
194          ++narc[start];
[591]195          start=next;
[592]196          while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
[591]197        }
[520]198      }
199    }
200
[592]201    ///Arc conversion
[520]202    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
[592]203    ///Edge conversion
[520]204    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
[592]205    ///Compare with \c INVALID
[520]206    bool operator==(Invalid) const { return euler.empty(); }
[592]207    ///Compare with \c INVALID
[520]208    bool operator!=(Invalid) const { return !euler.empty(); }
209
210    ///Next arc of the tour
[592]211
212    ///Next arc of the tour
213    ///
[520]214    EulerIt &operator++() {
215      Node s=g.target(euler.front());
216      euler.pop_front();
217      typename std::list<Arc>::iterator next=euler.begin();
[592]218      while(narc[s]!=INVALID) {
219        while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
220        if(narc[s]==INVALID) break;
[520]221        else {
[592]222          euler.insert(next,narc[s]);
223          visited[narc[s]]=true;
224          Node n=g.target(narc[s]);
225          ++narc[s];
[520]226          s=n;
227        }
228      }
229      return *this;
230    }
231
232    ///Postfix incrementation
233
[592]234    /// Postfix incrementation.
235    ///
[877]236    ///\warning This incrementation returns an \c Arc (which converts to
[592]237    ///an \c Edge), not an \ref EulerIt, as one may expect.
[520]238    Arc operator++(int)
239    {
240      Arc e=*this;
241      ++(*this);
242      return e;
243    }
244  };
245
246
[648]247  ///Check if the given graph is Eulerian
[520]248
[586]249  /// \ingroup graph_properties
[648]250  ///This function checks if the given graph is Eulerian.
[592]251  ///It works for both directed and undirected graphs.
252  ///
253  ///By definition, a digraph is called \e Eulerian if
254  ///and only if it is connected and the number of incoming and outgoing
[520]255  ///arcs are the same for each node.
[521]256  ///Similarly, an undirected graph is called \e Eulerian if
[592]257  ///and only if it is connected and the number of incident edges is even
258  ///for each node.
259  ///
260  ///\note There are (di)graphs that are not Eulerian, but still have an
261  /// Euler tour, since they may contain isolated nodes.
262  ///
263  ///\sa DiEulerIt, EulerIt
[559]264  template<typename GR>
[520]265#ifdef DOXYGEN
266  bool
267#else
[559]268  typename enable_if<UndirectedTagIndicator<GR>,bool>::type
269  eulerian(const GR &g)
[520]270  {
[559]271    for(typename GR::NodeIt n(g);n!=INVALID;++n)
[520]272      if(countIncEdges(g,n)%2) return false;
273    return connected(g);
274  }
[559]275  template<class GR>
276  typename disable_if<UndirectedTagIndicator<GR>,bool>::type
[520]277#endif
[559]278  eulerian(const GR &g)
[520]279  {
[559]280    for(typename GR::NodeIt n(g);n!=INVALID;++n)
[520]281      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
[592]282    return connected(undirector(g));
[520]283  }
284
285}
286
287#endif
Note: See TracBrowser for help on using the repository browser.