lemon/euler.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:17:34 +0100
changeset 805 d3e32a777d0b
parent 592 2ebfdb89ec66
child 877 141f9c0db4a3
permissions -rw-r--r--
Port CapacityScaling from SVN -r3524 (#180)
     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 iterators and a function for checking the \e Eulerian 
    30 /// property.
    31 ///
    32 ///This file provides Euler tour iterators and a function to check
    33 ///if a (di)graph is \e Eulerian.
    34 
    35 namespace lemon {
    36 
    37   ///Euler tour iterator for digraphs.
    38 
    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.
    42   ///
    43   ///For example, if the given digraph has an Euler tour (i.e it has only one
    44   ///non-trivial component and the in-degree is equal to the out-degree 
    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.
    47   ///\code
    48   ///  std::vector<ListDigraph::Arc> et;
    49   ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
    50   ///    et.push_back(e);
    51   ///\endcode
    52   ///If \c g has no Euler tour, then the resulted walk will not be closed
    53   ///or not contain all arcs.
    54   ///\sa EulerIt
    55   template<typename GR>
    56   class DiEulerIt
    57   {
    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;
    64 
    65     const GR &g;
    66     typename GR::template NodeMap<OutArcIt> narc;
    67     std::list<Arc> euler;
    68 
    69   public:
    70 
    71     ///Constructor
    72 
    73     ///Constructor.
    74     ///\param gr A digraph.
    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.
    77     DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
    78       : g(gr), narc(g)
    79     {
    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) {
    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];
    91           start=next;
    92         }
    93       }
    94     }
    95 
    96     ///Arc conversion
    97     operator Arc() { return euler.empty()?INVALID:euler.front(); }
    98     ///Compare with \c INVALID
    99     bool operator==(Invalid) { return euler.empty(); }
   100     ///Compare with \c INVALID
   101     bool operator!=(Invalid) { return !euler.empty(); }
   102 
   103     ///Next arc of the tour
   104 
   105     ///Next arc of the tour
   106     ///
   107     DiEulerIt &operator++() {
   108       Node s=g.target(euler.front());
   109       euler.pop_front();
   110       typename std::list<Arc>::iterator next=euler.begin();
   111       while(narc[s]!=INVALID) {
   112         euler.insert(next,narc[s]);
   113         Node n=g.target(narc[s]);
   114         ++narc[s];
   115         s=n;
   116       }
   117       return *this;
   118     }
   119     ///Postfix incrementation
   120 
   121     /// Postfix incrementation.
   122     ///
   123     ///\warning This incrementation
   124     ///returns an \c Arc, not a \ref DiEulerIt, as one may
   125     ///expect.
   126     Arc operator++(int)
   127     {
   128       Arc e=*this;
   129       ++(*this);
   130       return e;
   131     }
   132   };
   133 
   134   ///Euler tour iterator for graphs.
   135 
   136   /// \ingroup graph_properties
   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.
   140   ///
   141   ///For example, if the given graph has an Euler tour (i.e it has only one 
   142   ///non-trivial component and the degree of each node is even),
   143   ///the following code will print the arc IDs according to an
   144   ///Euler tour of \c g.
   145   ///\code
   146   ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
   147   ///    std::cout << g.id(Edge(e)) << std::eol;
   148   ///  }
   149   ///\endcode
   150   ///Although this iterator is for undirected graphs, it still returns 
   151   ///arcs in order to indicate the direction of the tour.
   152   ///(But arcs convert to edges, of course.)
   153   ///
   154   ///If \c g has no Euler tour, then the resulted walk will not be closed
   155   ///or not contain all edges.
   156   template<typename GR>
   157   class EulerIt
   158   {
   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;
   166 
   167     const GR &g;
   168     typename GR::template NodeMap<OutArcIt> narc;
   169     typename GR::template EdgeMap<bool> visited;
   170     std::list<Arc> euler;
   171 
   172   public:
   173 
   174     ///Constructor
   175 
   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.
   180     EulerIt(const GR &gr, typename GR::Node start = INVALID)
   181       : g(gr), narc(g), visited(g, false)
   182     {
   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) {
   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];
   195           start=next;
   196           while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
   197         }
   198       }
   199     }
   200 
   201     ///Arc conversion
   202     operator Arc() const { return euler.empty()?INVALID:euler.front(); }
   203     ///Edge conversion
   204     operator Edge() const { return euler.empty()?INVALID:euler.front(); }
   205     ///Compare with \c INVALID
   206     bool operator==(Invalid) const { return euler.empty(); }
   207     ///Compare with \c INVALID
   208     bool operator!=(Invalid) const { return !euler.empty(); }
   209 
   210     ///Next arc of the tour
   211 
   212     ///Next arc of the tour
   213     ///
   214     EulerIt &operator++() {
   215       Node s=g.target(euler.front());
   216       euler.pop_front();
   217       typename std::list<Arc>::iterator next=euler.begin();
   218       while(narc[s]!=INVALID) {
   219         while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
   220         if(narc[s]==INVALID) break;
   221         else {
   222           euler.insert(next,narc[s]);
   223           visited[narc[s]]=true;
   224           Node n=g.target(narc[s]);
   225           ++narc[s];
   226           s=n;
   227         }
   228       }
   229       return *this;
   230     }
   231 
   232     ///Postfix incrementation
   233 
   234     /// Postfix incrementation.
   235     ///
   236     ///\warning This incrementation returns an \c Arc (which converts to 
   237     ///an \c Edge), not an \ref EulerIt, as one may expect.
   238     Arc operator++(int)
   239     {
   240       Arc e=*this;
   241       ++(*this);
   242       return e;
   243     }
   244   };
   245 
   246 
   247   ///Check if the given graph is Eulerian
   248 
   249   /// \ingroup graph_properties
   250   ///This function checks if the given graph is Eulerian.
   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
   255   ///arcs are the same for each node.
   256   ///Similarly, an undirected graph is called \e Eulerian if
   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
   264   template<typename GR>
   265 #ifdef DOXYGEN
   266   bool
   267 #else
   268   typename enable_if<UndirectedTagIndicator<GR>,bool>::type
   269   eulerian(const GR &g)
   270   {
   271     for(typename GR::NodeIt n(g);n!=INVALID;++n)
   272       if(countIncEdges(g,n)%2) return false;
   273     return connected(g);
   274   }
   275   template<class GR>
   276   typename disable_if<UndirectedTagIndicator<GR>,bool>::type
   277 #endif
   278   eulerian(const GR &g)
   279   {
   280     for(typename GR::NodeIt n(g);n!=INVALID;++n)
   281       if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
   282     return connected(undirector(g));
   283   }
   284 
   285 }
   286 
   287 #endif