lemon/euler.h
changeset 520 42d4b889903a
child 521 3af83b6be1df
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/euler.h	Mon Feb 23 11:30:15 2009 +0000
     1.3 @@ -0,0 +1,267 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2009
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#ifndef LEMON_EULER_H
    1.23 +#define LEMON_EULER_H
    1.24 +
    1.25 +#include<lemon/core.h>
    1.26 +#include<lemon/adaptors.h>
    1.27 +#include<lemon/connectivity.h>
    1.28 +#include <list>
    1.29 +
    1.30 +/// \ingroup graph_prop
    1.31 +/// \file
    1.32 +/// \brief Euler tour
    1.33 +///
    1.34 +///This file provides an Euler tour iterator and ways to check
    1.35 +///if a digraph is euler.
    1.36 +
    1.37 +
    1.38 +namespace lemon {
    1.39 +
    1.40 +  ///Euler iterator for digraphs.
    1.41 +
    1.42 +  /// \ingroup graph_prop
    1.43 +  ///This iterator converts to the \c Arc type of the digraph and using
    1.44 +  ///operator ++, it provides an Euler tour of a \e directed
    1.45 +  ///graph (if there exists).
    1.46 +  ///
    1.47 +  ///For example
    1.48 +  ///if the given digraph is Euler (i.e it has only one nontrivial component
    1.49 +  ///and the in-degree is equal to the out-degree for all nodes),
    1.50 +  ///the following code will put the arcs of \c g
    1.51 +  ///to the vector \c et according to an
    1.52 +  ///Euler tour of \c g.
    1.53 +  ///\code
    1.54 +  ///  std::vector<ListDigraph::Arc> et;
    1.55 +  ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
    1.56 +  ///    et.push_back(e);
    1.57 +  ///\endcode
    1.58 +  ///If \c g is not Euler then the resulted tour will not be full or closed.
    1.59 +  ///\sa EulerIt
    1.60 +  ///\todo Test required
    1.61 +  template<class Digraph>
    1.62 +  class DiEulerIt
    1.63 +  {
    1.64 +    typedef typename Digraph::Node Node;
    1.65 +    typedef typename Digraph::NodeIt NodeIt;
    1.66 +    typedef typename Digraph::Arc Arc;
    1.67 +    typedef typename Digraph::ArcIt ArcIt;
    1.68 +    typedef typename Digraph::OutArcIt OutArcIt;
    1.69 +    typedef typename Digraph::InArcIt InArcIt;
    1.70 +
    1.71 +    const Digraph &g;
    1.72 +    typename Digraph::template NodeMap<OutArcIt> nedge;
    1.73 +    std::list<Arc> euler;
    1.74 +
    1.75 +  public:
    1.76 +
    1.77 +    ///Constructor
    1.78 +
    1.79 +    ///\param _g A digraph.
    1.80 +    ///\param start The starting point of the tour. If it is not given
    1.81 +    ///       the tour will start from the first node.
    1.82 +    DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
    1.83 +      : g(_g), nedge(g)
    1.84 +    {
    1.85 +      if(start==INVALID) start=NodeIt(g);
    1.86 +      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
    1.87 +      while(nedge[start]!=INVALID) {
    1.88 +        euler.push_back(nedge[start]);
    1.89 +        Node next=g.target(nedge[start]);
    1.90 +        ++nedge[start];
    1.91 +        start=next;
    1.92 +      }
    1.93 +    }
    1.94 +
    1.95 +    ///Arc Conversion
    1.96 +    operator Arc() { return euler.empty()?INVALID:euler.front(); }
    1.97 +    bool operator==(Invalid) { return euler.empty(); }
    1.98 +    bool operator!=(Invalid) { return !euler.empty(); }
    1.99 +
   1.100 +    ///Next arc of the tour
   1.101 +    DiEulerIt &operator++() {
   1.102 +      Node s=g.target(euler.front());
   1.103 +      euler.pop_front();
   1.104 +      //This produces a warning.Strange.
   1.105 +      //std::list<Arc>::iterator next=euler.begin();
   1.106 +      typename std::list<Arc>::iterator next=euler.begin();
   1.107 +      while(nedge[s]!=INVALID) {
   1.108 +        euler.insert(next,nedge[s]);
   1.109 +        Node n=g.target(nedge[s]);
   1.110 +        ++nedge[s];
   1.111 +        s=n;
   1.112 +      }
   1.113 +      return *this;
   1.114 +    }
   1.115 +    ///Postfix incrementation
   1.116 +
   1.117 +    ///\warning This incrementation
   1.118 +    ///returns an \c Arc, not an \ref DiEulerIt, as one may
   1.119 +    ///expect.
   1.120 +    Arc operator++(int)
   1.121 +    {
   1.122 +      Arc e=*this;
   1.123 +      ++(*this);
   1.124 +      return e;
   1.125 +    }
   1.126 +  };
   1.127 +
   1.128 +  ///Euler iterator for graphs.
   1.129 +
   1.130 +  /// \ingroup graph_prop
   1.131 +  ///This iterator converts to the \c Arc (or \c Edge)
   1.132 +  ///type of the digraph and using
   1.133 +  ///operator ++, it provides an Euler tour of an undirected
   1.134 +  ///digraph (if there exists).
   1.135 +  ///
   1.136 +  ///For example
   1.137 +  ///if the given digraph if Euler (i.e it has only one nontrivial component
   1.138 +  ///and the degree of each node is even),
   1.139 +  ///the following code will print the arc IDs according to an
   1.140 +  ///Euler tour of \c g.
   1.141 +  ///\code
   1.142 +  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
   1.143 +  ///    std::cout << g.id(Edge(e)) << std::eol;
   1.144 +  ///  }
   1.145 +  ///\endcode
   1.146 +  ///Although the iterator provides an Euler tour of an graph,
   1.147 +  ///it still returns Arcs in order to indicate the direction of the tour.
   1.148 +  ///(But Arc will convert to Edges, of course).
   1.149 +  ///
   1.150 +  ///If \c g is not Euler then the resulted tour will not be full or closed.
   1.151 +  ///\sa EulerIt
   1.152 +  ///\todo Test required
   1.153 +  template<class Digraph>
   1.154 +  class EulerIt
   1.155 +  {
   1.156 +    typedef typename Digraph::Node Node;
   1.157 +    typedef typename Digraph::NodeIt NodeIt;
   1.158 +    typedef typename Digraph::Arc Arc;
   1.159 +    typedef typename Digraph::Edge Edge;
   1.160 +    typedef typename Digraph::ArcIt ArcIt;
   1.161 +    typedef typename Digraph::OutArcIt OutArcIt;
   1.162 +    typedef typename Digraph::InArcIt InArcIt;
   1.163 +
   1.164 +    const Digraph &g;
   1.165 +    typename Digraph::template NodeMap<OutArcIt> nedge;
   1.166 +    typename Digraph::template EdgeMap<bool> visited;
   1.167 +    std::list<Arc> euler;
   1.168 +
   1.169 +  public:
   1.170 +
   1.171 +    ///Constructor
   1.172 +
   1.173 +    ///\param _g An graph.
   1.174 +    ///\param start The starting point of the tour. If it is not given
   1.175 +    ///       the tour will start from the first node.
   1.176 +    EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
   1.177 +      : g(_g), nedge(g), visited(g,false)
   1.178 +    {
   1.179 +      if(start==INVALID) start=NodeIt(g);
   1.180 +      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
   1.181 +      while(nedge[start]!=INVALID) {
   1.182 +        euler.push_back(nedge[start]);
   1.183 +        visited[nedge[start]]=true;
   1.184 +        Node next=g.target(nedge[start]);
   1.185 +        ++nedge[start];
   1.186 +        start=next;
   1.187 +        while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
   1.188 +      }
   1.189 +    }
   1.190 +
   1.191 +    ///Arc Conversion
   1.192 +    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
   1.193 +    ///Arc Conversion
   1.194 +    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
   1.195 +    ///\e
   1.196 +    bool operator==(Invalid) const { return euler.empty(); }
   1.197 +    ///\e
   1.198 +    bool operator!=(Invalid) const { return !euler.empty(); }
   1.199 +
   1.200 +    ///Next arc of the tour
   1.201 +    EulerIt &operator++() {
   1.202 +      Node s=g.target(euler.front());
   1.203 +      euler.pop_front();
   1.204 +      typename std::list<Arc>::iterator next=euler.begin();
   1.205 +
   1.206 +      while(nedge[s]!=INVALID) {
   1.207 +        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
   1.208 +        if(nedge[s]==INVALID) break;
   1.209 +        else {
   1.210 +          euler.insert(next,nedge[s]);
   1.211 +          visited[nedge[s]]=true;
   1.212 +          Node n=g.target(nedge[s]);
   1.213 +          ++nedge[s];
   1.214 +          s=n;
   1.215 +        }
   1.216 +      }
   1.217 +      return *this;
   1.218 +    }
   1.219 +
   1.220 +    ///Postfix incrementation
   1.221 +
   1.222 +    ///\warning This incrementation
   1.223 +    ///returns an \c Arc, not an \ref EulerIt, as one may
   1.224 +    ///expect.
   1.225 +    Arc operator++(int)
   1.226 +    {
   1.227 +      Arc e=*this;
   1.228 +      ++(*this);
   1.229 +      return e;
   1.230 +    }
   1.231 +  };
   1.232 +
   1.233 +
   1.234 +  ///Checks if the graph is Euler
   1.235 +
   1.236 +  /// \ingroup graph_prop
   1.237 +  ///Checks if the graph is Euler. It works for both directed and undirected
   1.238 +  ///graphs.
   1.239 +  ///\note By definition, a digraph is called \e Euler if
   1.240 +  ///and only if it is connected and the number of its incoming and outgoing
   1.241 +  ///arcs are the same for each node.
   1.242 +  ///Similarly, an undirected graph is called \e Euler if
   1.243 +  ///and only if it is connected and the number of incident arcs is even
   1.244 +  ///for each node. <em>Therefore, there are digraphs which are not Euler, but
   1.245 +  ///still have an Euler tour</em>.
   1.246 +  ///\todo Test required
   1.247 +  template<class Digraph>
   1.248 +#ifdef DOXYGEN
   1.249 +  bool
   1.250 +#else
   1.251 +  typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
   1.252 +  euler(const Digraph &g)
   1.253 +  {
   1.254 +    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
   1.255 +      if(countIncEdges(g,n)%2) return false;
   1.256 +    return connected(g);
   1.257 +  }
   1.258 +  template<class Digraph>
   1.259 +  typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
   1.260 +#endif
   1.261 +  euler(const Digraph &g)
   1.262 +  {
   1.263 +    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
   1.264 +      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
   1.265 +    return connected(Undirector<const Digraph>(g));
   1.266 +  }
   1.267 +
   1.268 +}
   1.269 +
   1.270 +#endif