1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/euler.h	Mon Oct 24 15:58:38 2005 +0000
     1.3 @@ -0,0 +1,141 @@
     1.4 +/* -*- C++ -*-
     1.5 + * lemon/topology.h - Part of LEMON, a generic C++ optimization library
     1.6 + *
     1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
     1.9 + *
    1.10 + * Permission to use, modify and distribute this software is granted
    1.11 + * provided that this copyright notice appears in all copies. For
    1.12 + * precise terms see the accompanying LICENSE file.
    1.13 + *
    1.14 + * This software is provided "AS IS" with no warranty of any kind,
    1.15 + * express or implied, and with no claim as to its suitability for any
    1.16 + * purpose.
    1.17 + *
    1.18 + */
    1.19 +#include<lemon/invalid.h>
    1.20 +#include <list>
    1.21 +
    1.22 +/// \ingroup gutils
    1.23 +/// \file
    1.24 +/// \brief Euler tour
    1.25 +///
    1.26 +///This file provides an Euler tour iterator and ways to check
    1.27 +///if a graph is euler.
    1.28 +
    1.29 +
    1.30 +namespace lemon {
    1.31 +
    1.32 +  ///Euler iterator in directed graphs.
    1.33 +
    1.34 +  /// \ingroup gutils
    1.35 +  ///This iterator converts to the \c Edge type of the graph and using
    1.36 +  ///the ++ operator it provides an Euler tour of the graph (if there exists).
    1.37 +  ///
    1.38 +  ///For example
    1.39 +  ///if the given graph if Euler (i.e it has only one nontrivial component
    1.40 +  ///and the in-degree is equal to the out-degree for all nodes),
    1.41 +  ///the the following code will print the edge IDs according to an
    1.42 +  ///Euler tour of \c g.
    1.43 +  ///\code
    1.44 +  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
    1.45 +  ///    std::cout << g.id(e) << std::eol;
    1.46 +  ///  }
    1.47 +  ///\endcode
    1.48 +  ///If \c g is not Euler then the resulted tour will not be full or closed.
    1.49 +  ///\todo Test required
    1.50 +  template<class Graph>
    1.51 +  class EulerIt 
    1.52 +  {
    1.53 +    typedef typename Graph::Node Node;
    1.54 +    typedef typename Graph::NodeIt NodeIt;
    1.55 +    typedef typename Graph::Edge Edge;
    1.56 +    typedef typename Graph::EdgeIt EdgeIt;
    1.57 +    typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.58 +    typedef typename Graph::InEdgeIt InEdgeIt;
    1.59 +    
    1.60 +    const Graph &g;
    1.61 +    typename Graph::NodeMap<OutEdgeIt> nedge;
    1.62 +    std::list<Edge> euler;
    1.63 +
    1.64 +  public:
    1.65 +    
    1.66 +    ///Constructor
    1.67 +
    1.68 +    ///\param _g A directed graph.
    1.69 +    ///\param start The starting point of the tour. If it is not given
    1.70 +    ///       tho tour will start from the first node.
    1.71 +    EulerIt(const Graph &_g,typename Graph::Node start=INVALID)
    1.72 +      : g(_g), nedge(g)
    1.73 +    {
    1.74 +      if(start==INVALID) start=NodeIt(g);
    1.75 +      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
    1.76 +      while(nedge[start]!=INVALID) {
    1.77 +	euler.push_back(nedge[start]);
    1.78 +	Node next=g.target(nedge[start]);
    1.79 +	++nedge[start];
    1.80 +	start=next;
    1.81 +      }
    1.82 +    }
    1.83 +    
    1.84 +    ///Edge Conversion
    1.85 +    operator Edge() { return euler.empty()?INVALID:euler.front(); }
    1.86 +    bool operator==(Invalid) { return euler.empty(); }
    1.87 +    bool operator!=(Invalid) { return !euler.empty(); }
    1.88 +    
    1.89 +    ///Next edge of the tour
    1.90 +    EulerIt &operator++() {
    1.91 +      Node s=g.target(euler.front());
    1.92 +      euler.pop_front();
    1.93 +      //This produces a warning.Strange.
    1.94 +      //std::list<Edge>::iterator next=euler.begin();
    1.95 +      typename std::list<Edge>::iterator next=euler.begin();
    1.96 +      while(nedge[s]!=INVALID) {
    1.97 +	euler.insert(next,nedge[s]);
    1.98 +	Node n=g.target(nedge[s]);
    1.99 +	++nedge[s];
   1.100 +	s=n;
   1.101 +      }
   1.102 +      return *this;
   1.103 +    }
   1.104 +    ///Postfix incrementation
   1.105 +    
   1.106 +    ///\warning This gives back an Edge, not an EulerIt!
   1.107 +    ///\todo Is this what we want?
   1.108 +    Edge operator++(int) 
   1.109 +    {
   1.110 +      Edge e=*this;
   1.111 +      ++(*this);
   1.112 +      return e;
   1.113 +    }
   1.114 +  };
   1.115 +
   1.116 +  ///Checks if the graph is Euler
   1.117 +
   1.118 +  /// \ingroup gutils
   1.119 +  ///Checks if the graph is Euler. It works for both directed and
   1.120 +  ///undirected graphs.
   1.121 +  ///\todo What to do with the isolated points?
   1.122 +  ///\todo Test required
   1.123 +  template<class Graph>
   1.124 +#ifdef DOXYGEN
   1.125 +  bool
   1.126 +#else
   1.127 +  typename enable_if<typename Graph::UndirTag,bool>::type
   1.128 +#endif
   1.129 +  euler(const Graph &g) 
   1.130 +  {
   1.131 +    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
   1.132 +      if(countIncEdges(g,n)%2) return false;
   1.133 +    return true;
   1.134 +  }
   1.135 +  template<class Graph>
   1.136 +  typename disable_if<typename Graph::UndirTag,bool>::type
   1.137 +  isEuler(const Graph &g) 
   1.138 +  {
   1.139 +    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
   1.140 +      if(countInEdges(g,n)!=countOutEdges(g,n)) return false;
   1.141 +    return true;
   1.142 +  }
   1.143 +  
   1.144 +}