# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1239788839 -7200
# Node ID 2ebfdb89ec66d93511d8510725b6662c018e80e7
# Parent 493533ead9df159b2a1a160663d5aa301fd3711f
Improvements for the Euler tools and the test file (#264)
diff -r 493533ead9df -r 2ebfdb89ec66 lemon/euler.h
--- a/lemon/euler.h Wed Apr 15 11:41:25 2009 +0200
+++ b/lemon/euler.h Wed Apr 15 11:47:19 2009 +0200
@@ -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<ListDigraph::Arc> et;
- /// for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)
+ /// for(DiEulerIt<ListDigraph> 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<typename GR>
class DiEulerIt
@@ -65,18 +63,19 @@
typedef typename GR::InArcIt InArcIt;
const GR &g;
- typename GR::template NodeMap<OutArcIt> nedge;
+ typename GR::template NodeMap<OutArcIt> narc;
std::list<Arc> 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<Arc>::iterator next=euler.begin();
typename std::list<Arc>::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<ListGraph> e(g),e!=INVALID;++e) {
+ /// for(EulerIt<ListGraph> 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<typename GR>
class EulerIt
{
@@ -163,7 +165,7 @@
typedef typename GR::InArcIt InArcIt;
const GR &g;
- typename GR::template NodeMap<OutArcIt> nedge;
+ typename GR::template NodeMap<OutArcIt> narc;
typename GR::template EdgeMap<bool> visited;
std::list<Arc> 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<Arc>::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. <em>Therefore, there are digraphs which are not Eulerian,
- ///but still have an Euler tour</em>.
+ ///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<typename GR>
#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<const GR>(g));
+ return connected(undirector(g));
}
}
diff -r 493533ead9df -r 2ebfdb89ec66 test/euler_test.cc
--- a/test/euler_test.cc Wed Apr 15 11:41:25 2009 +0200
+++ b/test/euler_test.cc Wed Apr 15 11:47:19 2009 +0200
@@ -18,136 +18,206 @@
#include <lemon/euler.h>
#include <lemon/list_graph.h>
-#include <test/test_tools.h>
+#include <lemon/adaptors.h>
+#include "test_tools.h"
using namespace lemon;
template <typename Digraph>
-void checkDiEulerIt(const Digraph& g)
+void checkDiEulerIt(const Digraph& g,
+ const typename Digraph::Node& start = INVALID)
{
typename Digraph::template ArcMap<int> visitationNumber(g, 0);
- DiEulerIt<Digraph> e(g);
+ DiEulerIt<Digraph> 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 <typename Graph>
-void checkEulerIt(const Graph& g)
+void checkEulerIt(const Graph& g,
+ const typename Graph::Node& start = INVALID)
{
typename Graph::template EdgeMap<int> visitationNumber(g, 0);
- EulerIt<Graph> e(g);
- typename Graph::Node firstNode = g.u(e);
- typename Graph::Node lastNode = g.v(e);
+ EulerIt<Graph> 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<Digraph> 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;
}