lemon/euler.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 20 Feb 2010 18:39:03 +0100
changeset 839 f3bc4e9b5f3a
parent 592 2ebfdb89ec66
child 877 141f9c0db4a3
permissions -rw-r--r--
New heuristics for MCF algorithms (#340)
and some implementation improvements.

- A useful heuristic is added to NetworkSimplex to make the
initial pivots faster.
- A powerful global update heuristic is added to CostScaling
and the implementation is reworked with various improvements.
- Better relabeling in CostScaling to improve numerical stability
and make the code faster.
- A small improvement is made in CapacityScaling for better
delta computation.
- Add notes to the classes about the usage of vector<char> instead
of vector<bool> for efficiency reasons.
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
kpeter@586
    27
/// \ingroup graph_properties
alpar@520
    28
/// \file
kpeter@592
    29
/// \brief Euler tour iterators and a function for checking the \e Eulerian 
kpeter@592
    30
/// property.
alpar@520
    31
///
kpeter@592
    32
///This file provides Euler tour iterators and a function to check
kpeter@592
    33
///if a (di)graph is \e Eulerian.
alpar@520
    34
alpar@520
    35
namespace lemon {
alpar@520
    36
kpeter@592
    37
  ///Euler tour iterator for digraphs.
alpar@520
    38
kpeter@592
    39
  /// \ingroup graph_prop
kpeter@592
    40
  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
kpeter@592
    41
  ///graph (if there exists) and it converts to the \c Arc type of the digraph.
alpar@520
    42
  ///
kpeter@592
    43
  ///For example, if the given digraph has an Euler tour (i.e it has only one
kpeter@592
    44
  ///non-trivial component and the in-degree is equal to the out-degree 
kpeter@592
    45
  ///for all nodes), then the following code will put the arcs of \c g
kpeter@592
    46
  ///to the vector \c et according to an Euler tour of \c g.
alpar@520
    47
  ///\code
alpar@520
    48
  ///  std::vector<ListDigraph::Arc> et;
kpeter@592
    49
  ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
alpar@520
    50
  ///    et.push_back(e);
alpar@520
    51
  ///\endcode
kpeter@592
    52
  ///If \c g has no Euler tour, then the resulted walk will not be closed
kpeter@592
    53
  ///or not contain all arcs.
alpar@520
    54
  ///\sa EulerIt
kpeter@559
    55
  template<typename GR>
alpar@520
    56
  class DiEulerIt
alpar@520
    57
  {
kpeter@559
    58
    typedef typename GR::Node Node;
kpeter@559
    59
    typedef typename GR::NodeIt NodeIt;
kpeter@559
    60
    typedef typename GR::Arc Arc;
kpeter@559
    61
    typedef typename GR::ArcIt ArcIt;
kpeter@559
    62
    typedef typename GR::OutArcIt OutArcIt;
kpeter@559
    63
    typedef typename GR::InArcIt InArcIt;
alpar@520
    64
kpeter@559
    65
    const GR &g;
kpeter@592
    66
    typename GR::template NodeMap<OutArcIt> narc;
alpar@520
    67
    std::list<Arc> euler;
alpar@520
    68
alpar@520
    69
  public:
alpar@520
    70
alpar@520
    71
    ///Constructor
alpar@520
    72
kpeter@592
    73
    ///Constructor.
kpeter@559
    74
    ///\param gr A digraph.
kpeter@592
    75
    ///\param start The starting point of the tour. If it is not given,
kpeter@592
    76
    ///the tour will start from the first node that has an outgoing arc.
kpeter@559
    77
    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
kpeter@592
    78
      : g(gr), narc(g)
alpar@520
    79
    {
kpeter@591
    80
      if (start==INVALID) {
kpeter@591
    81
        NodeIt n(g);
kpeter@591
    82
        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
kpeter@591
    83
        start=n;
kpeter@591
    84
      }
kpeter@591
    85
      if (start!=INVALID) {
kpeter@592
    86
        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
kpeter@592
    87
        while (narc[start]!=INVALID) {
kpeter@592
    88
          euler.push_back(narc[start]);
kpeter@592
    89
          Node next=g.target(narc[start]);
kpeter@592
    90
          ++narc[start];
kpeter@591
    91
          start=next;
kpeter@591
    92
        }
alpar@520
    93
      }
alpar@520
    94
    }
alpar@520
    95
kpeter@592
    96
    ///Arc conversion
alpar@520
    97
    operator Arc() { return euler.empty()?INVALID:euler.front(); }
kpeter@592
    98
    ///Compare with \c INVALID
alpar@520
    99
    bool operator==(Invalid) { return euler.empty(); }
kpeter@592
   100
    ///Compare with \c INVALID
alpar@520
   101
    bool operator!=(Invalid) { return !euler.empty(); }
alpar@520
   102
alpar@520
   103
    ///Next arc of the tour
kpeter@592
   104
kpeter@592
   105
    ///Next arc of the tour
kpeter@592
   106
    ///
alpar@520
   107
    DiEulerIt &operator++() {
alpar@520
   108
      Node s=g.target(euler.front());
alpar@520
   109
      euler.pop_front();
alpar@520
   110
      typename std::list<Arc>::iterator next=euler.begin();
kpeter@592
   111
      while(narc[s]!=INVALID) {
kpeter@592
   112
        euler.insert(next,narc[s]);
kpeter@592
   113
        Node n=g.target(narc[s]);
kpeter@592
   114
        ++narc[s];
alpar@520
   115
        s=n;
alpar@520
   116
      }
alpar@520
   117
      return *this;
alpar@520
   118
    }
alpar@520
   119
    ///Postfix incrementation
alpar@520
   120
kpeter@592
   121
    /// Postfix incrementation.
kpeter@592
   122
    ///
alpar@520
   123
    ///\warning This incrementation
kpeter@592
   124
    ///returns an \c Arc, not a \ref DiEulerIt, as one may
alpar@520
   125
    ///expect.
alpar@520
   126
    Arc operator++(int)
alpar@520
   127
    {
alpar@520
   128
      Arc e=*this;
alpar@520
   129
      ++(*this);
alpar@520
   130
      return e;
alpar@520
   131
    }
alpar@520
   132
  };
alpar@520
   133
kpeter@592
   134
  ///Euler tour iterator for graphs.
alpar@520
   135
kpeter@586
   136
  /// \ingroup graph_properties
kpeter@592
   137
  ///This iterator provides an Euler tour (Eulerian circuit) of an
kpeter@592
   138
  ///\e undirected graph (if there exists) and it converts to the \c Arc
kpeter@592
   139
  ///and \c Edge types of the graph.
alpar@520
   140
  ///
kpeter@592
   141
  ///For example, if the given graph has an Euler tour (i.e it has only one 
kpeter@592
   142
  ///non-trivial component and the degree of each node is even),
alpar@520
   143
  ///the following code will print the arc IDs according to an
alpar@520
   144
  ///Euler tour of \c g.
alpar@520
   145
  ///\code
kpeter@592
   146
  ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
alpar@520
   147
  ///    std::cout << g.id(Edge(e)) << std::eol;
alpar@520
   148
  ///  }
alpar@520
   149
  ///\endcode
kpeter@592
   150
  ///Although this iterator is for undirected graphs, it still returns 
kpeter@592
   151
  ///arcs in order to indicate the direction of the tour.
kpeter@592
   152
  ///(But arcs convert to edges, of course.)
alpar@520
   153
  ///
kpeter@592
   154
  ///If \c g has no Euler tour, then the resulted walk will not be closed
kpeter@592
   155
  ///or not contain all edges.
kpeter@559
   156
  template<typename GR>
alpar@520
   157
  class EulerIt
alpar@520
   158
  {
kpeter@559
   159
    typedef typename GR::Node Node;
kpeter@559
   160
    typedef typename GR::NodeIt NodeIt;
kpeter@559
   161
    typedef typename GR::Arc Arc;
kpeter@559
   162
    typedef typename GR::Edge Edge;
kpeter@559
   163
    typedef typename GR::ArcIt ArcIt;
kpeter@559
   164
    typedef typename GR::OutArcIt OutArcIt;
kpeter@559
   165
    typedef typename GR::InArcIt InArcIt;
alpar@520
   166
kpeter@559
   167
    const GR &g;
kpeter@592
   168
    typename GR::template NodeMap<OutArcIt> narc;
kpeter@559
   169
    typename GR::template EdgeMap<bool> visited;
alpar@520
   170
    std::list<Arc> euler;
alpar@520
   171
alpar@520
   172
  public:
alpar@520
   173
alpar@520
   174
    ///Constructor
alpar@520
   175
kpeter@592
   176
    ///Constructor.
kpeter@592
   177
    ///\param gr A graph.
kpeter@592
   178
    ///\param start The starting point of the tour. If it is not given,
kpeter@592
   179
    ///the tour will start from the first node that has an incident edge.
kpeter@559
   180
    EulerIt(const GR &gr, typename GR::Node start = INVALID)
kpeter@592
   181
      : g(gr), narc(g), visited(g, false)
alpar@520
   182
    {
kpeter@591
   183
      if (start==INVALID) {
kpeter@591
   184
        NodeIt n(g);
kpeter@591
   185
        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
kpeter@591
   186
        start=n;
kpeter@591
   187
      }
kpeter@591
   188
      if (start!=INVALID) {
kpeter@592
   189
        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
kpeter@592
   190
        while(narc[start]!=INVALID) {
kpeter@592
   191
          euler.push_back(narc[start]);
kpeter@592
   192
          visited[narc[start]]=true;
kpeter@592
   193
          Node next=g.target(narc[start]);
kpeter@592
   194
          ++narc[start];
kpeter@591
   195
          start=next;
kpeter@592
   196
          while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
kpeter@591
   197
        }
alpar@520
   198
      }
alpar@520
   199
    }
alpar@520
   200
kpeter@592
   201
    ///Arc conversion
alpar@520
   202
    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
kpeter@592
   203
    ///Edge conversion
alpar@520
   204
    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
kpeter@592
   205
    ///Compare with \c INVALID
alpar@520
   206
    bool operator==(Invalid) const { return euler.empty(); }
kpeter@592
   207
    ///Compare with \c INVALID
alpar@520
   208
    bool operator!=(Invalid) const { return !euler.empty(); }
alpar@520
   209
alpar@520
   210
    ///Next arc of the tour
kpeter@592
   211
kpeter@592
   212
    ///Next arc of the tour
kpeter@592
   213
    ///
alpar@520
   214
    EulerIt &operator++() {
alpar@520
   215
      Node s=g.target(euler.front());
alpar@520
   216
      euler.pop_front();
alpar@520
   217
      typename std::list<Arc>::iterator next=euler.begin();
kpeter@592
   218
      while(narc[s]!=INVALID) {
kpeter@592
   219
        while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
kpeter@592
   220
        if(narc[s]==INVALID) break;
alpar@520
   221
        else {
kpeter@592
   222
          euler.insert(next,narc[s]);
kpeter@592
   223
          visited[narc[s]]=true;
kpeter@592
   224
          Node n=g.target(narc[s]);
kpeter@592
   225
          ++narc[s];
alpar@520
   226
          s=n;
alpar@520
   227
        }
alpar@520
   228
      }
alpar@520
   229
      return *this;
alpar@520
   230
    }
alpar@520
   231
alpar@520
   232
    ///Postfix incrementation
alpar@520
   233
kpeter@592
   234
    /// Postfix incrementation.
kpeter@592
   235
    ///
kpeter@592
   236
    ///\warning This incrementation returns an \c Arc (which converts to 
kpeter@592
   237
    ///an \c Edge), not an \ref EulerIt, as one may expect.
alpar@520
   238
    Arc operator++(int)
alpar@520
   239
    {
alpar@520
   240
      Arc e=*this;
alpar@520
   241
      ++(*this);
alpar@520
   242
      return e;
alpar@520
   243
    }
alpar@520
   244
  };
alpar@520
   245
alpar@520
   246
kpeter@648
   247
  ///Check if the given graph is Eulerian
alpar@520
   248
kpeter@586
   249
  /// \ingroup graph_properties
kpeter@648
   250
  ///This function checks if the given graph is Eulerian.
kpeter@592
   251
  ///It works for both directed and undirected graphs.
kpeter@592
   252
  ///
kpeter@592
   253
  ///By definition, a digraph is called \e Eulerian if
kpeter@592
   254
  ///and only if it is connected and the number of incoming and outgoing
alpar@520
   255
  ///arcs are the same for each node.
alpar@521
   256
  ///Similarly, an undirected graph is called \e Eulerian if
kpeter@592
   257
  ///and only if it is connected and the number of incident edges is even
kpeter@592
   258
  ///for each node.
kpeter@592
   259
  ///
kpeter@592
   260
  ///\note There are (di)graphs that are not Eulerian, but still have an
kpeter@592
   261
  /// Euler tour, since they may contain isolated nodes.
kpeter@592
   262
  ///
kpeter@592
   263
  ///\sa DiEulerIt, EulerIt
kpeter@559
   264
  template<typename GR>
alpar@520
   265
#ifdef DOXYGEN
alpar@520
   266
  bool
alpar@520
   267
#else
kpeter@559
   268
  typename enable_if<UndirectedTagIndicator<GR>,bool>::type
kpeter@559
   269
  eulerian(const GR &g)
alpar@520
   270
  {
kpeter@559
   271
    for(typename GR::NodeIt n(g);n!=INVALID;++n)
alpar@520
   272
      if(countIncEdges(g,n)%2) return false;
alpar@520
   273
    return connected(g);
alpar@520
   274
  }
kpeter@559
   275
  template<class GR>
kpeter@559
   276
  typename disable_if<UndirectedTagIndicator<GR>,bool>::type
alpar@520
   277
#endif
kpeter@559
   278
  eulerian(const GR &g)
alpar@520
   279
  {
kpeter@559
   280
    for(typename GR::NodeIt n(g);n!=INVALID;++n)
alpar@520
   281
      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
kpeter@592
   282
    return connected(undirector(g));
alpar@520
   283
  }
alpar@520
   284
alpar@520
   285
}
alpar@520
   286
alpar@520
   287
#endif