UndirEulerIt added
authoralpar
Mon, 21 Nov 2005 09:08:16 +0000
changeset 18188f9905c4e1c1
parent 1817 dc3516405f8f
child 1819 fd82adfbe905
UndirEulerIt added
lemon/euler.h
     1.1 --- a/lemon/euler.h	Fri Nov 18 11:17:08 2005 +0000
     1.2 +++ b/lemon/euler.h	Mon Nov 21 09:08:16 2005 +0000
     1.3 @@ -1,5 +1,5 @@
     1.4  /* -*- C++ -*-
     1.5 - * lemon/topology.h - Part of LEMON, a generic C++ optimization library
     1.6 + * lemon/euler.h - Part of LEMON, a generic C++ optimization library
     1.7   *
     1.8   * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     1.9   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.10 @@ -14,6 +14,7 @@
    1.11   *
    1.12   */
    1.13  #include<lemon/invalid.h>
    1.14 +#include<lemon/topology.h>
    1.15  #include <list>
    1.16  
    1.17  /// \ingroup topology
    1.18 @@ -26,7 +27,7 @@
    1.19  
    1.20  namespace lemon {
    1.21  
    1.22 -  ///Euler iterator in directed graphs.
    1.23 +  ///Euler iterator for directed graphs.
    1.24  
    1.25    /// \ingroup topology
    1.26    ///This iterator converts to the \c Edge type of the graph and using
    1.27 @@ -111,31 +112,133 @@
    1.28      }
    1.29    };
    1.30  
    1.31 +  ///Euler iterator for undirected graphs.
    1.32 +
    1.33 +  /// \ingroup topology
    1.34 +  ///This iterator converts to the \c Edge type of the graph and using
    1.35 +  ///operator ++ it provides an Euler tour of the graph (if there exists).
    1.36 +  ///
    1.37 +  ///For example
    1.38 +  ///if the given graph if Euler (i.e it has only one nontrivial component
    1.39 +  ///and the degree of each node is even),
    1.40 +  ///the following code will print the edge IDs according to an
    1.41 +  ///Euler tour of \c g.
    1.42 +  ///\code
    1.43 +  ///  for(UndirEulerIt<UndirListGraph> e(g),e!=INVALID;++e) {
    1.44 +  ///    std::cout << g.id(UndirEdge(e)) << std::eol;
    1.45 +  ///  }
    1.46 +  ///\endcode
    1.47 +  ///Although the iterator provides an Euler tour of an undirected graph,
    1.48 +  ///in order to indicate the direction of the tour, UndirEulerIt
    1.49 +  ///returns directed edges (that convert to the undirected ones, of course).
    1.50 +  ///
    1.51 +  ///If \c g is not Euler then the resulted tour will not be full or closed.
    1.52 +  ///\todo Test required
    1.53 +  template<class Graph>
    1.54 +  class UndirEulerIt
    1.55 +  {
    1.56 +    typedef typename Graph::Node Node;
    1.57 +    typedef typename Graph::NodeIt NodeIt;
    1.58 +    typedef typename Graph::Edge Edge;
    1.59 +    typedef typename Graph::EdgeIt EdgeIt;
    1.60 +    typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.61 +    typedef typename Graph::InEdgeIt InEdgeIt;
    1.62 +    
    1.63 +    const Graph &g;
    1.64 +    typename Graph::NodeMap<OutEdgeIt> nedge;
    1.65 +    typename Graph::UndirEdgeMap<bool> visited;
    1.66 +    std::list<Edge> euler;
    1.67 +
    1.68 +  public:
    1.69 +    
    1.70 +    ///Constructor
    1.71 +
    1.72 +    ///\param _g An undirected graph.
    1.73 +    ///\param start The starting point of the tour. If it is not given
    1.74 +    ///       the tour will start from the first node.
    1.75 +    UndirEulerIt(const Graph &_g,typename Graph::Node start=INVALID)
    1.76 +      : g(_g), nedge(g), visited(g,false)
    1.77 +    {
    1.78 +      if(start==INVALID) start=NodeIt(g);
    1.79 +      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
    1.80 +      while(nedge[start]!=INVALID) {
    1.81 +	euler.push_back(nedge[start]);
    1.82 +	Node next=g.target(nedge[start]);
    1.83 +	++nedge[start];
    1.84 +	start=next;	while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
    1.85 +      }
    1.86 +    }
    1.87 +    
    1.88 +    ///Edge Conversion
    1.89 +    operator Edge() { return euler.empty()?INVALID:euler.front(); }
    1.90 +    bool operator==(Invalid) { return euler.empty(); }
    1.91 +    bool operator!=(Invalid) { return !euler.empty(); }
    1.92 +    
    1.93 +    ///Next edge of the tour
    1.94 +    UndirEulerIt &operator++() {
    1.95 +      Node s=g.target(euler.front());
    1.96 +      euler.pop_front();
    1.97 +      typename std::list<Edge>::iterator next=euler.begin();
    1.98 +
    1.99 +      while(nedge[s]!=INVALID) {
   1.100 +	while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
   1.101 +	if(nedge[s]==INVALID) break;
   1.102 +	else {
   1.103 +	  euler.insert(next,nedge[s]);
   1.104 +	  Node n=g.target(nedge[s]);
   1.105 +	  ++nedge[s];
   1.106 +	  s=n;
   1.107 +	}
   1.108 +      }
   1.109 +      return *this;
   1.110 +    }
   1.111 +    
   1.112 +    ///Postfix incrementation
   1.113 +    
   1.114 +    ///\warning This incrementation
   1.115 +    ///returns an \c Edge, not an \ref UndirEulerIt, as one may
   1.116 +    ///expect.
   1.117 +    Edge operator++(int) 
   1.118 +    {
   1.119 +      Edge e=*this;
   1.120 +      ++(*this);
   1.121 +      return e;
   1.122 +    }
   1.123 +  };
   1.124 +
   1.125 +
   1.126    ///Checks if the graph is Euler
   1.127  
   1.128 -  /// \ingroup gutils
   1.129 +  /// \ingroup topology
   1.130    ///Checks if the graph is Euler. It works for both directed and
   1.131    ///undirected graphs.
   1.132 +  ///\note By definition, a directed graph is called \e Euler if
   1.133 +  ///and only if connected and the number of it is incoming and outgoing edges
   1.134 +  ///are the same for each node.
   1.135 +  ///Similarly, an undirected graph is called \e Euler if
   1.136 +  ///and only if it is connected and the number of incident edges is even
   1.137 +  ///for each node. <em>Therefore, there are graphs which are not Euler, but
   1.138 +  ///still have an Euler tour</em>.
   1.139    ///\todo Test required
   1.140    template<class Graph>
   1.141  #ifdef DOXYGEN
   1.142    bool
   1.143  #else
   1.144    typename enable_if<typename Graph::UndirTag,bool>::type
   1.145 +  euler(const Graph &g) 
   1.146 +  {
   1.147 +    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
   1.148 +      if(countIncEdges(g,n)%2) return false;
   1.149 +    return connected(g);
   1.150 +  }
   1.151 +  template<class Graph>
   1.152 +  typename disable_if<typename Graph::UndirTag,bool>::type
   1.153  #endif
   1.154    euler(const Graph &g) 
   1.155    {
   1.156      for(typename Graph::NodeIt n(g);n!=INVALID;++n)
   1.157 -      if(countIncEdges(g,n)%2) return false;
   1.158 -    return true;
   1.159 -  }
   1.160 -  template<class Graph>
   1.161 -  typename disable_if<typename Graph::UndirTag,bool>::type
   1.162 -  euler(const Graph &g) 
   1.163 -  {
   1.164 -    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
   1.165        if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
   1.166 -    return true;
   1.167 +    return connected(g);
   1.168    }
   1.169    
   1.170  }