diff --git a/lemon/euler.h b/lemon/euler.h --- a/lemon/euler.h +++ b/lemon/euler.h @@ -26,33 +26,31 @@ /// \ingroup graph_properties /// \file -/// \brief Euler tour +/// \brief Euler tour iterators and a function for checking the \e Eulerian +/// property. /// -///This file provides an Euler tour iterator and ways to check -///if a digraph is euler. - +///This file provides Euler tour iterators and a function to check +///if a (di)graph is \e Eulerian. namespace lemon { - ///Euler iterator for digraphs. + ///Euler tour iterator for digraphs. - /// \ingroup graph_properties - ///This iterator converts to the \c Arc type of the digraph and using - ///operator ++, it provides an Euler tour of a \e directed - ///graph (if there exists). + /// \ingroup graph_prop + ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed + ///graph (if there exists) and it converts to the \c Arc type of the digraph. /// - ///For example - ///if the given digraph is Euler (i.e it has only one nontrivial component - ///and the in-degree is equal to the out-degree for all nodes), - ///the following code will put the arcs of \c g - ///to the vector \c et according to an - ///Euler tour of \c g. + ///For example, if the given digraph has an Euler tour (i.e it has only one + ///non-trivial component and the in-degree is equal to the out-degree + ///for all nodes), then the following code will put the arcs of \c g + ///to the vector \c et according to an Euler tour of \c g. ///\code /// std::vector et; - /// for(DiEulerIt e(g),e!=INVALID;++e) + /// for(DiEulerIt e(g); e!=INVALID; ++e) /// et.push_back(e); ///\endcode - ///If \c g is not Euler then the resulted tour will not be full or closed. + ///If \c g has no Euler tour, then the resulted walk will not be closed + ///or not contain all arcs. ///\sa EulerIt template class DiEulerIt @@ -65,18 +63,19 @@ typedef typename GR::InArcIt InArcIt; const GR &g; - typename GR::template NodeMap nedge; + typename GR::template NodeMap narc; std::list euler; public: ///Constructor + ///Constructor. ///\param gr A digraph. - ///\param start The starting point of the tour. If it is not given - /// the tour will start from the first node. + ///\param start The starting point of the tour. If it is not given, + ///the tour will start from the first node that has an outgoing arc. DiEulerIt(const GR &gr, typename GR::Node start = INVALID) - : g(gr), nedge(g) + : g(gr), narc(g) { if (start==INVALID) { NodeIt n(g); @@ -84,40 +83,45 @@ start=n; } if (start!=INVALID) { - for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n); - while (nedge[start]!=INVALID) { - euler.push_back(nedge[start]); - Node next=g.target(nedge[start]); - ++nedge[start]; + for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n); + while (narc[start]!=INVALID) { + euler.push_back(narc[start]); + Node next=g.target(narc[start]); + ++narc[start]; start=next; } } } - ///Arc Conversion + ///Arc conversion operator Arc() { return euler.empty()?INVALID:euler.front(); } + ///Compare with \c INVALID bool operator==(Invalid) { return euler.empty(); } + ///Compare with \c INVALID bool operator!=(Invalid) { return !euler.empty(); } ///Next arc of the tour + + ///Next arc of the tour + /// DiEulerIt &operator++() { Node s=g.target(euler.front()); euler.pop_front(); - //This produces a warning.Strange. - //std::list::iterator next=euler.begin(); typename std::list::iterator next=euler.begin(); - while(nedge[s]!=INVALID) { - euler.insert(next,nedge[s]); - Node n=g.target(nedge[s]); - ++nedge[s]; + while(narc[s]!=INVALID) { + euler.insert(next,narc[s]); + Node n=g.target(narc[s]); + ++narc[s]; s=n; } return *this; } ///Postfix incrementation + /// Postfix incrementation. + /// ///\warning This incrementation - ///returns an \c Arc, not an \ref DiEulerIt, as one may + ///returns an \c Arc, not a \ref DiEulerIt, as one may ///expect. Arc operator++(int) { @@ -127,30 +131,28 @@ } }; - ///Euler iterator for graphs. + ///Euler tour iterator for graphs. /// \ingroup graph_properties - ///This iterator converts to the \c Arc (or \c Edge) - ///type of the digraph and using - ///operator ++, it provides an Euler tour of an undirected - ///digraph (if there exists). + ///This iterator provides an Euler tour (Eulerian circuit) of an + ///\e undirected graph (if there exists) and it converts to the \c Arc + ///and \c Edge types of the graph. /// - ///For example - ///if the given digraph if Euler (i.e it has only one nontrivial component - ///and the degree of each node is even), + ///For example, if the given graph has an Euler tour (i.e it has only one + ///non-trivial component and the degree of each node is even), ///the following code will print the arc IDs according to an ///Euler tour of \c g. ///\code - /// for(EulerIt e(g),e!=INVALID;++e) { + /// for(EulerIt e(g); e!=INVALID; ++e) { /// std::cout << g.id(Edge(e)) << std::eol; /// } ///\endcode - ///Although the iterator provides an Euler tour of an graph, - ///it still returns Arcs in order to indicate the direction of the tour. - ///(But Arc will convert to Edges, of course). + ///Although this iterator is for undirected graphs, it still returns + ///arcs in order to indicate the direction of the tour. + ///(But arcs convert to edges, of course.) /// - ///If \c g is not Euler then the resulted tour will not be full or closed. - ///\sa EulerIt + ///If \c g has no Euler tour, then the resulted walk will not be closed + ///or not contain all edges. template class EulerIt { @@ -163,7 +165,7 @@ typedef typename GR::InArcIt InArcIt; const GR &g; - typename GR::template NodeMap nedge; + typename GR::template NodeMap narc; typename GR::template EdgeMap visited; std::list euler; @@ -171,11 +173,12 @@ ///Constructor - ///\param gr An graph. - ///\param start The starting point of the tour. If it is not given - /// the tour will start from the first node. + ///Constructor. + ///\param gr A graph. + ///\param start The starting point of the tour. If it is not given, + ///the tour will start from the first node that has an incident edge. EulerIt(const GR &gr, typename GR::Node start = INVALID) - : g(gr), nedge(g), visited(g, false) + : g(gr), narc(g), visited(g, false) { if (start==INVALID) { NodeIt n(g); @@ -183,41 +186,43 @@ start=n; } if (start!=INVALID) { - for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n); - while(nedge[start]!=INVALID) { - euler.push_back(nedge[start]); - visited[nedge[start]]=true; - Node next=g.target(nedge[start]); - ++nedge[start]; + for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n); + while(narc[start]!=INVALID) { + euler.push_back(narc[start]); + visited[narc[start]]=true; + Node next=g.target(narc[start]); + ++narc[start]; start=next; - while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; + while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start]; } } } - ///Arc Conversion + ///Arc conversion operator Arc() const { return euler.empty()?INVALID:euler.front(); } - ///Arc Conversion + ///Edge conversion operator Edge() const { return euler.empty()?INVALID:euler.front(); } - ///\e + ///Compare with \c INVALID bool operator==(Invalid) const { return euler.empty(); } - ///\e + ///Compare with \c INVALID bool operator!=(Invalid) const { return !euler.empty(); } ///Next arc of the tour + + ///Next arc of the tour + /// EulerIt &operator++() { Node s=g.target(euler.front()); euler.pop_front(); typename std::list::iterator next=euler.begin(); - - while(nedge[s]!=INVALID) { - while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; - if(nedge[s]==INVALID) break; + while(narc[s]!=INVALID) { + while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s]; + if(narc[s]==INVALID) break; else { - euler.insert(next,nedge[s]); - visited[nedge[s]]=true; - Node n=g.target(nedge[s]); - ++nedge[s]; + euler.insert(next,narc[s]); + visited[narc[s]]=true; + Node n=g.target(narc[s]); + ++narc[s]; s=n; } } @@ -226,9 +231,10 @@ ///Postfix incrementation - ///\warning This incrementation - ///returns an \c Arc, not an \ref EulerIt, as one may - ///expect. + /// Postfix incrementation. + /// + ///\warning This incrementation returns an \c Arc (which converts to + ///an \c Edge), not an \ref EulerIt, as one may expect. Arc operator++(int) { Arc e=*this; @@ -238,18 +244,23 @@ }; - ///Checks if the graph is Eulerian + ///Check if the given graph is \e Eulerian /// \ingroup graph_properties - ///Checks if the graph is Eulerian. It works for both directed and undirected - ///graphs. - ///\note By definition, a digraph is called \e Eulerian if - ///and only if it is connected and the number of its incoming and outgoing + ///This function checks if the given graph is \e Eulerian. + ///It works for both directed and undirected graphs. + /// + ///By definition, a digraph is called \e Eulerian if + ///and only if it is connected and the number of incoming and outgoing ///arcs are the same for each node. ///Similarly, an undirected graph is called \e Eulerian if - ///and only if it is connected and the number of incident arcs is even - ///for each node. Therefore, there are digraphs which are not Eulerian, - ///but still have an Euler tour. + ///and only if it is connected and the number of incident edges is even + ///for each node. + /// + ///\note There are (di)graphs that are not Eulerian, but still have an + /// Euler tour, since they may contain isolated nodes. + /// + ///\sa DiEulerIt, EulerIt template #ifdef DOXYGEN bool @@ -268,7 +279,7 @@ { for(typename GR::NodeIt n(g);n!=INVALID;++n) if(countInArcs(g,n)!=countOutArcs(g,n)) return false; - return connected(Undirector(g)); + return connected(undirector(g)); } } diff --git a/test/euler_test.cc b/test/euler_test.cc --- a/test/euler_test.cc +++ b/test/euler_test.cc @@ -18,136 +18,206 @@ #include #include -#include +#include +#include "test_tools.h" using namespace lemon; template -void checkDiEulerIt(const Digraph& g) +void checkDiEulerIt(const Digraph& g, + const typename Digraph::Node& start = INVALID) { typename Digraph::template ArcMap visitationNumber(g, 0); - DiEulerIt e(g); + DiEulerIt e(g, start); + if (e == INVALID) return; typename Digraph::Node firstNode = g.source(e); typename Digraph::Node lastNode = g.target(e); + if (start != INVALID) { + check(firstNode == start, "checkDiEulerIt: Wrong first node"); + } - for (; e != INVALID; ++e) - { - if (e != INVALID) - { - lastNode = g.target(e); - } + for (; e != INVALID; ++e) { + if (e != INVALID) lastNode = g.target(e); ++visitationNumber[e]; } check(firstNode == lastNode, - "checkDiEulerIt: first and last node are not the same"); + "checkDiEulerIt: First and last nodes are not the same"); for (typename Digraph::ArcIt a(g); a != INVALID; ++a) { check(visitationNumber[a] == 1, - "checkDiEulerIt: not visited or multiple times visited arc found"); + "checkDiEulerIt: Not visited or multiple times visited arc found"); } } template -void checkEulerIt(const Graph& g) +void checkEulerIt(const Graph& g, + const typename Graph::Node& start = INVALID) { typename Graph::template EdgeMap visitationNumber(g, 0); - EulerIt e(g); - typename Graph::Node firstNode = g.u(e); - typename Graph::Node lastNode = g.v(e); + EulerIt e(g, start); + if (e == INVALID) return; + typename Graph::Node firstNode = g.source(typename Graph::Arc(e)); + typename Graph::Node lastNode = g.target(typename Graph::Arc(e)); + if (start != INVALID) { + check(firstNode == start, "checkEulerIt: Wrong first node"); + } - for (; e != INVALID; ++e) - { - if (e != INVALID) - { - lastNode = g.v(e); - } + for (; e != INVALID; ++e) { + if (e != INVALID) lastNode = g.target(typename Graph::Arc(e)); ++visitationNumber[e]; } check(firstNode == lastNode, - "checkEulerIt: first and last node are not the same"); + "checkEulerIt: First and last nodes are not the same"); for (typename Graph::EdgeIt e(g); e != INVALID; ++e) { check(visitationNumber[e] == 1, - "checkEulerIt: not visited or multiple times visited edge found"); + "checkEulerIt: Not visited or multiple times visited edge found"); } } int main() { typedef ListDigraph Digraph; - typedef ListGraph Graph; + typedef Undirector Graph; + + { + Digraph d; + Graph g(d); + + checkDiEulerIt(d); + checkDiEulerIt(g); + checkEulerIt(g); - Digraph digraphWithEulerianCircuit; + check(eulerian(d), "This graph is Eulerian"); + check(eulerian(g), "This graph is Eulerian"); + } { - Digraph& g = digraphWithEulerianCircuit; + Digraph d; + Graph g(d); + Digraph::Node n = d.addNode(); - Digraph::Node n0 = g.addNode(); - Digraph::Node n1 = g.addNode(); - Digraph::Node n2 = g.addNode(); + checkDiEulerIt(d); + checkDiEulerIt(g); + checkEulerIt(g); - g.addArc(n0, n1); - g.addArc(n1, n0); - g.addArc(n1, n2); - g.addArc(n2, n1); + check(eulerian(d), "This graph is Eulerian"); + check(eulerian(g), "This graph is Eulerian"); } + { + Digraph d; + Graph g(d); + Digraph::Node n = d.addNode(); + d.addArc(n, n); - Digraph digraphWithoutEulerianCircuit; + checkDiEulerIt(d); + checkDiEulerIt(g); + checkEulerIt(g); + + check(eulerian(d), "This graph is Eulerian"); + check(eulerian(g), "This graph is Eulerian"); + } { - Digraph& g = digraphWithoutEulerianCircuit; + Digraph d; + Graph g(d); + Digraph::Node n1 = d.addNode(); + Digraph::Node n2 = d.addNode(); + Digraph::Node n3 = d.addNode(); + + d.addArc(n1, n2); + d.addArc(n2, n1); + d.addArc(n2, n3); + d.addArc(n3, n2); - Digraph::Node n0 = g.addNode(); - Digraph::Node n1 = g.addNode(); - Digraph::Node n2 = g.addNode(); + checkDiEulerIt(d); + checkDiEulerIt(d, n2); + checkDiEulerIt(g); + checkDiEulerIt(g, n2); + checkEulerIt(g); + checkEulerIt(g, n2); - g.addArc(n0, n1); - g.addArc(n1, n0); - g.addArc(n1, n2); + check(eulerian(d), "This graph is Eulerian"); + check(eulerian(g), "This graph is Eulerian"); } + { + Digraph d; + Graph g(d); + Digraph::Node n1 = d.addNode(); + Digraph::Node n2 = d.addNode(); + Digraph::Node n3 = d.addNode(); + Digraph::Node n4 = d.addNode(); + Digraph::Node n5 = d.addNode(); + Digraph::Node n6 = d.addNode(); + + d.addArc(n1, n2); + d.addArc(n2, n4); + d.addArc(n1, n3); + d.addArc(n3, n4); + d.addArc(n4, n1); + d.addArc(n3, n5); + d.addArc(n5, n2); + d.addArc(n4, n6); + d.addArc(n2, n6); + d.addArc(n6, n1); + d.addArc(n6, n3); - Graph graphWithEulerianCircuit; + checkDiEulerIt(d); + checkDiEulerIt(d, n1); + checkDiEulerIt(d, n5); + + checkDiEulerIt(g); + checkDiEulerIt(g, n1); + checkDiEulerIt(g, n5); + checkEulerIt(g); + checkEulerIt(g, n1); + checkEulerIt(g, n5); + + check(eulerian(d), "This graph is Eulerian"); + check(eulerian(g), "This graph is Eulerian"); + } { - Graph& g = graphWithEulerianCircuit; + Digraph d; + Graph g(d); + Digraph::Node n0 = d.addNode(); + Digraph::Node n1 = d.addNode(); + Digraph::Node n2 = d.addNode(); + Digraph::Node n3 = d.addNode(); + Digraph::Node n4 = d.addNode(); + Digraph::Node n5 = d.addNode(); + + d.addArc(n1, n2); + d.addArc(n2, n3); + d.addArc(n3, n1); - Graph::Node n0 = g.addNode(); - Graph::Node n1 = g.addNode(); - Graph::Node n2 = g.addNode(); + checkDiEulerIt(d); + checkDiEulerIt(d, n2); - g.addEdge(n0, n1); - g.addEdge(n1, n2); - g.addEdge(n2, n0); + checkDiEulerIt(g); + checkDiEulerIt(g, n2); + checkEulerIt(g); + checkEulerIt(g, n2); + + check(!eulerian(d), "This graph is not Eulerian"); + check(!eulerian(g), "This graph is not Eulerian"); } + { + Digraph d; + Graph g(d); + Digraph::Node n1 = d.addNode(); + Digraph::Node n2 = d.addNode(); + Digraph::Node n3 = d.addNode(); + + d.addArc(n1, n2); + d.addArc(n2, n3); - Graph graphWithoutEulerianCircuit; - { - Graph& g = graphWithoutEulerianCircuit; - - Graph::Node n0 = g.addNode(); - Graph::Node n1 = g.addNode(); - Graph::Node n2 = g.addNode(); - - g.addEdge(n0, n1); - g.addEdge(n1, n2); + check(!eulerian(d), "This graph is not Eulerian"); + check(!eulerian(g), "This graph is not Eulerian"); } - checkDiEulerIt(digraphWithEulerianCircuit); - - checkEulerIt(graphWithEulerianCircuit); - - check(eulerian(digraphWithEulerianCircuit), - "this graph should have an Eulerian circuit"); - check(!eulerian(digraphWithoutEulerianCircuit), - "this graph should not have an Eulerian circuit"); - - check(eulerian(graphWithEulerianCircuit), - "this graph should have an Eulerian circuit"); - check(!eulerian(graphWithoutEulerianCircuit), - "this graph should have an Eulerian circuit"); - return 0; }