author Peter Kovacs Wed, 15 Apr 2009 11:47:19 +0200 changeset 592 2ebfdb89ec66 parent 591 493533ead9df child 595 16d7255a6849
Improvements for the Euler tools and the test file (#264)
 lemon/euler.h file | annotate | diff | comparison | revisions test/euler_test.cc file | annotate | diff | comparison | revisions
     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  }

     2.1 --- a/test/euler_test.cc	Wed Apr 15 11:41:25 2009 +0200
2.2 +++ b/test/euler_test.cc	Wed Apr 15 11:47:19 2009 +0200
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.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.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.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.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.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.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.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.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.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.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  }