Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Sat, 18 Apr 2009 08:51:54 +0100
changeset 58716d7255a6849
parent 586 d657c71db7db
parent 584 2ebfdb89ec66
child 592 0ba8dfce7259
Merge
     1.1 --- a/lemon/euler.h	Fri Apr 17 09:58:50 2009 +0200
     1.2 +++ b/lemon/euler.h	Sat Apr 18 08:51:54 2009 +0100
     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,53 +63,65 @@
    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) start=NodeIt(g);
    1.75 -      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(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 +      if (start==INVALID) {
    1.82 +        NodeIt n(g);
    1.83 +        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
    1.84 +        start=n;
    1.85 +      }
    1.86 +      if (start!=INVALID) {
    1.87 +        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
    1.88 +        while (narc[start]!=INVALID) {
    1.89 +          euler.push_back(narc[start]);
    1.90 +          Node next=g.target(narc[start]);
    1.91 +          ++narc[start];
    1.92 +          start=next;
    1.93 +        }
    1.94        }
    1.95      }
    1.96  
    1.97 -    ///Arc Conversion
    1.98 +    ///Arc conversion
    1.99      operator Arc() { return euler.empty()?INVALID:euler.front(); }
   1.100 +    ///Compare with \c INVALID
   1.101      bool operator==(Invalid) { return euler.empty(); }
   1.102 +    ///Compare with \c INVALID
   1.103      bool operator!=(Invalid) { return !euler.empty(); }
   1.104  
   1.105      ///Next arc of the tour
   1.106 +
   1.107 +    ///Next arc of the tour
   1.108 +    ///
   1.109      DiEulerIt &operator++() {
   1.110        Node s=g.target(euler.front());
   1.111        euler.pop_front();
   1.112 -      //This produces a warning.Strange.
   1.113 -      //std::list<Arc>::iterator next=euler.begin();
   1.114        typename std::list<Arc>::iterator next=euler.begin();
   1.115 -      while(nedge[s]!=INVALID) {
   1.116 -        euler.insert(next,nedge[s]);
   1.117 -        Node n=g.target(nedge[s]);
   1.118 -        ++nedge[s];
   1.119 +      while(narc[s]!=INVALID) {
   1.120 +        euler.insert(next,narc[s]);
   1.121 +        Node n=g.target(narc[s]);
   1.122 +        ++narc[s];
   1.123          s=n;
   1.124        }
   1.125        return *this;
   1.126      }
   1.127      ///Postfix incrementation
   1.128  
   1.129 +    /// Postfix incrementation.
   1.130 +    ///
   1.131      ///\warning This incrementation
   1.132 -    ///returns an \c Arc, not an \ref DiEulerIt, as one may
   1.133 +    ///returns an \c Arc, not a \ref DiEulerIt, as one may
   1.134      ///expect.
   1.135      Arc operator++(int)
   1.136      {
   1.137 @@ -121,30 +131,28 @@
   1.138      }
   1.139    };
   1.140  
   1.141 -  ///Euler iterator for graphs.
   1.142 +  ///Euler tour iterator for graphs.
   1.143  
   1.144    /// \ingroup graph_properties
   1.145 -  ///This iterator converts to the \c Arc (or \c Edge)
   1.146 -  ///type of the digraph and using
   1.147 -  ///operator ++, it provides an Euler tour of an undirected
   1.148 -  ///digraph (if there exists).
   1.149 +  ///This iterator provides an Euler tour (Eulerian circuit) of an
   1.150 +  ///\e undirected graph (if there exists) and it converts to the \c Arc
   1.151 +  ///and \c Edge types of the graph.
   1.152    ///
   1.153 -  ///For example
   1.154 -  ///if the given digraph if Euler (i.e it has only one nontrivial component
   1.155 -  ///and the degree of each node is even),
   1.156 +  ///For example, if the given graph has an Euler tour (i.e it has only one 
   1.157 +  ///non-trivial component and the degree of each node is even),
   1.158    ///the following code will print the arc IDs according to an
   1.159    ///Euler tour of \c g.
   1.160    ///\code
   1.161 -  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {
   1.162 +  ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
   1.163    ///    std::cout << g.id(Edge(e)) << std::eol;
   1.164    ///  }
   1.165    ///\endcode
   1.166 -  ///Although the iterator provides an Euler tour of an graph,
   1.167 -  ///it still returns Arcs in order to indicate the direction of the tour.
   1.168 -  ///(But Arc will convert to Edges, of course).
   1.169 +  ///Although this iterator is for undirected graphs, it still returns 
   1.170 +  ///arcs in order to indicate the direction of the tour.
   1.171 +  ///(But arcs convert to edges, of course.)
   1.172    ///
   1.173 -  ///If \c g is not Euler then the resulted tour will not be full or closed.
   1.174 -  ///\sa EulerIt
   1.175 +  ///If \c g has no Euler tour, then the resulted walk will not be closed
   1.176 +  ///or not contain all edges.
   1.177    template<typename GR>
   1.178    class EulerIt
   1.179    {
   1.180 @@ -157,7 +165,7 @@
   1.181      typedef typename GR::InArcIt InArcIt;
   1.182  
   1.183      const GR &g;
   1.184 -    typename GR::template NodeMap<OutArcIt> nedge;
   1.185 +    typename GR::template NodeMap<OutArcIt> narc;
   1.186      typename GR::template EdgeMap<bool> visited;
   1.187      std::list<Arc> euler;
   1.188  
   1.189 @@ -165,47 +173,56 @@
   1.190  
   1.191      ///Constructor
   1.192  
   1.193 -    ///\param gr An graph.
   1.194 -    ///\param start The starting point of the tour. If it is not given
   1.195 -    ///       the tour will start from the first node.
   1.196 +    ///Constructor.
   1.197 +    ///\param gr A graph.
   1.198 +    ///\param start The starting point of the tour. If it is not given,
   1.199 +    ///the tour will start from the first node that has an incident edge.
   1.200      EulerIt(const GR &gr, typename GR::Node start = INVALID)
   1.201 -      : g(gr), nedge(g), visited(g, false)
   1.202 +      : g(gr), narc(g), visited(g, false)
   1.203      {
   1.204 -      if(start==INVALID) start=NodeIt(g);
   1.205 -      for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
   1.206 -      while(nedge[start]!=INVALID) {
   1.207 -        euler.push_back(nedge[start]);
   1.208 -        visited[nedge[start]]=true;
   1.209 -        Node next=g.target(nedge[start]);
   1.210 -        ++nedge[start];
   1.211 -        start=next;
   1.212 -        while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
   1.213 +      if (start==INVALID) {
   1.214 +        NodeIt n(g);
   1.215 +        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
   1.216 +        start=n;
   1.217 +      }
   1.218 +      if (start!=INVALID) {
   1.219 +        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
   1.220 +        while(narc[start]!=INVALID) {
   1.221 +          euler.push_back(narc[start]);
   1.222 +          visited[narc[start]]=true;
   1.223 +          Node next=g.target(narc[start]);
   1.224 +          ++narc[start];
   1.225 +          start=next;
   1.226 +          while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
   1.227 +        }
   1.228        }
   1.229      }
   1.230  
   1.231 -    ///Arc Conversion
   1.232 +    ///Arc conversion
   1.233      operator Arc() const { return euler.empty()?INVALID:euler.front(); }
   1.234 -    ///Arc Conversion
   1.235 +    ///Edge conversion
   1.236      operator Edge() const { return euler.empty()?INVALID:euler.front(); }
   1.237 -    ///\e
   1.238 +    ///Compare with \c INVALID
   1.239      bool operator==(Invalid) const { return euler.empty(); }
   1.240 -    ///\e
   1.241 +    ///Compare with \c INVALID
   1.242      bool operator!=(Invalid) const { return !euler.empty(); }
   1.243  
   1.244      ///Next arc of the tour
   1.245 +
   1.246 +    ///Next arc of the tour
   1.247 +    ///
   1.248      EulerIt &operator++() {
   1.249        Node s=g.target(euler.front());
   1.250        euler.pop_front();
   1.251        typename std::list<Arc>::iterator next=euler.begin();
   1.252 -
   1.253 -      while(nedge[s]!=INVALID) {
   1.254 -        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
   1.255 -        if(nedge[s]==INVALID) break;
   1.256 +      while(narc[s]!=INVALID) {
   1.257 +        while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
   1.258 +        if(narc[s]==INVALID) break;
   1.259          else {
   1.260 -          euler.insert(next,nedge[s]);
   1.261 -          visited[nedge[s]]=true;
   1.262 -          Node n=g.target(nedge[s]);
   1.263 -          ++nedge[s];
   1.264 +          euler.insert(next,narc[s]);
   1.265 +          visited[narc[s]]=true;
   1.266 +          Node n=g.target(narc[s]);
   1.267 +          ++narc[s];
   1.268            s=n;
   1.269          }
   1.270        }
   1.271 @@ -214,9 +231,10 @@
   1.272  
   1.273      ///Postfix incrementation
   1.274  
   1.275 -    ///\warning This incrementation
   1.276 -    ///returns an \c Arc, not an \ref EulerIt, as one may
   1.277 -    ///expect.
   1.278 +    /// Postfix incrementation.
   1.279 +    ///
   1.280 +    ///\warning This incrementation returns an \c Arc (which converts to 
   1.281 +    ///an \c Edge), not an \ref EulerIt, as one may expect.
   1.282      Arc operator++(int)
   1.283      {
   1.284        Arc e=*this;
   1.285 @@ -226,18 +244,23 @@
   1.286    };
   1.287  
   1.288  
   1.289 -  ///Checks if the graph is Eulerian
   1.290 +  ///Check if the given graph is \e Eulerian
   1.291  
   1.292    /// \ingroup graph_properties
   1.293 -  ///Checks if the graph is Eulerian. It works for both directed and undirected
   1.294 -  ///graphs.
   1.295 -  ///\note By definition, a digraph is called \e Eulerian if
   1.296 -  ///and only if it is connected and the number of its incoming and outgoing
   1.297 +  ///This function checks if the given graph is \e Eulerian.
   1.298 +  ///It works for both directed and undirected graphs.
   1.299 +  ///
   1.300 +  ///By definition, a digraph is called \e Eulerian if
   1.301 +  ///and only if it is connected and the number of incoming and outgoing
   1.302    ///arcs are the same for each node.
   1.303    ///Similarly, an undirected graph is called \e Eulerian if
   1.304 -  ///and only if it is connected and the number of incident arcs is even
   1.305 -  ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
   1.306 -  ///but still have an Euler tour</em>.
   1.307 +  ///and only if it is connected and the number of incident edges is even
   1.308 +  ///for each node.
   1.309 +  ///
   1.310 +  ///\note There are (di)graphs that are not Eulerian, but still have an
   1.311 +  /// Euler tour, since they may contain isolated nodes.
   1.312 +  ///
   1.313 +  ///\sa DiEulerIt, EulerIt
   1.314    template<typename GR>
   1.315  #ifdef DOXYGEN
   1.316    bool
   1.317 @@ -256,7 +279,7 @@
   1.318    {
   1.319      for(typename GR::NodeIt n(g);n!=INVALID;++n)
   1.320        if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
   1.321 -    return connected(Undirector<const GR>(g));
   1.322 +    return connected(undirector(g));
   1.323    }
   1.324  
   1.325  }
     2.1 --- a/test/euler_test.cc	Fri Apr 17 09:58:50 2009 +0200
     2.2 +++ b/test/euler_test.cc	Sat Apr 18 08:51:54 2009 +0100
     2.3 @@ -18,136 +18,206 @@
     2.4  
     2.5  #include <lemon/euler.h>
     2.6  #include <lemon/list_graph.h>
     2.7 -#include <test/test_tools.h>
     2.8 +#include <lemon/adaptors.h>
     2.9 +#include "test_tools.h"
    2.10  
    2.11  using namespace lemon;
    2.12  
    2.13  template <typename Digraph>
    2.14 -void checkDiEulerIt(const Digraph& g)
    2.15 +void checkDiEulerIt(const Digraph& g,
    2.16 +                    const typename Digraph::Node& start = INVALID)
    2.17  {
    2.18    typename Digraph::template ArcMap<int> visitationNumber(g, 0);
    2.19  
    2.20 -  DiEulerIt<Digraph> e(g);
    2.21 +  DiEulerIt<Digraph> e(g, start);
    2.22 +  if (e == INVALID) return;
    2.23    typename Digraph::Node firstNode = g.source(e);
    2.24    typename Digraph::Node lastNode = g.target(e);
    2.25 +  if (start != INVALID) {
    2.26 +    check(firstNode == start, "checkDiEulerIt: Wrong first node");
    2.27 +  }
    2.28  
    2.29 -  for (; e != INVALID; ++e)
    2.30 -  {
    2.31 -    if (e != INVALID)
    2.32 -    {
    2.33 -      lastNode = g.target(e);
    2.34 -    }
    2.35 +  for (; e != INVALID; ++e) {
    2.36 +    if (e != INVALID) lastNode = g.target(e);
    2.37      ++visitationNumber[e];
    2.38    }
    2.39  
    2.40    check(firstNode == lastNode,
    2.41 -      "checkDiEulerIt: first and last node are not the same");
    2.42 +      "checkDiEulerIt: First and last nodes are not the same");
    2.43  
    2.44    for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
    2.45    {
    2.46      check(visitationNumber[a] == 1,
    2.47 -        "checkDiEulerIt: not visited or multiple times visited arc found");
    2.48 +        "checkDiEulerIt: Not visited or multiple times visited arc found");
    2.49    }
    2.50  }
    2.51  
    2.52  template <typename Graph>
    2.53 -void checkEulerIt(const Graph& g)
    2.54 +void checkEulerIt(const Graph& g,
    2.55 +                  const typename Graph::Node& start = INVALID)
    2.56  {
    2.57    typename Graph::template EdgeMap<int> visitationNumber(g, 0);
    2.58  
    2.59 -  EulerIt<Graph> e(g);
    2.60 -  typename Graph::Node firstNode = g.u(e);
    2.61 -  typename Graph::Node lastNode = g.v(e);
    2.62 +  EulerIt<Graph> e(g, start);
    2.63 +  if (e == INVALID) return;
    2.64 +  typename Graph::Node firstNode = g.source(typename Graph::Arc(e));
    2.65 +  typename Graph::Node lastNode = g.target(typename Graph::Arc(e));
    2.66 +  if (start != INVALID) {
    2.67 +    check(firstNode == start, "checkEulerIt: Wrong first node");
    2.68 +  }
    2.69  
    2.70 -  for (; e != INVALID; ++e)
    2.71 -  {
    2.72 -    if (e != INVALID)
    2.73 -    {
    2.74 -      lastNode = g.v(e);
    2.75 -    }
    2.76 +  for (; e != INVALID; ++e) {
    2.77 +    if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
    2.78      ++visitationNumber[e];
    2.79    }
    2.80  
    2.81    check(firstNode == lastNode,
    2.82 -      "checkEulerIt: first and last node are not the same");
    2.83 +      "checkEulerIt: First and last nodes are not the same");
    2.84  
    2.85    for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
    2.86    {
    2.87      check(visitationNumber[e] == 1,
    2.88 -        "checkEulerIt: not visited or multiple times visited edge found");
    2.89 +        "checkEulerIt: Not visited or multiple times visited edge found");
    2.90    }
    2.91  }
    2.92  
    2.93  int main()
    2.94  {
    2.95    typedef ListDigraph Digraph;
    2.96 -  typedef ListGraph Graph;
    2.97 +  typedef Undirector<Digraph> Graph;
    2.98 +  
    2.99 +  {
   2.100 +    Digraph d;
   2.101 +    Graph g(d);
   2.102 +    
   2.103 +    checkDiEulerIt(d);
   2.104 +    checkDiEulerIt(g);
   2.105 +    checkEulerIt(g);
   2.106  
   2.107 -  Digraph digraphWithEulerianCircuit;
   2.108 +    check(eulerian(d), "This graph is Eulerian");
   2.109 +    check(eulerian(g), "This graph is Eulerian");
   2.110 +  }
   2.111    {
   2.112 -    Digraph& g = digraphWithEulerianCircuit;
   2.113 +    Digraph d;
   2.114 +    Graph g(d);
   2.115 +    Digraph::Node n = d.addNode();
   2.116  
   2.117 -    Digraph::Node n0 = g.addNode();
   2.118 -    Digraph::Node n1 = g.addNode();
   2.119 -    Digraph::Node n2 = g.addNode();
   2.120 +    checkDiEulerIt(d);
   2.121 +    checkDiEulerIt(g);
   2.122 +    checkEulerIt(g);
   2.123  
   2.124 -    g.addArc(n0, n1);
   2.125 -    g.addArc(n1, n0);
   2.126 -    g.addArc(n1, n2);
   2.127 -    g.addArc(n2, n1);
   2.128 +    check(eulerian(d), "This graph is Eulerian");
   2.129 +    check(eulerian(g), "This graph is Eulerian");
   2.130    }
   2.131 +  {
   2.132 +    Digraph d;
   2.133 +    Graph g(d);
   2.134 +    Digraph::Node n = d.addNode();
   2.135 +    d.addArc(n, n);
   2.136  
   2.137 -  Digraph digraphWithoutEulerianCircuit;
   2.138 +    checkDiEulerIt(d);
   2.139 +    checkDiEulerIt(g);
   2.140 +    checkEulerIt(g);
   2.141 +
   2.142 +    check(eulerian(d), "This graph is Eulerian");
   2.143 +    check(eulerian(g), "This graph is Eulerian");
   2.144 +  }
   2.145    {
   2.146 -    Digraph& g = digraphWithoutEulerianCircuit;
   2.147 +    Digraph d;
   2.148 +    Graph g(d);
   2.149 +    Digraph::Node n1 = d.addNode();
   2.150 +    Digraph::Node n2 = d.addNode();
   2.151 +    Digraph::Node n3 = d.addNode();
   2.152 +    
   2.153 +    d.addArc(n1, n2);
   2.154 +    d.addArc(n2, n1);
   2.155 +    d.addArc(n2, n3);
   2.156 +    d.addArc(n3, n2);
   2.157  
   2.158 -    Digraph::Node n0 = g.addNode();
   2.159 -    Digraph::Node n1 = g.addNode();
   2.160 -    Digraph::Node n2 = g.addNode();
   2.161 +    checkDiEulerIt(d);
   2.162 +    checkDiEulerIt(d, n2);
   2.163 +    checkDiEulerIt(g);
   2.164 +    checkDiEulerIt(g, n2);
   2.165 +    checkEulerIt(g);
   2.166 +    checkEulerIt(g, n2);
   2.167  
   2.168 -    g.addArc(n0, n1);
   2.169 -    g.addArc(n1, n0);
   2.170 -    g.addArc(n1, n2);
   2.171 +    check(eulerian(d), "This graph is Eulerian");
   2.172 +    check(eulerian(g), "This graph is Eulerian");
   2.173    }
   2.174 +  {
   2.175 +    Digraph d;
   2.176 +    Graph g(d);
   2.177 +    Digraph::Node n1 = d.addNode();
   2.178 +    Digraph::Node n2 = d.addNode();
   2.179 +    Digraph::Node n3 = d.addNode();
   2.180 +    Digraph::Node n4 = d.addNode();
   2.181 +    Digraph::Node n5 = d.addNode();
   2.182 +    Digraph::Node n6 = d.addNode();
   2.183 +    
   2.184 +    d.addArc(n1, n2);
   2.185 +    d.addArc(n2, n4);
   2.186 +    d.addArc(n1, n3);
   2.187 +    d.addArc(n3, n4);
   2.188 +    d.addArc(n4, n1);
   2.189 +    d.addArc(n3, n5);
   2.190 +    d.addArc(n5, n2);
   2.191 +    d.addArc(n4, n6);
   2.192 +    d.addArc(n2, n6);
   2.193 +    d.addArc(n6, n1);
   2.194 +    d.addArc(n6, n3);
   2.195  
   2.196 -  Graph graphWithEulerianCircuit;
   2.197 +    checkDiEulerIt(d);
   2.198 +    checkDiEulerIt(d, n1);
   2.199 +    checkDiEulerIt(d, n5);
   2.200 +
   2.201 +    checkDiEulerIt(g);
   2.202 +    checkDiEulerIt(g, n1);
   2.203 +    checkDiEulerIt(g, n5);
   2.204 +    checkEulerIt(g);
   2.205 +    checkEulerIt(g, n1);
   2.206 +    checkEulerIt(g, n5);
   2.207 +
   2.208 +    check(eulerian(d), "This graph is Eulerian");
   2.209 +    check(eulerian(g), "This graph is Eulerian");
   2.210 +  }
   2.211    {
   2.212 -    Graph& g = graphWithEulerianCircuit;
   2.213 +    Digraph d;
   2.214 +    Graph g(d);
   2.215 +    Digraph::Node n0 = d.addNode();
   2.216 +    Digraph::Node n1 = d.addNode();
   2.217 +    Digraph::Node n2 = d.addNode();
   2.218 +    Digraph::Node n3 = d.addNode();
   2.219 +    Digraph::Node n4 = d.addNode();
   2.220 +    Digraph::Node n5 = d.addNode();
   2.221 +    
   2.222 +    d.addArc(n1, n2);
   2.223 +    d.addArc(n2, n3);
   2.224 +    d.addArc(n3, n1);
   2.225  
   2.226 -    Graph::Node n0 = g.addNode();
   2.227 -    Graph::Node n1 = g.addNode();
   2.228 -    Graph::Node n2 = g.addNode();
   2.229 +    checkDiEulerIt(d);
   2.230 +    checkDiEulerIt(d, n2);
   2.231  
   2.232 -    g.addEdge(n0, n1);
   2.233 -    g.addEdge(n1, n2);
   2.234 -    g.addEdge(n2, n0);
   2.235 +    checkDiEulerIt(g);
   2.236 +    checkDiEulerIt(g, n2);
   2.237 +    checkEulerIt(g);
   2.238 +    checkEulerIt(g, n2);
   2.239 +
   2.240 +    check(!eulerian(d), "This graph is not Eulerian");
   2.241 +    check(!eulerian(g), "This graph is not Eulerian");
   2.242    }
   2.243 +  {
   2.244 +    Digraph d;
   2.245 +    Graph g(d);
   2.246 +    Digraph::Node n1 = d.addNode();
   2.247 +    Digraph::Node n2 = d.addNode();
   2.248 +    Digraph::Node n3 = d.addNode();
   2.249 +    
   2.250 +    d.addArc(n1, n2);
   2.251 +    d.addArc(n2, n3);
   2.252  
   2.253 -  Graph graphWithoutEulerianCircuit;
   2.254 -  {
   2.255 -    Graph& g = graphWithoutEulerianCircuit;
   2.256 -
   2.257 -    Graph::Node n0 = g.addNode();
   2.258 -    Graph::Node n1 = g.addNode();
   2.259 -    Graph::Node n2 = g.addNode();
   2.260 -
   2.261 -    g.addEdge(n0, n1);
   2.262 -    g.addEdge(n1, n2);
   2.263 +    check(!eulerian(d), "This graph is not Eulerian");
   2.264 +    check(!eulerian(g), "This graph is not Eulerian");
   2.265    }
   2.266  
   2.267 -  checkDiEulerIt(digraphWithEulerianCircuit);
   2.268 -
   2.269 -  checkEulerIt(graphWithEulerianCircuit);
   2.270 -
   2.271 -  check(eulerian(digraphWithEulerianCircuit),
   2.272 -      "this graph should have an Eulerian circuit");
   2.273 -  check(!eulerian(digraphWithoutEulerianCircuit),
   2.274 -      "this graph should not have an Eulerian circuit");
   2.275 -
   2.276 -  check(eulerian(graphWithEulerianCircuit),
   2.277 -      "this graph should have an Eulerian circuit");
   2.278 -  check(!eulerian(graphWithoutEulerianCircuit),
   2.279 -      "this graph should have an Eulerian circuit");
   2.280 -
   2.281    return 0;
   2.282  }