lemon/euler.h
 author Peter Kovacs Wed, 15 Apr 2009 11:47:19 +0200 changeset 639 2ebfdb89ec66 parent 638 493533ead9df child 695 4ff8041e9c2e permissions -rw-r--r--
Improvements for the Euler tools and the test file (#264)
     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 \e Eulerian

   248

   249   /// \ingroup graph_properties

   250   ///This function checks if the given graph is \e 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