lemon/euler.h
author deba
Wed, 02 Nov 2005 15:23:46 +0000
changeset 1750 5c76ebbb4818
child 1761 896464fe9fbb
permissions -rw-r--r--
Connected components, etc...
Based on the dfs visitor interface
alpar@1738
     1
/* -*- C++ -*-
alpar@1738
     2
 * lemon/topology.h - Part of LEMON, a generic C++ optimization library
alpar@1738
     3
 *
alpar@1738
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1738
     5
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1738
     6
 *
alpar@1738
     7
 * Permission to use, modify and distribute this software is granted
alpar@1738
     8
 * provided that this copyright notice appears in all copies. For
alpar@1738
     9
 * precise terms see the accompanying LICENSE file.
alpar@1738
    10
 *
alpar@1738
    11
 * This software is provided "AS IS" with no warranty of any kind,
alpar@1738
    12
 * express or implied, and with no claim as to its suitability for any
alpar@1738
    13
 * purpose.
alpar@1738
    14
 *
alpar@1738
    15
 */
alpar@1738
    16
#include<lemon/invalid.h>
alpar@1738
    17
#include <list>
alpar@1738
    18
alpar@1738
    19
/// \ingroup gutils
alpar@1738
    20
/// \file
alpar@1738
    21
/// \brief Euler tour
alpar@1738
    22
///
alpar@1738
    23
///This file provides an Euler tour iterator and ways to check
alpar@1738
    24
///if a graph is euler.
alpar@1738
    25
alpar@1738
    26
alpar@1738
    27
namespace lemon {
alpar@1738
    28
alpar@1738
    29
  ///Euler iterator in directed graphs.
alpar@1738
    30
alpar@1738
    31
  /// \ingroup gutils
alpar@1738
    32
  ///This iterator converts to the \c Edge type of the graph and using
alpar@1738
    33
  ///the ++ operator it provides an Euler tour of the graph (if there exists).
alpar@1738
    34
  ///
alpar@1738
    35
  ///For example
alpar@1738
    36
  ///if the given graph if Euler (i.e it has only one nontrivial component
alpar@1738
    37
  ///and the in-degree is equal to the out-degree for all nodes),
alpar@1738
    38
  ///the the following code will print the edge IDs according to an
alpar@1738
    39
  ///Euler tour of \c g.
alpar@1738
    40
  ///\code
alpar@1738
    41
  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
alpar@1738
    42
  ///    std::cout << g.id(e) << std::eol;
alpar@1738
    43
  ///  }
alpar@1738
    44
  ///\endcode
alpar@1738
    45
  ///If \c g is not Euler then the resulted tour will not be full or closed.
alpar@1738
    46
  ///\todo Test required
alpar@1738
    47
  template<class Graph>
alpar@1738
    48
  class EulerIt 
alpar@1738
    49
  {
alpar@1738
    50
    typedef typename Graph::Node Node;
alpar@1738
    51
    typedef typename Graph::NodeIt NodeIt;
alpar@1738
    52
    typedef typename Graph::Edge Edge;
alpar@1738
    53
    typedef typename Graph::EdgeIt EdgeIt;
alpar@1738
    54
    typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@1738
    55
    typedef typename Graph::InEdgeIt InEdgeIt;
alpar@1738
    56
    
alpar@1738
    57
    const Graph &g;
alpar@1738
    58
    typename Graph::NodeMap<OutEdgeIt> nedge;
alpar@1738
    59
    std::list<Edge> euler;
alpar@1738
    60
alpar@1738
    61
  public:
alpar@1738
    62
    
alpar@1738
    63
    ///Constructor
alpar@1738
    64
alpar@1738
    65
    ///\param _g A directed graph.
alpar@1738
    66
    ///\param start The starting point of the tour. If it is not given
alpar@1738
    67
    ///       tho tour will start from the first node.
alpar@1738
    68
    EulerIt(const Graph &_g,typename Graph::Node start=INVALID)
alpar@1738
    69
      : g(_g), nedge(g)
alpar@1738
    70
    {
alpar@1738
    71
      if(start==INVALID) start=NodeIt(g);
alpar@1738
    72
      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
alpar@1738
    73
      while(nedge[start]!=INVALID) {
alpar@1738
    74
	euler.push_back(nedge[start]);
alpar@1738
    75
	Node next=g.target(nedge[start]);
alpar@1738
    76
	++nedge[start];
alpar@1738
    77
	start=next;
alpar@1738
    78
      }
alpar@1738
    79
    }
alpar@1738
    80
    
alpar@1738
    81
    ///Edge Conversion
alpar@1738
    82
    operator Edge() { return euler.empty()?INVALID:euler.front(); }
alpar@1738
    83
    bool operator==(Invalid) { return euler.empty(); }
alpar@1738
    84
    bool operator!=(Invalid) { return !euler.empty(); }
alpar@1738
    85
    
alpar@1738
    86
    ///Next edge of the tour
alpar@1738
    87
    EulerIt &operator++() {
alpar@1738
    88
      Node s=g.target(euler.front());
alpar@1738
    89
      euler.pop_front();
alpar@1738
    90
      //This produces a warning.Strange.
alpar@1738
    91
      //std::list<Edge>::iterator next=euler.begin();
alpar@1738
    92
      typename std::list<Edge>::iterator next=euler.begin();
alpar@1738
    93
      while(nedge[s]!=INVALID) {
alpar@1738
    94
	euler.insert(next,nedge[s]);
alpar@1738
    95
	Node n=g.target(nedge[s]);
alpar@1738
    96
	++nedge[s];
alpar@1738
    97
	s=n;
alpar@1738
    98
      }
alpar@1738
    99
      return *this;
alpar@1738
   100
    }
alpar@1738
   101
    ///Postfix incrementation
alpar@1738
   102
    
alpar@1738
   103
    ///\warning This gives back an Edge, not an EulerIt!
alpar@1738
   104
    ///\todo Is this what we want?
alpar@1738
   105
    Edge operator++(int) 
alpar@1738
   106
    {
alpar@1738
   107
      Edge e=*this;
alpar@1738
   108
      ++(*this);
alpar@1738
   109
      return e;
alpar@1738
   110
    }
alpar@1738
   111
  };
alpar@1738
   112
alpar@1738
   113
  ///Checks if the graph is Euler
alpar@1738
   114
alpar@1738
   115
  /// \ingroup gutils
alpar@1738
   116
  ///Checks if the graph is Euler. It works for both directed and
alpar@1738
   117
  ///undirected graphs.
alpar@1738
   118
  ///\todo What to do with the isolated points?
alpar@1738
   119
  ///\todo Test required
alpar@1738
   120
  template<class Graph>
alpar@1738
   121
#ifdef DOXYGEN
alpar@1738
   122
  bool
alpar@1738
   123
#else
alpar@1738
   124
  typename enable_if<typename Graph::UndirTag,bool>::type
alpar@1738
   125
#endif
alpar@1738
   126
  euler(const Graph &g) 
alpar@1738
   127
  {
alpar@1738
   128
    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
alpar@1738
   129
      if(countIncEdges(g,n)%2) return false;
alpar@1738
   130
    return true;
alpar@1738
   131
  }
alpar@1738
   132
  template<class Graph>
alpar@1738
   133
  typename disable_if<typename Graph::UndirTag,bool>::type
alpar@1738
   134
  isEuler(const Graph &g) 
alpar@1738
   135
  {
alpar@1738
   136
    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
alpar@1738
   137
      if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
alpar@1738
   138
    return true;
alpar@1738
   139
  }
alpar@1738
   140
  
alpar@1738
   141
}