test/euler_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 522 22f932bbb305
child 592 2ebfdb89ec66
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
ladanyi@522
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
ladanyi@522
     2
 *
ladanyi@522
     3
 * This file is a part of LEMON, a generic C++ optimization library.
ladanyi@522
     4
 *
ladanyi@522
     5
 * Copyright (C) 2003-2009
ladanyi@522
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
ladanyi@522
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
ladanyi@522
     8
 *
ladanyi@522
     9
 * Permission to use, modify and distribute this software is granted
ladanyi@522
    10
 * provided that this copyright notice appears in all copies. For
ladanyi@522
    11
 * precise terms see the accompanying LICENSE file.
ladanyi@522
    12
 *
ladanyi@522
    13
 * This software is provided "AS IS" with no warranty of any kind,
ladanyi@522
    14
 * express or implied, and with no claim as to its suitability for any
ladanyi@522
    15
 * purpose.
ladanyi@522
    16
 *
ladanyi@522
    17
 */
ladanyi@522
    18
ladanyi@522
    19
#include <lemon/euler.h>
ladanyi@522
    20
#include <lemon/list_graph.h>
ladanyi@522
    21
#include <test/test_tools.h>
ladanyi@522
    22
ladanyi@522
    23
using namespace lemon;
ladanyi@522
    24
ladanyi@522
    25
template <typename Digraph>
ladanyi@522
    26
void checkDiEulerIt(const Digraph& g)
ladanyi@522
    27
{
kpeter@531
    28
  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
ladanyi@522
    29
ladanyi@522
    30
  DiEulerIt<Digraph> e(g);
ladanyi@522
    31
  typename Digraph::Node firstNode = g.source(e);
kpeter@531
    32
  typename Digraph::Node lastNode = g.target(e);
ladanyi@522
    33
ladanyi@522
    34
  for (; e != INVALID; ++e)
ladanyi@522
    35
  {
ladanyi@522
    36
    if (e != INVALID)
ladanyi@522
    37
    {
ladanyi@522
    38
      lastNode = g.target(e);
ladanyi@522
    39
    }
ladanyi@522
    40
    ++visitationNumber[e];
ladanyi@522
    41
  }
ladanyi@522
    42
ladanyi@522
    43
  check(firstNode == lastNode,
ladanyi@522
    44
      "checkDiEulerIt: first and last node are not the same");
ladanyi@522
    45
ladanyi@522
    46
  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
ladanyi@522
    47
  {
ladanyi@522
    48
    check(visitationNumber[a] == 1,
ladanyi@522
    49
        "checkDiEulerIt: not visited or multiple times visited arc found");
ladanyi@522
    50
  }
ladanyi@522
    51
}
ladanyi@522
    52
ladanyi@522
    53
template <typename Graph>
ladanyi@522
    54
void checkEulerIt(const Graph& g)
ladanyi@522
    55
{
kpeter@531
    56
  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
ladanyi@522
    57
ladanyi@522
    58
  EulerIt<Graph> e(g);
ladanyi@522
    59
  typename Graph::Node firstNode = g.u(e);
kpeter@531
    60
  typename Graph::Node lastNode = g.v(e);
ladanyi@522
    61
ladanyi@522
    62
  for (; e != INVALID; ++e)
ladanyi@522
    63
  {
ladanyi@522
    64
    if (e != INVALID)
ladanyi@522
    65
    {
ladanyi@522
    66
      lastNode = g.v(e);
ladanyi@522
    67
    }
ladanyi@522
    68
    ++visitationNumber[e];
ladanyi@522
    69
  }
ladanyi@522
    70
ladanyi@522
    71
  check(firstNode == lastNode,
ladanyi@522
    72
      "checkEulerIt: first and last node are not the same");
ladanyi@522
    73
ladanyi@522
    74
  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
ladanyi@522
    75
  {
ladanyi@522
    76
    check(visitationNumber[e] == 1,
ladanyi@522
    77
        "checkEulerIt: not visited or multiple times visited edge found");
ladanyi@522
    78
  }
ladanyi@522
    79
}
ladanyi@522
    80
ladanyi@522
    81
int main()
ladanyi@522
    82
{
ladanyi@522
    83
  typedef ListDigraph Digraph;
ladanyi@522
    84
  typedef ListGraph Graph;
ladanyi@522
    85
ladanyi@522
    86
  Digraph digraphWithEulerianCircuit;
ladanyi@522
    87
  {
ladanyi@522
    88
    Digraph& g = digraphWithEulerianCircuit;
ladanyi@522
    89
ladanyi@522
    90
    Digraph::Node n0 = g.addNode();
ladanyi@522
    91
    Digraph::Node n1 = g.addNode();
ladanyi@522
    92
    Digraph::Node n2 = g.addNode();
ladanyi@522
    93
ladanyi@522
    94
    g.addArc(n0, n1);
ladanyi@522
    95
    g.addArc(n1, n0);
ladanyi@522
    96
    g.addArc(n1, n2);
ladanyi@522
    97
    g.addArc(n2, n1);
ladanyi@522
    98
  }
ladanyi@522
    99
ladanyi@522
   100
  Digraph digraphWithoutEulerianCircuit;
ladanyi@522
   101
  {
ladanyi@522
   102
    Digraph& g = digraphWithoutEulerianCircuit;
ladanyi@522
   103
ladanyi@522
   104
    Digraph::Node n0 = g.addNode();
ladanyi@522
   105
    Digraph::Node n1 = g.addNode();
ladanyi@522
   106
    Digraph::Node n2 = g.addNode();
ladanyi@522
   107
ladanyi@522
   108
    g.addArc(n0, n1);
ladanyi@522
   109
    g.addArc(n1, n0);
ladanyi@522
   110
    g.addArc(n1, n2);
ladanyi@522
   111
  }
ladanyi@522
   112
ladanyi@522
   113
  Graph graphWithEulerianCircuit;
ladanyi@522
   114
  {
ladanyi@522
   115
    Graph& g = graphWithEulerianCircuit;
ladanyi@522
   116
ladanyi@522
   117
    Graph::Node n0 = g.addNode();
ladanyi@522
   118
    Graph::Node n1 = g.addNode();
ladanyi@522
   119
    Graph::Node n2 = g.addNode();
ladanyi@522
   120
ladanyi@522
   121
    g.addEdge(n0, n1);
ladanyi@522
   122
    g.addEdge(n1, n2);
ladanyi@522
   123
    g.addEdge(n2, n0);
ladanyi@522
   124
  }
ladanyi@522
   125
ladanyi@522
   126
  Graph graphWithoutEulerianCircuit;
ladanyi@522
   127
  {
ladanyi@522
   128
    Graph& g = graphWithoutEulerianCircuit;
ladanyi@522
   129
ladanyi@522
   130
    Graph::Node n0 = g.addNode();
ladanyi@522
   131
    Graph::Node n1 = g.addNode();
ladanyi@522
   132
    Graph::Node n2 = g.addNode();
ladanyi@522
   133
ladanyi@522
   134
    g.addEdge(n0, n1);
ladanyi@522
   135
    g.addEdge(n1, n2);
ladanyi@522
   136
  }
ladanyi@522
   137
ladanyi@522
   138
  checkDiEulerIt(digraphWithEulerianCircuit);
ladanyi@522
   139
ladanyi@522
   140
  checkEulerIt(graphWithEulerianCircuit);
ladanyi@522
   141
ladanyi@522
   142
  check(eulerian(digraphWithEulerianCircuit),
ladanyi@522
   143
      "this graph should have an Eulerian circuit");
ladanyi@522
   144
  check(!eulerian(digraphWithoutEulerianCircuit),
ladanyi@522
   145
      "this graph should not have an Eulerian circuit");
ladanyi@522
   146
ladanyi@522
   147
  check(eulerian(graphWithEulerianCircuit),
ladanyi@522
   148
      "this graph should have an Eulerian circuit");
ladanyi@522
   149
  check(!eulerian(graphWithoutEulerianCircuit),
ladanyi@522
   150
      "this graph should have an Eulerian circuit");
ladanyi@522
   151
ladanyi@522
   152
  return 0;
ladanyi@522
   153
}