lemon/euler.h
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 23 Feb 2009 11:30:15 +0000
changeset 567 42d4b889903a
child 568 3af83b6be1df
permissions -rw-r--r--
Port Euler walk tools from SVN -r3512 (#65)
     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_prop
    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_prop
    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   ///\todo Test required
    58   template<class Digraph>
    59   class DiEulerIt
    60   {
    61     typedef typename Digraph::Node Node;
    62     typedef typename Digraph::NodeIt NodeIt;
    63     typedef typename Digraph::Arc Arc;
    64     typedef typename Digraph::ArcIt ArcIt;
    65     typedef typename Digraph::OutArcIt OutArcIt;
    66     typedef typename Digraph::InArcIt InArcIt;
    67 
    68     const Digraph &g;
    69     typename Digraph::template NodeMap<OutArcIt> nedge;
    70     std::list<Arc> euler;
    71 
    72   public:
    73 
    74     ///Constructor
    75 
    76     ///\param _g A digraph.
    77     ///\param start The starting point of the tour. If it is not given
    78     ///       the tour will start from the first node.
    79     DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
    80       : g(_g), nedge(g)
    81     {
    82       if(start==INVALID) start=NodeIt(g);
    83       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
    84       while(nedge[start]!=INVALID) {
    85         euler.push_back(nedge[start]);
    86         Node next=g.target(nedge[start]);
    87         ++nedge[start];
    88         start=next;
    89       }
    90     }
    91 
    92     ///Arc Conversion
    93     operator Arc() { return euler.empty()?INVALID:euler.front(); }
    94     bool operator==(Invalid) { return euler.empty(); }
    95     bool operator!=(Invalid) { return !euler.empty(); }
    96 
    97     ///Next arc of the tour
    98     DiEulerIt &operator++() {
    99       Node s=g.target(euler.front());
   100       euler.pop_front();
   101       //This produces a warning.Strange.
   102       //std::list<Arc>::iterator next=euler.begin();
   103       typename std::list<Arc>::iterator next=euler.begin();
   104       while(nedge[s]!=INVALID) {
   105         euler.insert(next,nedge[s]);
   106         Node n=g.target(nedge[s]);
   107         ++nedge[s];
   108         s=n;
   109       }
   110       return *this;
   111     }
   112     ///Postfix incrementation
   113 
   114     ///\warning This incrementation
   115     ///returns an \c Arc, not an \ref DiEulerIt, as one may
   116     ///expect.
   117     Arc operator++(int)
   118     {
   119       Arc e=*this;
   120       ++(*this);
   121       return e;
   122     }
   123   };
   124 
   125   ///Euler iterator for graphs.
   126 
   127   /// \ingroup graph_prop
   128   ///This iterator converts to the \c Arc (or \c Edge)
   129   ///type of the digraph and using
   130   ///operator ++, it provides an Euler tour of an undirected
   131   ///digraph (if there exists).
   132   ///
   133   ///For example
   134   ///if the given digraph if Euler (i.e it has only one nontrivial component
   135   ///and the degree of each node is even),
   136   ///the following code will print the arc IDs according to an
   137   ///Euler tour of \c g.
   138   ///\code
   139   ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
   140   ///    std::cout << g.id(Edge(e)) << std::eol;
   141   ///  }
   142   ///\endcode
   143   ///Although the iterator provides an Euler tour of an graph,
   144   ///it still returns Arcs in order to indicate the direction of the tour.
   145   ///(But Arc will convert to Edges, of course).
   146   ///
   147   ///If \c g is not Euler then the resulted tour will not be full or closed.
   148   ///\sa EulerIt
   149   ///\todo Test required
   150   template<class Digraph>
   151   class EulerIt
   152   {
   153     typedef typename Digraph::Node Node;
   154     typedef typename Digraph::NodeIt NodeIt;
   155     typedef typename Digraph::Arc Arc;
   156     typedef typename Digraph::Edge Edge;
   157     typedef typename Digraph::ArcIt ArcIt;
   158     typedef typename Digraph::OutArcIt OutArcIt;
   159     typedef typename Digraph::InArcIt InArcIt;
   160 
   161     const Digraph &g;
   162     typename Digraph::template NodeMap<OutArcIt> nedge;
   163     typename Digraph::template EdgeMap<bool> visited;
   164     std::list<Arc> euler;
   165 
   166   public:
   167 
   168     ///Constructor
   169 
   170     ///\param _g An graph.
   171     ///\param start The starting point of the tour. If it is not given
   172     ///       the tour will start from the first node.
   173     EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
   174       : g(_g), nedge(g), visited(g,false)
   175     {
   176       if(start==INVALID) start=NodeIt(g);
   177       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
   178       while(nedge[start]!=INVALID) {
   179         euler.push_back(nedge[start]);
   180         visited[nedge[start]]=true;
   181         Node next=g.target(nedge[start]);
   182         ++nedge[start];
   183         start=next;
   184         while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
   185       }
   186     }
   187 
   188     ///Arc Conversion
   189     operator Arc() const { return euler.empty()?INVALID:euler.front(); }
   190     ///Arc Conversion
   191     operator Edge() const { return euler.empty()?INVALID:euler.front(); }
   192     ///\e
   193     bool operator==(Invalid) const { return euler.empty(); }
   194     ///\e
   195     bool operator!=(Invalid) const { return !euler.empty(); }
   196 
   197     ///Next arc of the tour
   198     EulerIt &operator++() {
   199       Node s=g.target(euler.front());
   200       euler.pop_front();
   201       typename std::list<Arc>::iterator next=euler.begin();
   202 
   203       while(nedge[s]!=INVALID) {
   204         while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
   205         if(nedge[s]==INVALID) break;
   206         else {
   207           euler.insert(next,nedge[s]);
   208           visited[nedge[s]]=true;
   209           Node n=g.target(nedge[s]);
   210           ++nedge[s];
   211           s=n;
   212         }
   213       }
   214       return *this;
   215     }
   216 
   217     ///Postfix incrementation
   218 
   219     ///\warning This incrementation
   220     ///returns an \c Arc, not an \ref EulerIt, as one may
   221     ///expect.
   222     Arc operator++(int)
   223     {
   224       Arc e=*this;
   225       ++(*this);
   226       return e;
   227     }
   228   };
   229 
   230 
   231   ///Checks if the graph is Euler
   232 
   233   /// \ingroup graph_prop
   234   ///Checks if the graph is Euler. It works for both directed and undirected
   235   ///graphs.
   236   ///\note By definition, a digraph is called \e Euler if
   237   ///and only if it is connected and the number of its incoming and outgoing
   238   ///arcs are the same for each node.
   239   ///Similarly, an undirected graph is called \e Euler if
   240   ///and only if it is connected and the number of incident arcs is even
   241   ///for each node. <em>Therefore, there are digraphs which are not Euler, but
   242   ///still have an Euler tour</em>.
   243   ///\todo Test required
   244   template<class Digraph>
   245 #ifdef DOXYGEN
   246   bool
   247 #else
   248   typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
   249   euler(const Digraph &g)
   250   {
   251     for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
   252       if(countIncEdges(g,n)%2) return false;
   253     return connected(g);
   254   }
   255   template<class Digraph>
   256   typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
   257 #endif
   258   euler(const Digraph &g)
   259   {
   260     for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
   261       if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
   262     return connected(Undirector<const Digraph>(g));
   263   }
   264 
   265 }
   266 
   267 #endif