lemon/euler.h
 author Alpar Juttner Mon, 23 Feb 2009 11:30:15 +0000 changeset 568 3af83b6be1df parent 567 42d4b889903a child 569 22f932bbb305 permissions -rw-r--r--
Rename euler() to eulerian() (#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 Eulerian

   232

   233   /// \ingroup graph_prop

   234   ///Checks if the graph is Eulerian. It works for both directed and undirected

   235   ///graphs.

   236   ///\note By definition, a digraph is called \e Eulerian 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 Eulerian 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 Eulerian,

   242   ///but 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   eulerian(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   eulerian(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