lemon/euler.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 07 Apr 2009 12:56:50 +0100
changeset 571 d5c39e9d1a4e
parent 522 22f932bbb305
child 586 7c12061bd271
permissions -rw-r--r--
Merge
alpar@520
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@520
     2
 *
alpar@520
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@520
     4
 *
alpar@520
     5
 * Copyright (C) 2003-2009
alpar@520
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@520
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@520
     8
 *
alpar@520
     9
 * Permission to use, modify and distribute this software is granted
alpar@520
    10
 * provided that this copyright notice appears in all copies. For
alpar@520
    11
 * precise terms see the accompanying LICENSE file.
alpar@520
    12
 *
alpar@520
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@520
    14
 * express or implied, and with no claim as to its suitability for any
alpar@520
    15
 * purpose.
alpar@520
    16
 *
alpar@520
    17
 */
alpar@520
    18
alpar@520
    19
#ifndef LEMON_EULER_H
alpar@520
    20
#define LEMON_EULER_H
alpar@520
    21
alpar@520
    22
#include<lemon/core.h>
alpar@520
    23
#include<lemon/adaptors.h>
alpar@520
    24
#include<lemon/connectivity.h>
alpar@520
    25
#include <list>
alpar@520
    26
alpar@520
    27
/// \ingroup graph_prop
alpar@520
    28
/// \file
alpar@520
    29
/// \brief Euler tour
alpar@520
    30
///
alpar@520
    31
///This file provides an Euler tour iterator and ways to check
alpar@520
    32
///if a digraph is euler.
alpar@520
    33
alpar@520
    34
alpar@520
    35
namespace lemon {
alpar@520
    36
alpar@520
    37
  ///Euler iterator for digraphs.
alpar@520
    38
alpar@520
    39
  /// \ingroup graph_prop
alpar@520
    40
  ///This iterator converts to the \c Arc type of the digraph and using
alpar@520
    41
  ///operator ++, it provides an Euler tour of a \e directed
alpar@520
    42
  ///graph (if there exists).
alpar@520
    43
  ///
alpar@520
    44
  ///For example
alpar@520
    45
  ///if the given digraph is Euler (i.e it has only one nontrivial component
alpar@520
    46
  ///and the in-degree is equal to the out-degree for all nodes),
alpar@520
    47
  ///the following code will put the arcs of \c g
alpar@520
    48
  ///to the vector \c et according to an
alpar@520
    49
  ///Euler tour of \c g.
alpar@520
    50
  ///\code
alpar@520
    51
  ///  std::vector<ListDigraph::Arc> et;
alpar@520
    52
  ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
alpar@520
    53
  ///    et.push_back(e);
alpar@520
    54
  ///\endcode
alpar@520
    55
  ///If \c g is not Euler then the resulted tour will not be full or closed.
alpar@520
    56
  ///\sa EulerIt
kpeter@559
    57
  template<typename GR>
alpar@520
    58
  class DiEulerIt
alpar@520
    59
  {
kpeter@559
    60
    typedef typename GR::Node Node;
kpeter@559
    61
    typedef typename GR::NodeIt NodeIt;
kpeter@559
    62
    typedef typename GR::Arc Arc;
kpeter@559
    63
    typedef typename GR::ArcIt ArcIt;
kpeter@559
    64
    typedef typename GR::OutArcIt OutArcIt;
kpeter@559
    65
    typedef typename GR::InArcIt InArcIt;
alpar@520
    66
kpeter@559
    67
    const GR &g;
kpeter@559
    68
    typename GR::template NodeMap<OutArcIt> nedge;
alpar@520
    69
    std::list<Arc> euler;
alpar@520
    70
alpar@520
    71
  public:
alpar@520
    72
alpar@520
    73
    ///Constructor
alpar@520
    74
kpeter@559
    75
    ///\param gr A digraph.
alpar@520
    76
    ///\param start The starting point of the tour. If it is not given
alpar@520
    77
    ///       the tour will start from the first node.
kpeter@559
    78
    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
kpeter@559
    79
      : g(gr), nedge(g)
alpar@520
    80
    {
alpar@520
    81
      if(start==INVALID) start=NodeIt(g);
alpar@520
    82
      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
alpar@520
    83
      while(nedge[start]!=INVALID) {
alpar@520
    84
        euler.push_back(nedge[start]);
alpar@520
    85
        Node next=g.target(nedge[start]);
alpar@520
    86
        ++nedge[start];
alpar@520
    87
        start=next;
alpar@520
    88
      }
alpar@520
    89
    }
alpar@520
    90
alpar@520
    91
    ///Arc Conversion
alpar@520
    92
    operator Arc() { return euler.empty()?INVALID:euler.front(); }
alpar@520
    93
    bool operator==(Invalid) { return euler.empty(); }
alpar@520
    94
    bool operator!=(Invalid) { return !euler.empty(); }
alpar@520
    95
alpar@520
    96
    ///Next arc of the tour
alpar@520
    97
    DiEulerIt &operator++() {
alpar@520
    98
      Node s=g.target(euler.front());
alpar@520
    99
      euler.pop_front();
alpar@520
   100
      //This produces a warning.Strange.
alpar@520
   101
      //std::list<Arc>::iterator next=euler.begin();
alpar@520
   102
      typename std::list<Arc>::iterator next=euler.begin();
alpar@520
   103
      while(nedge[s]!=INVALID) {
alpar@520
   104
        euler.insert(next,nedge[s]);
alpar@520
   105
        Node n=g.target(nedge[s]);
alpar@520
   106
        ++nedge[s];
alpar@520
   107
        s=n;
alpar@520
   108
      }
alpar@520
   109
      return *this;
alpar@520
   110
    }
alpar@520
   111
    ///Postfix incrementation
alpar@520
   112
alpar@520
   113
    ///\warning This incrementation
alpar@520
   114
    ///returns an \c Arc, not an \ref DiEulerIt, as one may
alpar@520
   115
    ///expect.
alpar@520
   116
    Arc operator++(int)
alpar@520
   117
    {
alpar@520
   118
      Arc e=*this;
alpar@520
   119
      ++(*this);
alpar@520
   120
      return e;
alpar@520
   121
    }
alpar@520
   122
  };
alpar@520
   123
alpar@520
   124
  ///Euler iterator for graphs.
alpar@520
   125
alpar@520
   126
  /// \ingroup graph_prop
alpar@520
   127
  ///This iterator converts to the \c Arc (or \c Edge)
alpar@520
   128
  ///type of the digraph and using
alpar@520
   129
  ///operator ++, it provides an Euler tour of an undirected
alpar@520
   130
  ///digraph (if there exists).
alpar@520
   131
  ///
alpar@520
   132
  ///For example
alpar@520
   133
  ///if the given digraph if Euler (i.e it has only one nontrivial component
alpar@520
   134
  ///and the degree of each node is even),
alpar@520
   135
  ///the following code will print the arc IDs according to an
alpar@520
   136
  ///Euler tour of \c g.
alpar@520
   137
  ///\code
alpar@520
   138
  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
alpar@520
   139
  ///    std::cout << g.id(Edge(e)) << std::eol;
alpar@520
   140
  ///  }
alpar@520
   141
  ///\endcode
alpar@520
   142
  ///Although the iterator provides an Euler tour of an graph,
alpar@520
   143
  ///it still returns Arcs in order to indicate the direction of the tour.
alpar@520
   144
  ///(But Arc will convert to Edges, of course).
alpar@520
   145
  ///
alpar@520
   146
  ///If \c g is not Euler then the resulted tour will not be full or closed.
alpar@520
   147
  ///\sa EulerIt
kpeter@559
   148
  template<typename GR>
alpar@520
   149
  class EulerIt
alpar@520
   150
  {
kpeter@559
   151
    typedef typename GR::Node Node;
kpeter@559
   152
    typedef typename GR::NodeIt NodeIt;
kpeter@559
   153
    typedef typename GR::Arc Arc;
kpeter@559
   154
    typedef typename GR::Edge Edge;
kpeter@559
   155
    typedef typename GR::ArcIt ArcIt;
kpeter@559
   156
    typedef typename GR::OutArcIt OutArcIt;
kpeter@559
   157
    typedef typename GR::InArcIt InArcIt;
alpar@520
   158
kpeter@559
   159
    const GR &g;
kpeter@559
   160
    typename GR::template NodeMap<OutArcIt> nedge;
kpeter@559
   161
    typename GR::template EdgeMap<bool> visited;
alpar@520
   162
    std::list<Arc> euler;
alpar@520
   163
alpar@520
   164
  public:
alpar@520
   165
alpar@520
   166
    ///Constructor
alpar@520
   167
kpeter@559
   168
    ///\param gr An graph.
alpar@520
   169
    ///\param start The starting point of the tour. If it is not given
alpar@520
   170
    ///       the tour will start from the first node.
kpeter@559
   171
    EulerIt(const GR &gr, typename GR::Node start = INVALID)
kpeter@559
   172
      : g(gr), nedge(g), visited(g, false)
alpar@520
   173
    {
alpar@520
   174
      if(start==INVALID) start=NodeIt(g);
alpar@520
   175
      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
alpar@520
   176
      while(nedge[start]!=INVALID) {
alpar@520
   177
        euler.push_back(nedge[start]);
alpar@520
   178
        visited[nedge[start]]=true;
alpar@520
   179
        Node next=g.target(nedge[start]);
alpar@520
   180
        ++nedge[start];
alpar@520
   181
        start=next;
alpar@520
   182
        while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
alpar@520
   183
      }
alpar@520
   184
    }
alpar@520
   185
alpar@520
   186
    ///Arc Conversion
alpar@520
   187
    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
alpar@520
   188
    ///Arc Conversion
alpar@520
   189
    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
alpar@520
   190
    ///\e
alpar@520
   191
    bool operator==(Invalid) const { return euler.empty(); }
alpar@520
   192
    ///\e
alpar@520
   193
    bool operator!=(Invalid) const { return !euler.empty(); }
alpar@520
   194
alpar@520
   195
    ///Next arc of the tour
alpar@520
   196
    EulerIt &operator++() {
alpar@520
   197
      Node s=g.target(euler.front());
alpar@520
   198
      euler.pop_front();
alpar@520
   199
      typename std::list<Arc>::iterator next=euler.begin();
alpar@520
   200
alpar@520
   201
      while(nedge[s]!=INVALID) {
alpar@520
   202
        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
alpar@520
   203
        if(nedge[s]==INVALID) break;
alpar@520
   204
        else {
alpar@520
   205
          euler.insert(next,nedge[s]);
alpar@520
   206
          visited[nedge[s]]=true;
alpar@520
   207
          Node n=g.target(nedge[s]);
alpar@520
   208
          ++nedge[s];
alpar@520
   209
          s=n;
alpar@520
   210
        }
alpar@520
   211
      }
alpar@520
   212
      return *this;
alpar@520
   213
    }
alpar@520
   214
alpar@520
   215
    ///Postfix incrementation
alpar@520
   216
alpar@520
   217
    ///\warning This incrementation
alpar@520
   218
    ///returns an \c Arc, not an \ref EulerIt, as one may
alpar@520
   219
    ///expect.
alpar@520
   220
    Arc operator++(int)
alpar@520
   221
    {
alpar@520
   222
      Arc e=*this;
alpar@520
   223
      ++(*this);
alpar@520
   224
      return e;
alpar@520
   225
    }
alpar@520
   226
  };
alpar@520
   227
alpar@520
   228
alpar@521
   229
  ///Checks if the graph is Eulerian
alpar@520
   230
alpar@520
   231
  /// \ingroup graph_prop
alpar@521
   232
  ///Checks if the graph is Eulerian. It works for both directed and undirected
alpar@520
   233
  ///graphs.
alpar@521
   234
  ///\note By definition, a digraph is called \e Eulerian if
alpar@520
   235
  ///and only if it is connected and the number of its incoming and outgoing
alpar@520
   236
  ///arcs are the same for each node.
alpar@521
   237
  ///Similarly, an undirected graph is called \e Eulerian if
alpar@520
   238
  ///and only if it is connected and the number of incident arcs is even
alpar@521
   239
  ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
alpar@521
   240
  ///but still have an Euler tour</em>.
kpeter@559
   241
  template<typename GR>
alpar@520
   242
#ifdef DOXYGEN
alpar@520
   243
  bool
alpar@520
   244
#else
kpeter@559
   245
  typename enable_if<UndirectedTagIndicator<GR>,bool>::type
kpeter@559
   246
  eulerian(const GR &g)
alpar@520
   247
  {
kpeter@559
   248
    for(typename GR::NodeIt n(g);n!=INVALID;++n)
alpar@520
   249
      if(countIncEdges(g,n)%2) return false;
alpar@520
   250
    return connected(g);
alpar@520
   251
  }
kpeter@559
   252
  template<class GR>
kpeter@559
   253
  typename disable_if<UndirectedTagIndicator<GR>,bool>::type
alpar@520
   254
#endif
kpeter@559
   255
  eulerian(const GR &g)
alpar@520
   256
  {
kpeter@559
   257
    for(typename GR::NodeIt n(g);n!=INVALID;++n)
alpar@520
   258
      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
kpeter@559
   259
    return connected(Undirector<const GR>(g));
alpar@520
   260
  }
alpar@520
   261
alpar@520
   262
}
alpar@520
   263
alpar@520
   264
#endif