test/euler_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 22 May 2015 17:44:29 +0200
changeset 1356 138714057145
parent 1259 8b2d4e5d96e4
permissions -rw-r--r--
Merge
ladanyi@569
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
ladanyi@569
     2
 *
ladanyi@569
     3
 * This file is a part of LEMON, a generic C++ optimization library.
ladanyi@569
     4
 *
alpar@1270
     5
 * Copyright (C) 2003-2013
ladanyi@569
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
ladanyi@569
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
ladanyi@569
     8
 *
ladanyi@569
     9
 * Permission to use, modify and distribute this software is granted
ladanyi@569
    10
 * provided that this copyright notice appears in all copies. For
ladanyi@569
    11
 * precise terms see the accompanying LICENSE file.
ladanyi@569
    12
 *
ladanyi@569
    13
 * This software is provided "AS IS" with no warranty of any kind,
ladanyi@569
    14
 * express or implied, and with no claim as to its suitability for any
ladanyi@569
    15
 * purpose.
ladanyi@569
    16
 *
ladanyi@569
    17
 */
ladanyi@569
    18
ladanyi@569
    19
#include <lemon/euler.h>
ladanyi@569
    20
#include <lemon/list_graph.h>
kpeter@639
    21
#include <lemon/adaptors.h>
kpeter@639
    22
#include "test_tools.h"
ladanyi@569
    23
ladanyi@569
    24
using namespace lemon;
ladanyi@569
    25
ladanyi@569
    26
template <typename Digraph>
kpeter@639
    27
void checkDiEulerIt(const Digraph& g,
kpeter@639
    28
                    const typename Digraph::Node& start = INVALID)
ladanyi@569
    29
{
kpeter@578
    30
  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
ladanyi@569
    31
kpeter@639
    32
  DiEulerIt<Digraph> e(g, start);
kpeter@639
    33
  if (e == INVALID) return;
ladanyi@569
    34
  typename Digraph::Node firstNode = g.source(e);
kpeter@578
    35
  typename Digraph::Node lastNode = g.target(e);
kpeter@639
    36
  if (start != INVALID) {
kpeter@639
    37
    check(firstNode == start, "checkDiEulerIt: Wrong first node");
kpeter@639
    38
  }
ladanyi@569
    39
kpeter@639
    40
  for (; e != INVALID; ++e) {
kpeter@639
    41
    if (e != INVALID) lastNode = g.target(e);
ladanyi@569
    42
    ++visitationNumber[e];
ladanyi@569
    43
  }
ladanyi@569
    44
ladanyi@569
    45
  check(firstNode == lastNode,
kpeter@639
    46
      "checkDiEulerIt: First and last nodes are not the same");
ladanyi@569
    47
ladanyi@569
    48
  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
ladanyi@569
    49
  {
ladanyi@569
    50
    check(visitationNumber[a] == 1,
kpeter@639
    51
        "checkDiEulerIt: Not visited or multiple times visited arc found");
ladanyi@569
    52
  }
ladanyi@569
    53
}
ladanyi@569
    54
ladanyi@569
    55
template <typename Graph>
kpeter@639
    56
void checkEulerIt(const Graph& g,
kpeter@639
    57
                  const typename Graph::Node& start = INVALID)
ladanyi@569
    58
{
kpeter@578
    59
  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
ladanyi@569
    60
kpeter@639
    61
  EulerIt<Graph> e(g, start);
kpeter@639
    62
  if (e == INVALID) return;
kpeter@639
    63
  typename Graph::Node firstNode = g.source(typename Graph::Arc(e));
kpeter@639
    64
  typename Graph::Node lastNode = g.target(typename Graph::Arc(e));
kpeter@639
    65
  if (start != INVALID) {
kpeter@639
    66
    check(firstNode == start, "checkEulerIt: Wrong first node");
kpeter@639
    67
  }
ladanyi@569
    68
kpeter@639
    69
  for (; e != INVALID; ++e) {
kpeter@639
    70
    if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
ladanyi@569
    71
    ++visitationNumber[e];
ladanyi@569
    72
  }
ladanyi@569
    73
ladanyi@569
    74
  check(firstNode == lastNode,
kpeter@639
    75
      "checkEulerIt: First and last nodes are not the same");
ladanyi@569
    76
ladanyi@569
    77
  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
ladanyi@569
    78
  {
ladanyi@569
    79
    check(visitationNumber[e] == 1,
kpeter@639
    80
        "checkEulerIt: Not visited or multiple times visited edge found");
ladanyi@569
    81
  }
ladanyi@569
    82
}
ladanyi@569
    83
ladanyi@569
    84
int main()
ladanyi@569
    85
{
ladanyi@569
    86
  typedef ListDigraph Digraph;
kpeter@639
    87
  typedef Undirector<Digraph> Graph;
alpar@956
    88
kpeter@639
    89
  {
kpeter@639
    90
    Digraph d;
kpeter@639
    91
    Graph g(d);
alpar@956
    92
kpeter@639
    93
    checkDiEulerIt(d);
kpeter@639
    94
    checkDiEulerIt(g);
kpeter@639
    95
    checkEulerIt(g);
ladanyi@569
    96
kpeter@639
    97
    check(eulerian(d), "This graph is Eulerian");
kpeter@639
    98
    check(eulerian(g), "This graph is Eulerian");
kpeter@639
    99
  }
ladanyi@569
   100
  {
kpeter@639
   101
    Digraph d;
kpeter@639
   102
    Graph g(d);
kpeter@639
   103
    Digraph::Node n = d.addNode();
alpar@1257
   104
    ::lemon::ignore_unused_variable_warning(n);
alpar@1270
   105
kpeter@639
   106
    checkDiEulerIt(d);
kpeter@639
   107
    checkDiEulerIt(g);
kpeter@639
   108
    checkEulerIt(g);
ladanyi@569
   109
kpeter@639
   110
    check(eulerian(d), "This graph is Eulerian");
kpeter@639
   111
    check(eulerian(g), "This graph is Eulerian");
ladanyi@569
   112
  }
kpeter@639
   113
  {
kpeter@639
   114
    Digraph d;
kpeter@639
   115
    Graph g(d);
kpeter@639
   116
    Digraph::Node n = d.addNode();
kpeter@639
   117
    d.addArc(n, n);
ladanyi@569
   118
kpeter@639
   119
    checkDiEulerIt(d);
kpeter@639
   120
    checkDiEulerIt(g);
kpeter@639
   121
    checkEulerIt(g);
kpeter@639
   122
kpeter@639
   123
    check(eulerian(d), "This graph is Eulerian");
kpeter@639
   124
    check(eulerian(g), "This graph is Eulerian");
kpeter@639
   125
  }
ladanyi@569
   126
  {
kpeter@639
   127
    Digraph d;
kpeter@639
   128
    Graph g(d);
kpeter@639
   129
    Digraph::Node n1 = d.addNode();
kpeter@639
   130
    Digraph::Node n2 = d.addNode();
kpeter@639
   131
    Digraph::Node n3 = d.addNode();
alpar@956
   132
kpeter@639
   133
    d.addArc(n1, n2);
kpeter@639
   134
    d.addArc(n2, n1);
kpeter@639
   135
    d.addArc(n2, n3);
kpeter@639
   136
    d.addArc(n3, n2);
ladanyi@569
   137
kpeter@639
   138
    checkDiEulerIt(d);
kpeter@639
   139
    checkDiEulerIt(d, n2);
kpeter@639
   140
    checkDiEulerIt(g);
kpeter@639
   141
    checkDiEulerIt(g, n2);
kpeter@639
   142
    checkEulerIt(g);
kpeter@639
   143
    checkEulerIt(g, n2);
ladanyi@569
   144
kpeter@639
   145
    check(eulerian(d), "This graph is Eulerian");
kpeter@639
   146
    check(eulerian(g), "This graph is Eulerian");
ladanyi@569
   147
  }
kpeter@639
   148
  {
kpeter@639
   149
    Digraph d;
kpeter@639
   150
    Graph g(d);
kpeter@639
   151
    Digraph::Node n1 = d.addNode();
kpeter@639
   152
    Digraph::Node n2 = d.addNode();
kpeter@639
   153
    Digraph::Node n3 = d.addNode();
kpeter@639
   154
    Digraph::Node n4 = d.addNode();
kpeter@639
   155
    Digraph::Node n5 = d.addNode();
kpeter@639
   156
    Digraph::Node n6 = d.addNode();
alpar@956
   157
kpeter@639
   158
    d.addArc(n1, n2);
kpeter@639
   159
    d.addArc(n2, n4);
kpeter@639
   160
    d.addArc(n1, n3);
kpeter@639
   161
    d.addArc(n3, n4);
kpeter@639
   162
    d.addArc(n4, n1);
kpeter@639
   163
    d.addArc(n3, n5);
kpeter@639
   164
    d.addArc(n5, n2);
kpeter@639
   165
    d.addArc(n4, n6);
kpeter@639
   166
    d.addArc(n2, n6);
kpeter@639
   167
    d.addArc(n6, n1);
kpeter@639
   168
    d.addArc(n6, n3);
ladanyi@569
   169
kpeter@639
   170
    checkDiEulerIt(d);
kpeter@639
   171
    checkDiEulerIt(d, n1);
kpeter@639
   172
    checkDiEulerIt(d, n5);
kpeter@639
   173
kpeter@639
   174
    checkDiEulerIt(g);
kpeter@639
   175
    checkDiEulerIt(g, n1);
kpeter@639
   176
    checkDiEulerIt(g, n5);
kpeter@639
   177
    checkEulerIt(g);
kpeter@639
   178
    checkEulerIt(g, n1);
kpeter@639
   179
    checkEulerIt(g, n5);
kpeter@639
   180
kpeter@639
   181
    check(eulerian(d), "This graph is Eulerian");
kpeter@639
   182
    check(eulerian(g), "This graph is Eulerian");
kpeter@639
   183
  }
ladanyi@569
   184
  {
kpeter@639
   185
    Digraph d;
kpeter@639
   186
    Graph g(d);
kpeter@639
   187
    Digraph::Node n0 = d.addNode();
kpeter@639
   188
    Digraph::Node n1 = d.addNode();
kpeter@639
   189
    Digraph::Node n2 = d.addNode();
kpeter@639
   190
    Digraph::Node n3 = d.addNode();
kpeter@639
   191
    Digraph::Node n4 = d.addNode();
kpeter@639
   192
    Digraph::Node n5 = d.addNode();
alpar@1257
   193
    ::lemon::ignore_unused_variable_warning(n0,n4,n5);
alpar@1157
   194
kpeter@639
   195
    d.addArc(n1, n2);
kpeter@639
   196
    d.addArc(n2, n3);
kpeter@639
   197
    d.addArc(n3, n1);
ladanyi@569
   198
kpeter@639
   199
    checkDiEulerIt(d);
kpeter@639
   200
    checkDiEulerIt(d, n2);
ladanyi@569
   201
kpeter@639
   202
    checkDiEulerIt(g);
kpeter@639
   203
    checkDiEulerIt(g, n2);
kpeter@639
   204
    checkEulerIt(g);
kpeter@639
   205
    checkEulerIt(g, n2);
kpeter@639
   206
kpeter@639
   207
    check(!eulerian(d), "This graph is not Eulerian");
kpeter@639
   208
    check(!eulerian(g), "This graph is not Eulerian");
ladanyi@569
   209
  }
kpeter@639
   210
  {
kpeter@639
   211
    Digraph d;
kpeter@639
   212
    Graph g(d);
kpeter@639
   213
    Digraph::Node n1 = d.addNode();
kpeter@639
   214
    Digraph::Node n2 = d.addNode();
kpeter@639
   215
    Digraph::Node n3 = d.addNode();
alpar@956
   216
kpeter@639
   217
    d.addArc(n1, n2);
kpeter@639
   218
    d.addArc(n2, n3);
ladanyi@569
   219
kpeter@639
   220
    check(!eulerian(d), "This graph is not Eulerian");
kpeter@639
   221
    check(!eulerian(g), "This graph is not Eulerian");
ladanyi@569
   222
  }
ladanyi@569
   223
ladanyi@569
   224
  return 0;
ladanyi@569
   225
}