1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/euler_test.cc Mon Nov 03 11:59:54 2008 +0000
1.3 @@ -0,0 +1,153 @@
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 <test/test_tools.h>
1.25 +
1.26 +using namespace lemon;
1.27 +
1.28 +template <typename Digraph>
1.29 +void checkDiEulerIt(const Digraph& g)
1.30 +{
1.31 + typename Digraph::template ArcMap<int> visitationNumber(g);
1.32 +
1.33 + DiEulerIt<Digraph> e(g);
1.34 + typename Digraph::Node firstNode = g.source(e);
1.35 + typename Digraph::Node lastNode;
1.36 +
1.37 + for (; e != INVALID; ++e)
1.38 + {
1.39 + if (e != INVALID)
1.40 + {
1.41 + lastNode = g.target(e);
1.42 + }
1.43 + ++visitationNumber[e];
1.44 + }
1.45 +
1.46 + check(firstNode == lastNode,
1.47 + "checkDiEulerIt: first and last node are not the same");
1.48 +
1.49 + for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
1.50 + {
1.51 + check(visitationNumber[a] == 1,
1.52 + "checkDiEulerIt: not visited or multiple times visited arc found");
1.53 + }
1.54 +}
1.55 +
1.56 +template <typename Graph>
1.57 +void checkEulerIt(const Graph& g)
1.58 +{
1.59 + typename Graph::template EdgeMap<int> visitationNumber(g);
1.60 +
1.61 + EulerIt<Graph> e(g);
1.62 + typename Graph::Node firstNode = g.u(e);
1.63 + typename Graph::Node lastNode;
1.64 +
1.65 + for (; e != INVALID; ++e)
1.66 + {
1.67 + if (e != INVALID)
1.68 + {
1.69 + lastNode = g.v(e);
1.70 + }
1.71 + ++visitationNumber[e];
1.72 + }
1.73 +
1.74 + check(firstNode == lastNode,
1.75 + "checkEulerIt: first and last node are not the same");
1.76 +
1.77 + for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
1.78 + {
1.79 + check(visitationNumber[e] == 1,
1.80 + "checkEulerIt: not visited or multiple times visited edge found");
1.81 + }
1.82 +}
1.83 +
1.84 +int main()
1.85 +{
1.86 + typedef ListDigraph Digraph;
1.87 + typedef ListGraph Graph;
1.88 +
1.89 + Digraph digraphWithEulerianCircuit;
1.90 + {
1.91 + Digraph& g = digraphWithEulerianCircuit;
1.92 +
1.93 + Digraph::Node n0 = g.addNode();
1.94 + Digraph::Node n1 = g.addNode();
1.95 + Digraph::Node n2 = g.addNode();
1.96 +
1.97 + g.addArc(n0, n1);
1.98 + g.addArc(n1, n0);
1.99 + g.addArc(n1, n2);
1.100 + g.addArc(n2, n1);
1.101 + }
1.102 +
1.103 + Digraph digraphWithoutEulerianCircuit;
1.104 + {
1.105 + Digraph& g = digraphWithoutEulerianCircuit;
1.106 +
1.107 + Digraph::Node n0 = g.addNode();
1.108 + Digraph::Node n1 = g.addNode();
1.109 + Digraph::Node n2 = g.addNode();
1.110 +
1.111 + g.addArc(n0, n1);
1.112 + g.addArc(n1, n0);
1.113 + g.addArc(n1, n2);
1.114 + }
1.115 +
1.116 + Graph graphWithEulerianCircuit;
1.117 + {
1.118 + Graph& g = graphWithEulerianCircuit;
1.119 +
1.120 + Graph::Node n0 = g.addNode();
1.121 + Graph::Node n1 = g.addNode();
1.122 + Graph::Node n2 = g.addNode();
1.123 +
1.124 + g.addEdge(n0, n1);
1.125 + g.addEdge(n1, n2);
1.126 + g.addEdge(n2, n0);
1.127 + }
1.128 +
1.129 + Graph graphWithoutEulerianCircuit;
1.130 + {
1.131 + Graph& g = graphWithoutEulerianCircuit;
1.132 +
1.133 + Graph::Node n0 = g.addNode();
1.134 + Graph::Node n1 = g.addNode();
1.135 + Graph::Node n2 = g.addNode();
1.136 +
1.137 + g.addEdge(n0, n1);
1.138 + g.addEdge(n1, n2);
1.139 + }
1.140 +
1.141 + checkDiEulerIt(digraphWithEulerianCircuit);
1.142 +
1.143 + checkEulerIt(graphWithEulerianCircuit);
1.144 +
1.145 + check(eulerian(digraphWithEulerianCircuit),
1.146 + "this graph should have an Eulerian circuit");
1.147 + check(!eulerian(digraphWithoutEulerianCircuit),
1.148 + "this graph should not have an Eulerian circuit");
1.149 +
1.150 + check(eulerian(graphWithEulerianCircuit),
1.151 + "this graph should have an Eulerian circuit");
1.152 + check(!eulerian(graphWithoutEulerianCircuit),
1.153 + "this graph should have an Eulerian circuit");
1.154 +
1.155 + return 0;
1.156 +}