# HG changeset patch # User Akos Ladanyi # Date 1225713594 0 # Node ID 22f932bbb3051c81efbbd0d3a5e70d5e47547610 # Parent 3af83b6be1df1c4d7a3da1bb927221b375259338 Test for euler.h (#65) diff -r 3af83b6be1df -r 22f932bbb305 lemon/Makefile.am --- a/lemon/Makefile.am Mon Feb 23 11:30:15 2009 +0000 +++ b/lemon/Makefile.am Mon Nov 03 11:59:54 2008 +0000 @@ -54,6 +54,7 @@ lemon/clp.h \ lemon/color.h \ lemon/concept_check.h \ + lemon/connectivity.h \ lemon/counter.h \ lemon/core.h \ lemon/cplex.h \ diff -r 3af83b6be1df -r 22f932bbb305 lemon/euler.h --- a/lemon/euler.h Mon Feb 23 11:30:15 2009 +0000 +++ b/lemon/euler.h Mon Nov 03 11:59:54 2008 +0000 @@ -54,7 +54,6 @@ ///\endcode ///If \c g is not Euler then the resulted tour will not be full or closed. ///\sa EulerIt - ///\todo Test required template class DiEulerIt { @@ -146,7 +145,6 @@ /// ///If \c g is not Euler then the resulted tour will not be full or closed. ///\sa EulerIt - ///\todo Test required template class EulerIt { @@ -240,7 +238,6 @@ ///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. - ///\todo Test required template #ifdef DOXYGEN bool diff -r 3af83b6be1df -r 22f932bbb305 test/CMakeLists.txt --- a/test/CMakeLists.txt Mon Feb 23 11:30:15 2009 +0000 +++ b/test/CMakeLists.txt Mon Nov 03 11:59:54 2008 +0000 @@ -20,6 +20,7 @@ dim_test edge_set_test error_test + euler_test graph_copy_test graph_test graph_utils_test diff -r 3af83b6be1df -r 22f932bbb305 test/Makefile.am --- a/test/Makefile.am Mon Feb 23 11:30:15 2009 +0000 +++ b/test/Makefile.am Mon Nov 03 11:59:54 2008 +0000 @@ -16,6 +16,7 @@ test/dim_test \ test/edge_set_test \ test/error_test \ + test/euler_test \ test/graph_copy_test \ test/graph_test \ test/graph_utils_test \ @@ -54,6 +55,7 @@ test_dim_test_SOURCES = test/dim_test.cc test_edge_set_test_SOURCES = test/edge_set_test.cc test_error_test_SOURCES = test/error_test.cc +test_euler_test_SOURCES = test/euler_test.cc test_graph_copy_test_SOURCES = test/graph_copy_test.cc test_graph_test_SOURCES = test/graph_test.cc test_graph_utils_test_SOURCES = test/graph_utils_test.cc diff -r 3af83b6be1df -r 22f932bbb305 test/euler_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/euler_test.cc Mon Nov 03 11:59:54 2008 +0000 @@ -0,0 +1,153 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#include +#include +#include + +using namespace lemon; + +template +void checkDiEulerIt(const Digraph& g) +{ + typename Digraph::template ArcMap visitationNumber(g); + + DiEulerIt e(g); + typename Digraph::Node firstNode = g.source(e); + typename Digraph::Node lastNode; + + 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"); + + for (typename Digraph::ArcIt a(g); a != INVALID; ++a) + { + check(visitationNumber[a] == 1, + "checkDiEulerIt: not visited or multiple times visited arc found"); + } +} + +template +void checkEulerIt(const Graph& g) +{ + typename Graph::template EdgeMap visitationNumber(g); + + EulerIt e(g); + typename Graph::Node firstNode = g.u(e); + typename Graph::Node lastNode; + + for (; e != INVALID; ++e) + { + if (e != INVALID) + { + lastNode = g.v(e); + } + ++visitationNumber[e]; + } + + check(firstNode == lastNode, + "checkEulerIt: first and last node 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"); + } +} + +int main() +{ + typedef ListDigraph Digraph; + typedef ListGraph Graph; + + Digraph digraphWithEulerianCircuit; + { + Digraph& g = digraphWithEulerianCircuit; + + Digraph::Node n0 = g.addNode(); + Digraph::Node n1 = g.addNode(); + Digraph::Node n2 = g.addNode(); + + g.addArc(n0, n1); + g.addArc(n1, n0); + g.addArc(n1, n2); + g.addArc(n2, n1); + } + + Digraph digraphWithoutEulerianCircuit; + { + Digraph& g = digraphWithoutEulerianCircuit; + + Digraph::Node n0 = g.addNode(); + Digraph::Node n1 = g.addNode(); + Digraph::Node n2 = g.addNode(); + + g.addArc(n0, n1); + g.addArc(n1, n0); + g.addArc(n1, n2); + } + + Graph graphWithEulerianCircuit; + { + Graph& g = graphWithEulerianCircuit; + + Graph::Node n0 = g.addNode(); + Graph::Node n1 = g.addNode(); + Graph::Node n2 = g.addNode(); + + g.addEdge(n0, n1); + g.addEdge(n1, n2); + g.addEdge(n2, n0); + } + + 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); + } + + 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; +}