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 +}