1.1 --- a/test/euler_test.cc Wed Apr 15 11:41:25 2009 +0200
1.2 +++ b/test/euler_test.cc Wed Apr 15 11:47:19 2009 +0200
1.3 @@ -18,136 +18,206 @@
1.4
1.5 #include <lemon/euler.h>
1.6 #include <lemon/list_graph.h>
1.7 -#include <test/test_tools.h>
1.8 +#include <lemon/adaptors.h>
1.9 +#include "test_tools.h"
1.10
1.11 using namespace lemon;
1.12
1.13 template <typename Digraph>
1.14 -void checkDiEulerIt(const Digraph& g)
1.15 +void checkDiEulerIt(const Digraph& g,
1.16 + const typename Digraph::Node& start = INVALID)
1.17 {
1.18 typename Digraph::template ArcMap<int> visitationNumber(g, 0);
1.19
1.20 - DiEulerIt<Digraph> e(g);
1.21 + DiEulerIt<Digraph> e(g, start);
1.22 + if (e == INVALID) return;
1.23 typename Digraph::Node firstNode = g.source(e);
1.24 typename Digraph::Node lastNode = g.target(e);
1.25 + if (start != INVALID) {
1.26 + check(firstNode == start, "checkDiEulerIt: Wrong first node");
1.27 + }
1.28
1.29 - for (; e != INVALID; ++e)
1.30 - {
1.31 - if (e != INVALID)
1.32 - {
1.33 - lastNode = g.target(e);
1.34 - }
1.35 + for (; e != INVALID; ++e) {
1.36 + if (e != INVALID) lastNode = g.target(e);
1.37 ++visitationNumber[e];
1.38 }
1.39
1.40 check(firstNode == lastNode,
1.41 - "checkDiEulerIt: first and last node are not the same");
1.42 + "checkDiEulerIt: First and last nodes are not the same");
1.43
1.44 for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
1.45 {
1.46 check(visitationNumber[a] == 1,
1.47 - "checkDiEulerIt: not visited or multiple times visited arc found");
1.48 + "checkDiEulerIt: Not visited or multiple times visited arc found");
1.49 }
1.50 }
1.51
1.52 template <typename Graph>
1.53 -void checkEulerIt(const Graph& g)
1.54 +void checkEulerIt(const Graph& g,
1.55 + const typename Graph::Node& start = INVALID)
1.56 {
1.57 typename Graph::template EdgeMap<int> visitationNumber(g, 0);
1.58
1.59 - EulerIt<Graph> e(g);
1.60 - typename Graph::Node firstNode = g.u(e);
1.61 - typename Graph::Node lastNode = g.v(e);
1.62 + EulerIt<Graph> e(g, start);
1.63 + if (e == INVALID) return;
1.64 + typename Graph::Node firstNode = g.source(typename Graph::Arc(e));
1.65 + typename Graph::Node lastNode = g.target(typename Graph::Arc(e));
1.66 + if (start != INVALID) {
1.67 + check(firstNode == start, "checkEulerIt: Wrong first node");
1.68 + }
1.69
1.70 - for (; e != INVALID; ++e)
1.71 - {
1.72 - if (e != INVALID)
1.73 - {
1.74 - lastNode = g.v(e);
1.75 - }
1.76 + for (; e != INVALID; ++e) {
1.77 + if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
1.78 ++visitationNumber[e];
1.79 }
1.80
1.81 check(firstNode == lastNode,
1.82 - "checkEulerIt: first and last node are not the same");
1.83 + "checkEulerIt: First and last nodes are not the same");
1.84
1.85 for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
1.86 {
1.87 check(visitationNumber[e] == 1,
1.88 - "checkEulerIt: not visited or multiple times visited edge found");
1.89 + "checkEulerIt: Not visited or multiple times visited edge found");
1.90 }
1.91 }
1.92
1.93 int main()
1.94 {
1.95 typedef ListDigraph Digraph;
1.96 - typedef ListGraph Graph;
1.97 + typedef Undirector<Digraph> Graph;
1.98 +
1.99 + {
1.100 + Digraph d;
1.101 + Graph g(d);
1.102 +
1.103 + checkDiEulerIt(d);
1.104 + checkDiEulerIt(g);
1.105 + checkEulerIt(g);
1.106
1.107 - Digraph digraphWithEulerianCircuit;
1.108 + check(eulerian(d), "This graph is Eulerian");
1.109 + check(eulerian(g), "This graph is Eulerian");
1.110 + }
1.111 {
1.112 - Digraph& g = digraphWithEulerianCircuit;
1.113 + Digraph d;
1.114 + Graph g(d);
1.115 + Digraph::Node n = d.addNode();
1.116
1.117 - Digraph::Node n0 = g.addNode();
1.118 - Digraph::Node n1 = g.addNode();
1.119 - Digraph::Node n2 = g.addNode();
1.120 + checkDiEulerIt(d);
1.121 + checkDiEulerIt(g);
1.122 + checkEulerIt(g);
1.123
1.124 - g.addArc(n0, n1);
1.125 - g.addArc(n1, n0);
1.126 - g.addArc(n1, n2);
1.127 - g.addArc(n2, n1);
1.128 + check(eulerian(d), "This graph is Eulerian");
1.129 + check(eulerian(g), "This graph is Eulerian");
1.130 }
1.131 + {
1.132 + Digraph d;
1.133 + Graph g(d);
1.134 + Digraph::Node n = d.addNode();
1.135 + d.addArc(n, n);
1.136
1.137 - Digraph digraphWithoutEulerianCircuit;
1.138 + checkDiEulerIt(d);
1.139 + checkDiEulerIt(g);
1.140 + checkEulerIt(g);
1.141 +
1.142 + check(eulerian(d), "This graph is Eulerian");
1.143 + check(eulerian(g), "This graph is Eulerian");
1.144 + }
1.145 {
1.146 - Digraph& g = digraphWithoutEulerianCircuit;
1.147 + Digraph d;
1.148 + Graph g(d);
1.149 + Digraph::Node n1 = d.addNode();
1.150 + Digraph::Node n2 = d.addNode();
1.151 + Digraph::Node n3 = d.addNode();
1.152 +
1.153 + d.addArc(n1, n2);
1.154 + d.addArc(n2, n1);
1.155 + d.addArc(n2, n3);
1.156 + d.addArc(n3, n2);
1.157
1.158 - Digraph::Node n0 = g.addNode();
1.159 - Digraph::Node n1 = g.addNode();
1.160 - Digraph::Node n2 = g.addNode();
1.161 + checkDiEulerIt(d);
1.162 + checkDiEulerIt(d, n2);
1.163 + checkDiEulerIt(g);
1.164 + checkDiEulerIt(g, n2);
1.165 + checkEulerIt(g);
1.166 + checkEulerIt(g, n2);
1.167
1.168 - g.addArc(n0, n1);
1.169 - g.addArc(n1, n0);
1.170 - g.addArc(n1, n2);
1.171 + check(eulerian(d), "This graph is Eulerian");
1.172 + check(eulerian(g), "This graph is Eulerian");
1.173 }
1.174 + {
1.175 + Digraph d;
1.176 + Graph g(d);
1.177 + Digraph::Node n1 = d.addNode();
1.178 + Digraph::Node n2 = d.addNode();
1.179 + Digraph::Node n3 = d.addNode();
1.180 + Digraph::Node n4 = d.addNode();
1.181 + Digraph::Node n5 = d.addNode();
1.182 + Digraph::Node n6 = d.addNode();
1.183 +
1.184 + d.addArc(n1, n2);
1.185 + d.addArc(n2, n4);
1.186 + d.addArc(n1, n3);
1.187 + d.addArc(n3, n4);
1.188 + d.addArc(n4, n1);
1.189 + d.addArc(n3, n5);
1.190 + d.addArc(n5, n2);
1.191 + d.addArc(n4, n6);
1.192 + d.addArc(n2, n6);
1.193 + d.addArc(n6, n1);
1.194 + d.addArc(n6, n3);
1.195
1.196 - Graph graphWithEulerianCircuit;
1.197 + checkDiEulerIt(d);
1.198 + checkDiEulerIt(d, n1);
1.199 + checkDiEulerIt(d, n5);
1.200 +
1.201 + checkDiEulerIt(g);
1.202 + checkDiEulerIt(g, n1);
1.203 + checkDiEulerIt(g, n5);
1.204 + checkEulerIt(g);
1.205 + checkEulerIt(g, n1);
1.206 + checkEulerIt(g, n5);
1.207 +
1.208 + check(eulerian(d), "This graph is Eulerian");
1.209 + check(eulerian(g), "This graph is Eulerian");
1.210 + }
1.211 {
1.212 - Graph& g = graphWithEulerianCircuit;
1.213 + Digraph d;
1.214 + Graph g(d);
1.215 + Digraph::Node n0 = d.addNode();
1.216 + Digraph::Node n1 = d.addNode();
1.217 + Digraph::Node n2 = d.addNode();
1.218 + Digraph::Node n3 = d.addNode();
1.219 + Digraph::Node n4 = d.addNode();
1.220 + Digraph::Node n5 = d.addNode();
1.221 +
1.222 + d.addArc(n1, n2);
1.223 + d.addArc(n2, n3);
1.224 + d.addArc(n3, n1);
1.225
1.226 - Graph::Node n0 = g.addNode();
1.227 - Graph::Node n1 = g.addNode();
1.228 - Graph::Node n2 = g.addNode();
1.229 + checkDiEulerIt(d);
1.230 + checkDiEulerIt(d, n2);
1.231
1.232 - g.addEdge(n0, n1);
1.233 - g.addEdge(n1, n2);
1.234 - g.addEdge(n2, n0);
1.235 + checkDiEulerIt(g);
1.236 + checkDiEulerIt(g, n2);
1.237 + checkEulerIt(g);
1.238 + checkEulerIt(g, n2);
1.239 +
1.240 + check(!eulerian(d), "This graph is not Eulerian");
1.241 + check(!eulerian(g), "This graph is not Eulerian");
1.242 }
1.243 + {
1.244 + Digraph d;
1.245 + Graph g(d);
1.246 + Digraph::Node n1 = d.addNode();
1.247 + Digraph::Node n2 = d.addNode();
1.248 + Digraph::Node n3 = d.addNode();
1.249 +
1.250 + d.addArc(n1, n2);
1.251 + d.addArc(n2, n3);
1.252
1.253 - Graph graphWithoutEulerianCircuit;
1.254 - {
1.255 - Graph& g = graphWithoutEulerianCircuit;
1.256 -
1.257 - Graph::Node n0 = g.addNode();
1.258 - Graph::Node n1 = g.addNode();
1.259 - Graph::Node n2 = g.addNode();
1.260 -
1.261 - g.addEdge(n0, n1);
1.262 - g.addEdge(n1, n2);
1.263 + check(!eulerian(d), "This graph is not Eulerian");
1.264 + check(!eulerian(g), "This graph is not Eulerian");
1.265 }
1.266
1.267 - checkDiEulerIt(digraphWithEulerianCircuit);
1.268 -
1.269 - checkEulerIt(graphWithEulerianCircuit);
1.270 -
1.271 - check(eulerian(digraphWithEulerianCircuit),
1.272 - "this graph should have an Eulerian circuit");
1.273 - check(!eulerian(digraphWithoutEulerianCircuit),
1.274 - "this graph should not have an Eulerian circuit");
1.275 -
1.276 - check(eulerian(graphWithEulerianCircuit),
1.277 - "this graph should have an Eulerian circuit");
1.278 - check(!eulerian(graphWithoutEulerianCircuit),
1.279 - "this graph should have an Eulerian circuit");
1.280 -
1.281 return 0;
1.282 }