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