lemon/euler.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 521 3af83b6be1df
child 559 c5fd2d996909
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
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
alpar@520
    57
  template<class Digraph>
alpar@520
    58
  class DiEulerIt
alpar@520
    59
  {
alpar@520
    60
    typedef typename Digraph::Node Node;
alpar@520
    61
    typedef typename Digraph::NodeIt NodeIt;
alpar@520
    62
    typedef typename Digraph::Arc Arc;
alpar@520
    63
    typedef typename Digraph::ArcIt ArcIt;
alpar@520
    64
    typedef typename Digraph::OutArcIt OutArcIt;
alpar@520
    65
    typedef typename Digraph::InArcIt InArcIt;
alpar@520
    66
alpar@520
    67
    const Digraph &g;
alpar@520
    68
    typename Digraph::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
alpar@520
    75
    ///\param _g 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.
alpar@520
    78
    DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
alpar@520
    79
      : g(_g), 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
alpar@520
   148
  template<class Digraph>
alpar@520
   149
  class EulerIt
alpar@520
   150
  {
alpar@520
   151
    typedef typename Digraph::Node Node;
alpar@520
   152
    typedef typename Digraph::NodeIt NodeIt;
alpar@520
   153
    typedef typename Digraph::Arc Arc;
alpar@520
   154
    typedef typename Digraph::Edge Edge;
alpar@520
   155
    typedef typename Digraph::ArcIt ArcIt;
alpar@520
   156
    typedef typename Digraph::OutArcIt OutArcIt;
alpar@520
   157
    typedef typename Digraph::InArcIt InArcIt;
alpar@520
   158
alpar@520
   159
    const Digraph &g;
alpar@520
   160
    typename Digraph::template NodeMap<OutArcIt> nedge;
alpar@520
   161
    typename Digraph::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
alpar@520
   168
    ///\param _g 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.
alpar@520
   171
    EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
alpar@520
   172
      : g(_g), 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>.
alpar@520
   241
  template<class Digraph>
alpar@520
   242
#ifdef DOXYGEN
alpar@520
   243
  bool
alpar@520
   244
#else
alpar@520
   245
  typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
alpar@521
   246
  eulerian(const Digraph &g)
alpar@520
   247
  {
alpar@520
   248
    for(typename Digraph::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
  }
alpar@520
   252
  template<class Digraph>
alpar@520
   253
  typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
alpar@520
   254
#endif
alpar@521
   255
  eulerian(const Digraph &g)
alpar@520
   256
  {
alpar@520
   257
    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
alpar@520
   258
      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
alpar@520
   259
    return connected(Undirector<const Digraph>(g));
alpar@520
   260
  }
alpar@520
   261
alpar@520
   262
}
alpar@520
   263
alpar@520
   264
#endif