lemon/euler.h
changeset 592 2ebfdb89ec66
parent 591 493533ead9df
child 648 4ff8041e9c2e
     1.1 --- a/lemon/euler.h	Wed Apr 15 11:41:25 2009 +0200
     1.2 +++ b/lemon/euler.h	Wed Apr 15 11:47:19 2009 +0200
     1.3 @@ -26,33 +26,31 @@
     1.4  
     1.5  /// \ingroup graph_properties
     1.6  /// \file
     1.7 -/// \brief Euler tour
     1.8 +/// \brief Euler tour iterators and a function for checking the \e Eulerian 
     1.9 +/// property.
    1.10  ///
    1.11 -///This file provides an Euler tour iterator and ways to check
    1.12 -///if a digraph is euler.
    1.13 -
    1.14 +///This file provides Euler tour iterators and a function to check
    1.15 +///if a (di)graph is \e Eulerian.
    1.16  
    1.17  namespace lemon {
    1.18  
    1.19 -  ///Euler iterator for digraphs.
    1.20 +  ///Euler tour iterator for digraphs.
    1.21  
    1.22 -  /// \ingroup graph_properties
    1.23 -  ///This iterator converts to the \c Arc type of the digraph and using
    1.24 -  ///operator ++, it provides an Euler tour of a \e directed
    1.25 -  ///graph (if there exists).
    1.26 +  /// \ingroup graph_prop
    1.27 +  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
    1.28 +  ///graph (if there exists) and it converts to the \c Arc type of the digraph.
    1.29    ///
    1.30 -  ///For example
    1.31 -  ///if the given digraph is Euler (i.e it has only one nontrivial component
    1.32 -  ///and the in-degree is equal to the out-degree for all nodes),
    1.33 -  ///the following code will put the arcs of \c g
    1.34 -  ///to the vector \c et according to an
    1.35 -  ///Euler tour of \c g.
    1.36 +  ///For example, if the given digraph has an Euler tour (i.e it has only one
    1.37 +  ///non-trivial component and the in-degree is equal to the out-degree 
    1.38 +  ///for all nodes), then the following code will put the arcs of \c g
    1.39 +  ///to the vector \c et according to an Euler tour of \c g.
    1.40    ///\code
    1.41    ///  std::vector<ListDigraph::Arc> et;
    1.42 -  ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
    1.43 +  ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
    1.44    ///    et.push_back(e);
    1.45    ///\endcode
    1.46 -  ///If \c g is not Euler then the resulted tour will not be full or closed.
    1.47 +  ///If \c g has no Euler tour, then the resulted walk will not be closed
    1.48 +  ///or not contain all arcs.
    1.49    ///\sa EulerIt
    1.50    template<typename GR>
    1.51    class DiEulerIt
    1.52 @@ -65,18 +63,19 @@
    1.53      typedef typename GR::InArcIt InArcIt;
    1.54  
    1.55      const GR &g;
    1.56 -    typename GR::template NodeMap<OutArcIt> nedge;
    1.57 +    typename GR::template NodeMap<OutArcIt> narc;
    1.58      std::list<Arc> euler;
    1.59  
    1.60    public:
    1.61  
    1.62      ///Constructor
    1.63  
    1.64 +    ///Constructor.
    1.65      ///\param gr A digraph.
    1.66 -    ///\param start The starting point of the tour. If it is not given
    1.67 -    ///       the tour will start from the first node.
    1.68 +    ///\param start The starting point of the tour. If it is not given,
    1.69 +    ///the tour will start from the first node that has an outgoing arc.
    1.70      DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
    1.71 -      : g(gr), nedge(g)
    1.72 +      : g(gr), narc(g)
    1.73      {
    1.74        if (start==INVALID) {
    1.75          NodeIt n(g);
    1.76 @@ -84,40 +83,45 @@
    1.77          start=n;
    1.78        }
    1.79        if (start!=INVALID) {
    1.80 -        for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
    1.81 -        while (nedge[start]!=INVALID) {
    1.82 -          euler.push_back(nedge[start]);
    1.83 -          Node next=g.target(nedge[start]);
    1.84 -          ++nedge[start];
    1.85 +        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
    1.86 +        while (narc[start]!=INVALID) {
    1.87 +          euler.push_back(narc[start]);
    1.88 +          Node next=g.target(narc[start]);
    1.89 +          ++narc[start];
    1.90            start=next;
    1.91          }
    1.92        }
    1.93      }
    1.94  
    1.95 -    ///Arc Conversion
    1.96 +    ///Arc conversion
    1.97      operator Arc() { return euler.empty()?INVALID:euler.front(); }
    1.98 +    ///Compare with \c INVALID
    1.99      bool operator==(Invalid) { return euler.empty(); }
   1.100 +    ///Compare with \c INVALID
   1.101      bool operator!=(Invalid) { return !euler.empty(); }
   1.102  
   1.103      ///Next arc of the tour
   1.104 +
   1.105 +    ///Next arc of the tour
   1.106 +    ///
   1.107      DiEulerIt &operator++() {
   1.108        Node s=g.target(euler.front());
   1.109        euler.pop_front();
   1.110 -      //This produces a warning.Strange.
   1.111 -      //std::list<Arc>::iterator next=euler.begin();
   1.112        typename std::list<Arc>::iterator next=euler.begin();
   1.113 -      while(nedge[s]!=INVALID) {
   1.114 -        euler.insert(next,nedge[s]);
   1.115 -        Node n=g.target(nedge[s]);
   1.116 -        ++nedge[s];
   1.117 +      while(narc[s]!=INVALID) {
   1.118 +        euler.insert(next,narc[s]);
   1.119 +        Node n=g.target(narc[s]);
   1.120 +        ++narc[s];
   1.121          s=n;
   1.122        }
   1.123        return *this;
   1.124      }
   1.125      ///Postfix incrementation
   1.126  
   1.127 +    /// Postfix incrementation.
   1.128 +    ///
   1.129      ///\warning This incrementation
   1.130 -    ///returns an \c Arc, not an \ref DiEulerIt, as one may
   1.131 +    ///returns an \c Arc, not a \ref DiEulerIt, as one may
   1.132      ///expect.
   1.133      Arc operator++(int)
   1.134      {
   1.135 @@ -127,30 +131,28 @@
   1.136      }
   1.137    };
   1.138  
   1.139 -  ///Euler iterator for graphs.
   1.140 +  ///Euler tour iterator for graphs.
   1.141  
   1.142    /// \ingroup graph_properties
   1.143 -  ///This iterator converts to the \c Arc (or \c Edge)
   1.144 -  ///type of the digraph and using
   1.145 -  ///operator ++, it provides an Euler tour of an undirected
   1.146 -  ///digraph (if there exists).
   1.147 +  ///This iterator provides an Euler tour (Eulerian circuit) of an
   1.148 +  ///\e undirected graph (if there exists) and it converts to the \c Arc
   1.149 +  ///and \c Edge types of the graph.
   1.150    ///
   1.151 -  ///For example
   1.152 -  ///if the given digraph if Euler (i.e it has only one nontrivial component
   1.153 -  ///and the degree of each node is even),
   1.154 +  ///For example, if the given graph has an Euler tour (i.e it has only one 
   1.155 +  ///non-trivial component and the degree of each node is even),
   1.156    ///the following code will print the arc IDs according to an
   1.157    ///Euler tour of \c g.
   1.158    ///\code
   1.159 -  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
   1.160 +  ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
   1.161    ///    std::cout << g.id(Edge(e)) << std::eol;
   1.162    ///  }
   1.163    ///\endcode
   1.164 -  ///Although the iterator provides an Euler tour of an graph,
   1.165 -  ///it still returns Arcs in order to indicate the direction of the tour.
   1.166 -  ///(But Arc will convert to Edges, of course).
   1.167 +  ///Although this iterator is for undirected graphs, it still returns 
   1.168 +  ///arcs in order to indicate the direction of the tour.
   1.169 +  ///(But arcs convert to edges, of course.)
   1.170    ///
   1.171 -  ///If \c g is not Euler then the resulted tour will not be full or closed.
   1.172 -  ///\sa EulerIt
   1.173 +  ///If \c g has no Euler tour, then the resulted walk will not be closed
   1.174 +  ///or not contain all edges.
   1.175    template<typename GR>
   1.176    class EulerIt
   1.177    {
   1.178 @@ -163,7 +165,7 @@
   1.179      typedef typename GR::InArcIt InArcIt;
   1.180  
   1.181      const GR &g;
   1.182 -    typename GR::template NodeMap<OutArcIt> nedge;
   1.183 +    typename GR::template NodeMap<OutArcIt> narc;
   1.184      typename GR::template EdgeMap<bool> visited;
   1.185      std::list<Arc> euler;
   1.186  
   1.187 @@ -171,11 +173,12 @@
   1.188  
   1.189      ///Constructor
   1.190  
   1.191 -    ///\param gr An graph.
   1.192 -    ///\param start The starting point of the tour. If it is not given
   1.193 -    ///       the tour will start from the first node.
   1.194 +    ///Constructor.
   1.195 +    ///\param gr A graph.
   1.196 +    ///\param start The starting point of the tour. If it is not given,
   1.197 +    ///the tour will start from the first node that has an incident edge.
   1.198      EulerIt(const GR &gr, typename GR::Node start = INVALID)
   1.199 -      : g(gr), nedge(g), visited(g, false)
   1.200 +      : g(gr), narc(g), visited(g, false)
   1.201      {
   1.202        if (start==INVALID) {
   1.203          NodeIt n(g);
   1.204 @@ -183,41 +186,43 @@
   1.205          start=n;
   1.206        }
   1.207        if (start!=INVALID) {
   1.208 -        for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);
   1.209 -        while(nedge[start]!=INVALID) {
   1.210 -          euler.push_back(nedge[start]);
   1.211 -          visited[nedge[start]]=true;
   1.212 -          Node next=g.target(nedge[start]);
   1.213 -          ++nedge[start];
   1.214 +        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
   1.215 +        while(narc[start]!=INVALID) {
   1.216 +          euler.push_back(narc[start]);
   1.217 +          visited[narc[start]]=true;
   1.218 +          Node next=g.target(narc[start]);
   1.219 +          ++narc[start];
   1.220            start=next;
   1.221 -          while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
   1.222 +          while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
   1.223          }
   1.224        }
   1.225      }
   1.226  
   1.227 -    ///Arc Conversion
   1.228 +    ///Arc conversion
   1.229      operator Arc() const { return euler.empty()?INVALID:euler.front(); }
   1.230 -    ///Arc Conversion
   1.231 +    ///Edge conversion
   1.232      operator Edge() const { return euler.empty()?INVALID:euler.front(); }
   1.233 -    ///\e
   1.234 +    ///Compare with \c INVALID
   1.235      bool operator==(Invalid) const { return euler.empty(); }
   1.236 -    ///\e
   1.237 +    ///Compare with \c INVALID
   1.238      bool operator!=(Invalid) const { return !euler.empty(); }
   1.239  
   1.240      ///Next arc of the tour
   1.241 +
   1.242 +    ///Next arc of the tour
   1.243 +    ///
   1.244      EulerIt &operator++() {
   1.245        Node s=g.target(euler.front());
   1.246        euler.pop_front();
   1.247        typename std::list<Arc>::iterator next=euler.begin();
   1.248 -
   1.249 -      while(nedge[s]!=INVALID) {
   1.250 -        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
   1.251 -        if(nedge[s]==INVALID) break;
   1.252 +      while(narc[s]!=INVALID) {
   1.253 +        while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
   1.254 +        if(narc[s]==INVALID) break;
   1.255          else {
   1.256 -          euler.insert(next,nedge[s]);
   1.257 -          visited[nedge[s]]=true;
   1.258 -          Node n=g.target(nedge[s]);
   1.259 -          ++nedge[s];
   1.260 +          euler.insert(next,narc[s]);
   1.261 +          visited[narc[s]]=true;
   1.262 +          Node n=g.target(narc[s]);
   1.263 +          ++narc[s];
   1.264            s=n;
   1.265          }
   1.266        }
   1.267 @@ -226,9 +231,10 @@
   1.268  
   1.269      ///Postfix incrementation
   1.270  
   1.271 -    ///\warning This incrementation
   1.272 -    ///returns an \c Arc, not an \ref EulerIt, as one may
   1.273 -    ///expect.
   1.274 +    /// Postfix incrementation.
   1.275 +    ///
   1.276 +    ///\warning This incrementation returns an \c Arc (which converts to 
   1.277 +    ///an \c Edge), not an \ref EulerIt, as one may expect.
   1.278      Arc operator++(int)
   1.279      {
   1.280        Arc e=*this;
   1.281 @@ -238,18 +244,23 @@
   1.282    };
   1.283  
   1.284  
   1.285 -  ///Checks if the graph is Eulerian
   1.286 +  ///Check if the given graph is \e Eulerian
   1.287  
   1.288    /// \ingroup graph_properties
   1.289 -  ///Checks if the graph is Eulerian. It works for both directed and undirected
   1.290 -  ///graphs.
   1.291 -  ///\note By definition, a digraph is called \e Eulerian if
   1.292 -  ///and only if it is connected and the number of its incoming and outgoing
   1.293 +  ///This function checks if the given graph is \e Eulerian.
   1.294 +  ///It works for both directed and undirected graphs.
   1.295 +  ///
   1.296 +  ///By definition, a digraph is called \e Eulerian if
   1.297 +  ///and only if it is connected and the number of incoming and outgoing
   1.298    ///arcs are the same for each node.
   1.299    ///Similarly, an undirected graph is called \e Eulerian if
   1.300 -  ///and only if it is connected and the number of incident arcs is even
   1.301 -  ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
   1.302 -  ///but still have an Euler tour</em>.
   1.303 +  ///and only if it is connected and the number of incident edges is even
   1.304 +  ///for each node.
   1.305 +  ///
   1.306 +  ///\note There are (di)graphs that are not Eulerian, but still have an
   1.307 +  /// Euler tour, since they may contain isolated nodes.
   1.308 +  ///
   1.309 +  ///\sa DiEulerIt, EulerIt
   1.310    template<typename GR>
   1.311  #ifdef DOXYGEN
   1.312    bool
   1.313 @@ -268,7 +279,7 @@
   1.314    {
   1.315      for(typename GR::NodeIt n(g);n!=INVALID;++n)
   1.316        if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
   1.317 -    return connected(Undirector<const GR>(g));
   1.318 +    return connected(undirector(g));
   1.319    }
   1.320  
   1.321  }