lemon/euler.h
 author Akos Ladanyi Mon, 03 Nov 2008 11:59:54 +0000 changeset 569 22f932bbb305 parent 568 3af83b6be1df child 606 c5fd2d996909 permissions -rw-r--r--
Test for euler.h (#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   template<class Digraph>

    58   class DiEulerIt

    59   {

    60     typedef typename Digraph::Node Node;

    61     typedef typename Digraph::NodeIt NodeIt;

    62     typedef typename Digraph::Arc Arc;

    63     typedef typename Digraph::ArcIt ArcIt;

    64     typedef typename Digraph::OutArcIt OutArcIt;

    65     typedef typename Digraph::InArcIt InArcIt;

    66

    67     const Digraph &g;

    68     typename Digraph::template NodeMap<OutArcIt> nedge;

    69     std::list<Arc> euler;

    70

    71   public:

    72

    73     ///Constructor

    74

    75     ///\param _g 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 Digraph &_g,typename Digraph::Node start=INVALID)

    79       : g(_g), nedge(g)

    80     {

    81       if(start==INVALID) start=NodeIt(g);

    82       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);

    83       while(nedge[start]!=INVALID) {

    84         euler.push_back(nedge[start]);

    85         Node next=g.target(nedge[start]);

    86         ++nedge[start];

    87         start=next;

    88       }

    89     }

    90

    91     ///Arc Conversion

    92     operator Arc() { return euler.empty()?INVALID:euler.front(); }

    93     bool operator==(Invalid) { return euler.empty(); }

    94     bool operator!=(Invalid) { return !euler.empty(); }

    95

    96     ///Next arc of the tour

    97     DiEulerIt &operator++() {

    98       Node s=g.target(euler.front());

    99       euler.pop_front();

   100       //This produces a warning.Strange.

   101       //std::list<Arc>::iterator next=euler.begin();

   102       typename std::list<Arc>::iterator next=euler.begin();

   103       while(nedge[s]!=INVALID) {

   104         euler.insert(next,nedge[s]);

   105         Node n=g.target(nedge[s]);

   106         ++nedge[s];

   107         s=n;

   108       }

   109       return *this;

   110     }

   111     ///Postfix incrementation

   112

   113     ///\warning This incrementation

   114     ///returns an \c Arc, not an \ref DiEulerIt, as one may

   115     ///expect.

   116     Arc operator++(int)

   117     {

   118       Arc e=*this;

   119       ++(*this);

   120       return e;

   121     }

   122   };

   123

   124   ///Euler iterator for graphs.

   125

   126   /// \ingroup graph_prop

   127   ///This iterator converts to the \c Arc (or \c Edge)

   128   ///type of the digraph and using

   129   ///operator ++, it provides an Euler tour of an undirected

   130   ///digraph (if there exists).

   131   ///

   132   ///For example

   133   ///if the given digraph if Euler (i.e it has only one nontrivial component

   134   ///and the degree of each node is even),

   135   ///the following code will print the arc IDs according to an

   136   ///Euler tour of \c g.

   137   ///\code

   138   ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {

   139   ///    std::cout << g.id(Edge(e)) << std::eol;

   140   ///  }

   141   ///\endcode

   142   ///Although the iterator provides an Euler tour of an graph,

   143   ///it still returns Arcs in order to indicate the direction of the tour.

   144   ///(But Arc will convert to Edges, of course).

   145   ///

   146   ///If \c g is not Euler then the resulted tour will not be full or closed.

   147   ///\sa EulerIt

   148   template<class Digraph>

   149   class EulerIt

   150   {

   151     typedef typename Digraph::Node Node;

   152     typedef typename Digraph::NodeIt NodeIt;

   153     typedef typename Digraph::Arc Arc;

   154     typedef typename Digraph::Edge Edge;

   155     typedef typename Digraph::ArcIt ArcIt;

   156     typedef typename Digraph::OutArcIt OutArcIt;

   157     typedef typename Digraph::InArcIt InArcIt;

   158

   159     const Digraph &g;

   160     typename Digraph::template NodeMap<OutArcIt> nedge;

   161     typename Digraph::template EdgeMap<bool> visited;

   162     std::list<Arc> euler;

   163

   164   public:

   165

   166     ///Constructor

   167

   168     ///\param _g An graph.

   169     ///\param start The starting point of the tour. If it is not given

   170     ///       the tour will start from the first node.

   171     EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)

   172       : g(_g), nedge(g), visited(g,false)

   173     {

   174       if(start==INVALID) start=NodeIt(g);

   175       for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);

   176       while(nedge[start]!=INVALID) {

   177         euler.push_back(nedge[start]);

   178         visited[nedge[start]]=true;

   179         Node next=g.target(nedge[start]);

   180         ++nedge[start];

   181         start=next;

   182         while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];

   183       }

   184     }

   185

   186     ///Arc Conversion

   187     operator Arc() const { return euler.empty()?INVALID:euler.front(); }

   188     ///Arc Conversion

   189     operator Edge() const { return euler.empty()?INVALID:euler.front(); }

   190     ///\e

   191     bool operator==(Invalid) const { return euler.empty(); }

   192     ///\e

   193     bool operator!=(Invalid) const { return !euler.empty(); }

   194

   195     ///Next arc of the tour

   196     EulerIt &operator++() {

   197       Node s=g.target(euler.front());

   198       euler.pop_front();

   199       typename std::list<Arc>::iterator next=euler.begin();

   200

   201       while(nedge[s]!=INVALID) {

   202         while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];

   203         if(nedge[s]==INVALID) break;

   204         else {

   205           euler.insert(next,nedge[s]);

   206           visited[nedge[s]]=true;

   207           Node n=g.target(nedge[s]);

   208           ++nedge[s];

   209           s=n;

   210         }

   211       }

   212       return *this;

   213     }

   214

   215     ///Postfix incrementation

   216

   217     ///\warning This incrementation

   218     ///returns an \c Arc, not an \ref EulerIt, as one may

   219     ///expect.

   220     Arc operator++(int)

   221     {

   222       Arc e=*this;

   223       ++(*this);

   224       return e;

   225     }

   226   };

   227

   228

   229   ///Checks if the graph is Eulerian

   230

   231   /// \ingroup graph_prop

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

   233   ///graphs.

   234   ///\note By definition, a digraph is called \e Eulerian if

   235   ///and only if it is connected and the number of its incoming and outgoing

   236   ///arcs are the same for each node.

   237   ///Similarly, an undirected graph is called \e Eulerian if

   238   ///and only if it is connected and the number of incident arcs is even

   239   ///for each node. <em>Therefore, there are digraphs which are not Eulerian,

   240   ///but still have an Euler tour</em>.

   241   template<class Digraph>

   242 #ifdef DOXYGEN

   243   bool

   244 #else

   245   typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type

   246   eulerian(const Digraph &g)

   247   {

   248     for(typename Digraph::NodeIt n(g);n!=INVALID;++n)

   249       if(countIncEdges(g,n)%2) return false;

   250     return connected(g);

   251   }

   252   template<class Digraph>

   253   typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type

   254 #endif

   255   eulerian(const Digraph &g)

   256   {

   257     for(typename Digraph::NodeIt n(g);n!=INVALID;++n)

   258       if(countInArcs(g,n)!=countOutArcs(g,n)) return false;

   259     return connected(Undirector<const Digraph>(g));

   260   }

   261

   262 }

   263

   264 #endif