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