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 }