test/euler_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 30 Jul 2013 15:24:45 +0200
changeset 1071 879fcb781086
parent 877 141f9c0db4a3
parent 997 761fe0846f49
child 1084 8b2d4e5d96e4
permissions -rw-r--r--
Merge #454
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
 *
alpar@877
     5
 * Copyright (C) 2003-2010
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>
kpeter@592
    21
#include <lemon/adaptors.h>
kpeter@592
    22
#include "test_tools.h"
ladanyi@522
    23
ladanyi@522
    24
using namespace lemon;
ladanyi@522
    25
ladanyi@522
    26
template <typename Digraph>
kpeter@592
    27
void checkDiEulerIt(const Digraph& g,
kpeter@592
    28
                    const typename Digraph::Node& start = INVALID)
ladanyi@522
    29
{
kpeter@531
    30
  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
ladanyi@522
    31
kpeter@592
    32
  DiEulerIt<Digraph> e(g, start);
kpeter@592
    33
  if (e == INVALID) return;
ladanyi@522
    34
  typename Digraph::Node firstNode = g.source(e);
kpeter@531
    35
  typename Digraph::Node lastNode = g.target(e);
kpeter@592
    36
  if (start != INVALID) {
kpeter@592
    37
    check(firstNode == start, "checkDiEulerIt: Wrong first node");
kpeter@592
    38
  }
ladanyi@522
    39
kpeter@592
    40
  for (; e != INVALID; ++e) {
kpeter@592
    41
    if (e != INVALID) lastNode = g.target(e);
ladanyi@522
    42
    ++visitationNumber[e];
ladanyi@522
    43
  }
ladanyi@522
    44
ladanyi@522
    45
  check(firstNode == lastNode,
kpeter@592
    46
      "checkDiEulerIt: First and last nodes are not the same");
ladanyi@522
    47
ladanyi@522
    48
  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
ladanyi@522
    49
  {
ladanyi@522
    50
    check(visitationNumber[a] == 1,
kpeter@592
    51
        "checkDiEulerIt: Not visited or multiple times visited arc found");
ladanyi@522
    52
  }
ladanyi@522
    53
}
ladanyi@522
    54
ladanyi@522
    55
template <typename Graph>
kpeter@592
    56
void checkEulerIt(const Graph& g,
kpeter@592
    57
                  const typename Graph::Node& start = INVALID)
ladanyi@522
    58
{
kpeter@531
    59
  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
ladanyi@522
    60
kpeter@592
    61
  EulerIt<Graph> e(g, start);
kpeter@592
    62
  if (e == INVALID) return;
kpeter@592
    63
  typename Graph::Node firstNode = g.source(typename Graph::Arc(e));
kpeter@592
    64
  typename Graph::Node lastNode = g.target(typename Graph::Arc(e));
kpeter@592
    65
  if (start != INVALID) {
kpeter@592
    66
    check(firstNode == start, "checkEulerIt: Wrong first node");
kpeter@592
    67
  }
ladanyi@522
    68
kpeter@592
    69
  for (; e != INVALID; ++e) {
kpeter@592
    70
    if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
ladanyi@522
    71
    ++visitationNumber[e];
ladanyi@522
    72
  }
ladanyi@522
    73
ladanyi@522
    74
  check(firstNode == lastNode,
kpeter@592
    75
      "checkEulerIt: First and last nodes are not the same");
ladanyi@522
    76
ladanyi@522
    77
  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
ladanyi@522
    78
  {
ladanyi@522
    79
    check(visitationNumber[e] == 1,
kpeter@592
    80
        "checkEulerIt: Not visited or multiple times visited edge found");
ladanyi@522
    81
  }
ladanyi@522
    82
}
ladanyi@522
    83
ladanyi@522
    84
int main()
ladanyi@522
    85
{
ladanyi@522
    86
  typedef ListDigraph Digraph;
kpeter@592
    87
  typedef Undirector<Digraph> Graph;
alpar@877
    88
kpeter@592
    89
  {
kpeter@592
    90
    Digraph d;
kpeter@592
    91
    Graph g(d);
alpar@877
    92
kpeter@592
    93
    checkDiEulerIt(d);
kpeter@592
    94
    checkDiEulerIt(g);
kpeter@592
    95
    checkEulerIt(g);
ladanyi@522
    96
kpeter@592
    97
    check(eulerian(d), "This graph is Eulerian");
kpeter@592
    98
    check(eulerian(g), "This graph is Eulerian");
kpeter@592
    99
  }
ladanyi@522
   100
  {
kpeter@592
   101
    Digraph d;
kpeter@592
   102
    Graph g(d);
kpeter@592
   103
    Digraph::Node n = d.addNode();
alpar@997
   104
    ignore_unused_variable_warning(n);
alpar@997
   105
  
kpeter@592
   106
    checkDiEulerIt(d);
kpeter@592
   107
    checkDiEulerIt(g);
kpeter@592
   108
    checkEulerIt(g);
ladanyi@522
   109
kpeter@592
   110
    check(eulerian(d), "This graph is Eulerian");
kpeter@592
   111
    check(eulerian(g), "This graph is Eulerian");
ladanyi@522
   112
  }
kpeter@592
   113
  {
kpeter@592
   114
    Digraph d;
kpeter@592
   115
    Graph g(d);
kpeter@592
   116
    Digraph::Node n = d.addNode();
kpeter@592
   117
    d.addArc(n, n);
ladanyi@522
   118
kpeter@592
   119
    checkDiEulerIt(d);
kpeter@592
   120
    checkDiEulerIt(g);
kpeter@592
   121
    checkEulerIt(g);
kpeter@592
   122
kpeter@592
   123
    check(eulerian(d), "This graph is Eulerian");
kpeter@592
   124
    check(eulerian(g), "This graph is Eulerian");
kpeter@592
   125
  }
ladanyi@522
   126
  {
kpeter@592
   127
    Digraph d;
kpeter@592
   128
    Graph g(d);
kpeter@592
   129
    Digraph::Node n1 = d.addNode();
kpeter@592
   130
    Digraph::Node n2 = d.addNode();
kpeter@592
   131
    Digraph::Node n3 = d.addNode();
alpar@877
   132
kpeter@592
   133
    d.addArc(n1, n2);
kpeter@592
   134
    d.addArc(n2, n1);
kpeter@592
   135
    d.addArc(n2, n3);
kpeter@592
   136
    d.addArc(n3, n2);
ladanyi@522
   137
kpeter@592
   138
    checkDiEulerIt(d);
kpeter@592
   139
    checkDiEulerIt(d, n2);
kpeter@592
   140
    checkDiEulerIt(g);
kpeter@592
   141
    checkDiEulerIt(g, n2);
kpeter@592
   142
    checkEulerIt(g);
kpeter@592
   143
    checkEulerIt(g, n2);
ladanyi@522
   144
kpeter@592
   145
    check(eulerian(d), "This graph is Eulerian");
kpeter@592
   146
    check(eulerian(g), "This graph is Eulerian");
ladanyi@522
   147
  }
kpeter@592
   148
  {
kpeter@592
   149
    Digraph d;
kpeter@592
   150
    Graph g(d);
kpeter@592
   151
    Digraph::Node n1 = d.addNode();
kpeter@592
   152
    Digraph::Node n2 = d.addNode();
kpeter@592
   153
    Digraph::Node n3 = d.addNode();
kpeter@592
   154
    Digraph::Node n4 = d.addNode();
kpeter@592
   155
    Digraph::Node n5 = d.addNode();
kpeter@592
   156
    Digraph::Node n6 = d.addNode();
alpar@877
   157
kpeter@592
   158
    d.addArc(n1, n2);
kpeter@592
   159
    d.addArc(n2, n4);
kpeter@592
   160
    d.addArc(n1, n3);
kpeter@592
   161
    d.addArc(n3, n4);
kpeter@592
   162
    d.addArc(n4, n1);
kpeter@592
   163
    d.addArc(n3, n5);
kpeter@592
   164
    d.addArc(n5, n2);
kpeter@592
   165
    d.addArc(n4, n6);
kpeter@592
   166
    d.addArc(n2, n6);
kpeter@592
   167
    d.addArc(n6, n1);
kpeter@592
   168
    d.addArc(n6, n3);
ladanyi@522
   169
kpeter@592
   170
    checkDiEulerIt(d);
kpeter@592
   171
    checkDiEulerIt(d, n1);
kpeter@592
   172
    checkDiEulerIt(d, n5);
kpeter@592
   173
kpeter@592
   174
    checkDiEulerIt(g);
kpeter@592
   175
    checkDiEulerIt(g, n1);
kpeter@592
   176
    checkDiEulerIt(g, n5);
kpeter@592
   177
    checkEulerIt(g);
kpeter@592
   178
    checkEulerIt(g, n1);
kpeter@592
   179
    checkEulerIt(g, n5);
kpeter@592
   180
kpeter@592
   181
    check(eulerian(d), "This graph is Eulerian");
kpeter@592
   182
    check(eulerian(g), "This graph is Eulerian");
kpeter@592
   183
  }
ladanyi@522
   184
  {
kpeter@592
   185
    Digraph d;
kpeter@592
   186
    Graph g(d);
kpeter@592
   187
    Digraph::Node n0 = d.addNode();
kpeter@592
   188
    Digraph::Node n1 = d.addNode();
kpeter@592
   189
    Digraph::Node n2 = d.addNode();
kpeter@592
   190
    Digraph::Node n3 = d.addNode();
kpeter@592
   191
    Digraph::Node n4 = d.addNode();
kpeter@592
   192
    Digraph::Node n5 = d.addNode();
alpar@997
   193
    ignore_unused_variable_warning(n0,n4,n5);
alpar@997
   194
kpeter@592
   195
    d.addArc(n1, n2);
kpeter@592
   196
    d.addArc(n2, n3);
kpeter@592
   197
    d.addArc(n3, n1);
ladanyi@522
   198
kpeter@592
   199
    checkDiEulerIt(d);
kpeter@592
   200
    checkDiEulerIt(d, n2);
ladanyi@522
   201
kpeter@592
   202
    checkDiEulerIt(g);
kpeter@592
   203
    checkDiEulerIt(g, n2);
kpeter@592
   204
    checkEulerIt(g);
kpeter@592
   205
    checkEulerIt(g, n2);
kpeter@592
   206
kpeter@592
   207
    check(!eulerian(d), "This graph is not Eulerian");
kpeter@592
   208
    check(!eulerian(g), "This graph is not Eulerian");
ladanyi@522
   209
  }
kpeter@592
   210
  {
kpeter@592
   211
    Digraph d;
kpeter@592
   212
    Graph g(d);
kpeter@592
   213
    Digraph::Node n1 = d.addNode();
kpeter@592
   214
    Digraph::Node n2 = d.addNode();
kpeter@592
   215
    Digraph::Node n3 = d.addNode();
alpar@877
   216
kpeter@592
   217
    d.addArc(n1, n2);
kpeter@592
   218
    d.addArc(n2, n3);
ladanyi@522
   219
kpeter@592
   220
    check(!eulerian(d), "This graph is not Eulerian");
kpeter@592
   221
    check(!eulerian(g), "This graph is not Eulerian");
ladanyi@522
   222
  }
ladanyi@522
   223
ladanyi@522
   224
  return 0;
ladanyi@522
   225
}