1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/euler_test.cc Thu Dec 10 17:05:35 2009 +0100
1.3 @@ -0,0 +1,223 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <lemon/euler.h>
1.23 +#include <lemon/list_graph.h>
1.24 +#include <lemon/adaptors.h>
1.25 +#include "test_tools.h"
1.26 +
1.27 +using namespace lemon;
1.28 +
1.29 +template <typename Digraph>
1.30 +void checkDiEulerIt(const Digraph& g,
1.31 + const typename Digraph::Node& start = INVALID)
1.32 +{
1.33 + typename Digraph::template ArcMap<int> visitationNumber(g, 0);
1.34 +
1.35 + DiEulerIt<Digraph> e(g, start);
1.36 + if (e == INVALID) return;
1.37 + typename Digraph::Node firstNode = g.source(e);
1.38 + typename Digraph::Node lastNode = g.target(e);
1.39 + if (start != INVALID) {
1.40 + check(firstNode == start, "checkDiEulerIt: Wrong first node");
1.41 + }
1.42 +
1.43 + for (; e != INVALID; ++e) {
1.44 + if (e != INVALID) lastNode = g.target(e);
1.45 + ++visitationNumber[e];
1.46 + }
1.47 +
1.48 + check(firstNode == lastNode,
1.49 + "checkDiEulerIt: First and last nodes are not the same");
1.50 +
1.51 + for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
1.52 + {
1.53 + check(visitationNumber[a] == 1,
1.54 + "checkDiEulerIt: Not visited or multiple times visited arc found");
1.55 + }
1.56 +}
1.57 +
1.58 +template <typename Graph>
1.59 +void checkEulerIt(const Graph& g,
1.60 + const typename Graph::Node& start = INVALID)
1.61 +{
1.62 + typename Graph::template EdgeMap<int> visitationNumber(g, 0);
1.63 +
1.64 + EulerIt<Graph> e(g, start);
1.65 + if (e == INVALID) return;
1.66 + typename Graph::Node firstNode = g.source(typename Graph::Arc(e));
1.67 + typename Graph::Node lastNode = g.target(typename Graph::Arc(e));
1.68 + if (start != INVALID) {
1.69 + check(firstNode == start, "checkEulerIt: Wrong first node");
1.70 + }
1.71 +
1.72 + for (; e != INVALID; ++e) {
1.73 + if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
1.74 + ++visitationNumber[e];
1.75 + }
1.76 +
1.77 + check(firstNode == lastNode,
1.78 + "checkEulerIt: First and last nodes are not the same");
1.79 +
1.80 + for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
1.81 + {
1.82 + check(visitationNumber[e] == 1,
1.83 + "checkEulerIt: Not visited or multiple times visited edge found");
1.84 + }
1.85 +}
1.86 +
1.87 +int main()
1.88 +{
1.89 + typedef ListDigraph Digraph;
1.90 + typedef Undirector<Digraph> Graph;
1.91 +
1.92 + {
1.93 + Digraph d;
1.94 + Graph g(d);
1.95 +
1.96 + checkDiEulerIt(d);
1.97 + checkDiEulerIt(g);
1.98 + checkEulerIt(g);
1.99 +
1.100 + check(eulerian(d), "This graph is Eulerian");
1.101 + check(eulerian(g), "This graph is Eulerian");
1.102 + }
1.103 + {
1.104 + Digraph d;
1.105 + Graph g(d);
1.106 + Digraph::Node n = d.addNode();
1.107 +
1.108 + checkDiEulerIt(d);
1.109 + checkDiEulerIt(g);
1.110 + checkEulerIt(g);
1.111 +
1.112 + check(eulerian(d), "This graph is Eulerian");
1.113 + check(eulerian(g), "This graph is Eulerian");
1.114 + }
1.115 + {
1.116 + Digraph d;
1.117 + Graph g(d);
1.118 + Digraph::Node n = d.addNode();
1.119 + d.addArc(n, n);
1.120 +
1.121 + checkDiEulerIt(d);
1.122 + checkDiEulerIt(g);
1.123 + checkEulerIt(g);
1.124 +
1.125 + check(eulerian(d), "This graph is Eulerian");
1.126 + check(eulerian(g), "This graph is Eulerian");
1.127 + }
1.128 + {
1.129 + Digraph d;
1.130 + Graph g(d);
1.131 + Digraph::Node n1 = d.addNode();
1.132 + Digraph::Node n2 = d.addNode();
1.133 + Digraph::Node n3 = d.addNode();
1.134 +
1.135 + d.addArc(n1, n2);
1.136 + d.addArc(n2, n1);
1.137 + d.addArc(n2, n3);
1.138 + d.addArc(n3, n2);
1.139 +
1.140 + checkDiEulerIt(d);
1.141 + checkDiEulerIt(d, n2);
1.142 + checkDiEulerIt(g);
1.143 + checkDiEulerIt(g, n2);
1.144 + checkEulerIt(g);
1.145 + checkEulerIt(g, n2);
1.146 +
1.147 + check(eulerian(d), "This graph is Eulerian");
1.148 + check(eulerian(g), "This graph is Eulerian");
1.149 + }
1.150 + {
1.151 + Digraph d;
1.152 + Graph g(d);
1.153 + Digraph::Node n1 = d.addNode();
1.154 + Digraph::Node n2 = d.addNode();
1.155 + Digraph::Node n3 = d.addNode();
1.156 + Digraph::Node n4 = d.addNode();
1.157 + Digraph::Node n5 = d.addNode();
1.158 + Digraph::Node n6 = d.addNode();
1.159 +
1.160 + d.addArc(n1, n2);
1.161 + d.addArc(n2, n4);
1.162 + d.addArc(n1, n3);
1.163 + d.addArc(n3, n4);
1.164 + d.addArc(n4, n1);
1.165 + d.addArc(n3, n5);
1.166 + d.addArc(n5, n2);
1.167 + d.addArc(n4, n6);
1.168 + d.addArc(n2, n6);
1.169 + d.addArc(n6, n1);
1.170 + d.addArc(n6, n3);
1.171 +
1.172 + checkDiEulerIt(d);
1.173 + checkDiEulerIt(d, n1);
1.174 + checkDiEulerIt(d, n5);
1.175 +
1.176 + checkDiEulerIt(g);
1.177 + checkDiEulerIt(g, n1);
1.178 + checkDiEulerIt(g, n5);
1.179 + checkEulerIt(g);
1.180 + checkEulerIt(g, n1);
1.181 + checkEulerIt(g, n5);
1.182 +
1.183 + check(eulerian(d), "This graph is Eulerian");
1.184 + check(eulerian(g), "This graph is Eulerian");
1.185 + }
1.186 + {
1.187 + Digraph d;
1.188 + Graph g(d);
1.189 + Digraph::Node n0 = d.addNode();
1.190 + Digraph::Node n1 = d.addNode();
1.191 + Digraph::Node n2 = d.addNode();
1.192 + Digraph::Node n3 = d.addNode();
1.193 + Digraph::Node n4 = d.addNode();
1.194 + Digraph::Node n5 = d.addNode();
1.195 +
1.196 + d.addArc(n1, n2);
1.197 + d.addArc(n2, n3);
1.198 + d.addArc(n3, n1);
1.199 +
1.200 + checkDiEulerIt(d);
1.201 + checkDiEulerIt(d, n2);
1.202 +
1.203 + checkDiEulerIt(g);
1.204 + checkDiEulerIt(g, n2);
1.205 + checkEulerIt(g);
1.206 + checkEulerIt(g, n2);
1.207 +
1.208 + check(!eulerian(d), "This graph is not Eulerian");
1.209 + check(!eulerian(g), "This graph is not Eulerian");
1.210 + }
1.211 + {
1.212 + Digraph d;
1.213 + Graph g(d);
1.214 + Digraph::Node n1 = d.addNode();
1.215 + Digraph::Node n2 = d.addNode();
1.216 + Digraph::Node n3 = d.addNode();
1.217 +
1.218 + d.addArc(n1, n2);
1.219 + d.addArc(n2, n3);
1.220 +
1.221 + check(!eulerian(d), "This graph is not Eulerian");
1.222 + check(!eulerian(g), "This graph is not Eulerian");
1.223 + }
1.224 +
1.225 + return 0;
1.226 +}