1.1 --- a/lemon/Makefile.am Mon Feb 23 11:30:15 2009 +0000
1.2 +++ b/lemon/Makefile.am Mon Nov 03 11:59:54 2008 +0000
1.3 @@ -54,6 +54,7 @@
1.4 lemon/clp.h \
1.5 lemon/color.h \
1.6 lemon/concept_check.h \
1.7 + lemon/connectivity.h \
1.8 lemon/counter.h \
1.9 lemon/core.h \
1.10 lemon/cplex.h \
2.1 --- a/lemon/euler.h Mon Feb 23 11:30:15 2009 +0000
2.2 +++ b/lemon/euler.h Mon Nov 03 11:59:54 2008 +0000
2.3 @@ -54,7 +54,6 @@
2.4 ///\endcode
2.5 ///If \c g is not Euler then the resulted tour will not be full or closed.
2.6 ///\sa EulerIt
2.7 - ///\todo Test required
2.8 template<class Digraph>
2.9 class DiEulerIt
2.10 {
2.11 @@ -146,7 +145,6 @@
2.12 ///
2.13 ///If \c g is not Euler then the resulted tour will not be full or closed.
2.14 ///\sa EulerIt
2.15 - ///\todo Test required
2.16 template<class Digraph>
2.17 class EulerIt
2.18 {
2.19 @@ -240,7 +238,6 @@
2.20 ///and only if it is connected and the number of incident arcs is even
2.21 ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
2.22 ///but still have an Euler tour</em>.
2.23 - ///\todo Test required
2.24 template<class Digraph>
2.25 #ifdef DOXYGEN
2.26 bool
3.1 --- a/test/CMakeLists.txt Mon Feb 23 11:30:15 2009 +0000
3.2 +++ b/test/CMakeLists.txt Mon Nov 03 11:59:54 2008 +0000
3.3 @@ -20,6 +20,7 @@
3.4 dim_test
3.5 edge_set_test
3.6 error_test
3.7 + euler_test
3.8 graph_copy_test
3.9 graph_test
3.10 graph_utils_test
4.1 --- a/test/Makefile.am Mon Feb 23 11:30:15 2009 +0000
4.2 +++ b/test/Makefile.am Mon Nov 03 11:59:54 2008 +0000
4.3 @@ -16,6 +16,7 @@
4.4 test/dim_test \
4.5 test/edge_set_test \
4.6 test/error_test \
4.7 + test/euler_test \
4.8 test/graph_copy_test \
4.9 test/graph_test \
4.10 test/graph_utils_test \
4.11 @@ -54,6 +55,7 @@
4.12 test_dim_test_SOURCES = test/dim_test.cc
4.13 test_edge_set_test_SOURCES = test/edge_set_test.cc
4.14 test_error_test_SOURCES = test/error_test.cc
4.15 +test_euler_test_SOURCES = test/euler_test.cc
4.16 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
4.17 test_graph_test_SOURCES = test/graph_test.cc
4.18 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/test/euler_test.cc Mon Nov 03 11:59:54 2008 +0000
5.3 @@ -0,0 +1,153 @@
5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library.
5.7 + *
5.8 + * Copyright (C) 2003-2009
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +#include <lemon/euler.h>
5.23 +#include <lemon/list_graph.h>
5.24 +#include <test/test_tools.h>
5.25 +
5.26 +using namespace lemon;
5.27 +
5.28 +template <typename Digraph>
5.29 +void checkDiEulerIt(const Digraph& g)
5.30 +{
5.31 + typename Digraph::template ArcMap<int> visitationNumber(g);
5.32 +
5.33 + DiEulerIt<Digraph> e(g);
5.34 + typename Digraph::Node firstNode = g.source(e);
5.35 + typename Digraph::Node lastNode;
5.36 +
5.37 + for (; e != INVALID; ++e)
5.38 + {
5.39 + if (e != INVALID)
5.40 + {
5.41 + lastNode = g.target(e);
5.42 + }
5.43 + ++visitationNumber[e];
5.44 + }
5.45 +
5.46 + check(firstNode == lastNode,
5.47 + "checkDiEulerIt: first and last node are not the same");
5.48 +
5.49 + for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
5.50 + {
5.51 + check(visitationNumber[a] == 1,
5.52 + "checkDiEulerIt: not visited or multiple times visited arc found");
5.53 + }
5.54 +}
5.55 +
5.56 +template <typename Graph>
5.57 +void checkEulerIt(const Graph& g)
5.58 +{
5.59 + typename Graph::template EdgeMap<int> visitationNumber(g);
5.60 +
5.61 + EulerIt<Graph> e(g);
5.62 + typename Graph::Node firstNode = g.u(e);
5.63 + typename Graph::Node lastNode;
5.64 +
5.65 + for (; e != INVALID; ++e)
5.66 + {
5.67 + if (e != INVALID)
5.68 + {
5.69 + lastNode = g.v(e);
5.70 + }
5.71 + ++visitationNumber[e];
5.72 + }
5.73 +
5.74 + check(firstNode == lastNode,
5.75 + "checkEulerIt: first and last node are not the same");
5.76 +
5.77 + for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
5.78 + {
5.79 + check(visitationNumber[e] == 1,
5.80 + "checkEulerIt: not visited or multiple times visited edge found");
5.81 + }
5.82 +}
5.83 +
5.84 +int main()
5.85 +{
5.86 + typedef ListDigraph Digraph;
5.87 + typedef ListGraph Graph;
5.88 +
5.89 + Digraph digraphWithEulerianCircuit;
5.90 + {
5.91 + Digraph& g = digraphWithEulerianCircuit;
5.92 +
5.93 + Digraph::Node n0 = g.addNode();
5.94 + Digraph::Node n1 = g.addNode();
5.95 + Digraph::Node n2 = g.addNode();
5.96 +
5.97 + g.addArc(n0, n1);
5.98 + g.addArc(n1, n0);
5.99 + g.addArc(n1, n2);
5.100 + g.addArc(n2, n1);
5.101 + }
5.102 +
5.103 + Digraph digraphWithoutEulerianCircuit;
5.104 + {
5.105 + Digraph& g = digraphWithoutEulerianCircuit;
5.106 +
5.107 + Digraph::Node n0 = g.addNode();
5.108 + Digraph::Node n1 = g.addNode();
5.109 + Digraph::Node n2 = g.addNode();
5.110 +
5.111 + g.addArc(n0, n1);
5.112 + g.addArc(n1, n0);
5.113 + g.addArc(n1, n2);
5.114 + }
5.115 +
5.116 + Graph graphWithEulerianCircuit;
5.117 + {
5.118 + Graph& g = graphWithEulerianCircuit;
5.119 +
5.120 + Graph::Node n0 = g.addNode();
5.121 + Graph::Node n1 = g.addNode();
5.122 + Graph::Node n2 = g.addNode();
5.123 +
5.124 + g.addEdge(n0, n1);
5.125 + g.addEdge(n1, n2);
5.126 + g.addEdge(n2, n0);
5.127 + }
5.128 +
5.129 + Graph graphWithoutEulerianCircuit;
5.130 + {
5.131 + Graph& g = graphWithoutEulerianCircuit;
5.132 +
5.133 + Graph::Node n0 = g.addNode();
5.134 + Graph::Node n1 = g.addNode();
5.135 + Graph::Node n2 = g.addNode();
5.136 +
5.137 + g.addEdge(n0, n1);
5.138 + g.addEdge(n1, n2);
5.139 + }
5.140 +
5.141 + checkDiEulerIt(digraphWithEulerianCircuit);
5.142 +
5.143 + checkEulerIt(graphWithEulerianCircuit);
5.144 +
5.145 + check(eulerian(digraphWithEulerianCircuit),
5.146 + "this graph should have an Eulerian circuit");
5.147 + check(!eulerian(digraphWithoutEulerianCircuit),
5.148 + "this graph should not have an Eulerian circuit");
5.149 +
5.150 + check(eulerian(graphWithEulerianCircuit),
5.151 + "this graph should have an Eulerian circuit");
5.152 + check(!eulerian(graphWithoutEulerianCircuit),
5.153 + "this graph should have an Eulerian circuit");
5.154 +
5.155 + return 0;
5.156 +}