test/euler_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 25 Aug 2010 21:34:58 +0200
changeset 742 16d466589b54
parent 517 ba7bafdc458d
child 761 f1398882a928
child 792 761fe0846f49
permissions -rw-r--r--
Backport the CMAKE related changesets from the main branch

[e20fecd1945f] Add check target for CMake (#388)
[e74b5db4f2c6] Put the output of chg-len.py in the version string (#389)
[7d166b8b8018] Safer call of ./scripts/chg-len.py on Windows (#389)
[659ba4805a48] Make CMAKE config more consistent with configure.ac (#390)
[63e4468c680e] Add 'Maintainer' CMAKE build type (#388, #390)
[a725503acfe9] Allow CPACK configuration on all platforms
[10242c611190] Create and install lemon.pc (#393)
[48e29534cf03] The deafult target doesn't build lp_test and mip_test (#388)
[0fbbdd578c06] Full path for DoxygenLayout.xml in Doxyfile.in (#395)
[481496e6d71f] SOURCE_BROWSER Doxygen switch is configurable from CMAKE (#395)
[09282720100b] update-external-tags CMAKE target (#395)
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
 *
ladanyi@506
     5
 * Copyright (C) 2003-2009
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;
kpeter@584
    88
  
kpeter@584
    89
  {
kpeter@584
    90
    Digraph d;
kpeter@584
    91
    Graph g(d);
kpeter@584
    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();
ladanyi@506
   104
kpeter@584
   105
    checkDiEulerIt(d);
kpeter@584
   106
    checkDiEulerIt(g);
kpeter@584
   107
    checkEulerIt(g);
ladanyi@506
   108
kpeter@584
   109
    check(eulerian(d), "This graph is Eulerian");
kpeter@584
   110
    check(eulerian(g), "This graph is Eulerian");
ladanyi@506
   111
  }
kpeter@584
   112
  {
kpeter@584
   113
    Digraph d;
kpeter@584
   114
    Graph g(d);
kpeter@584
   115
    Digraph::Node n = d.addNode();
kpeter@584
   116
    d.addArc(n, n);
ladanyi@506
   117
kpeter@584
   118
    checkDiEulerIt(d);
kpeter@584
   119
    checkDiEulerIt(g);
kpeter@584
   120
    checkEulerIt(g);
kpeter@584
   121
kpeter@584
   122
    check(eulerian(d), "This graph is Eulerian");
kpeter@584
   123
    check(eulerian(g), "This graph is Eulerian");
kpeter@584
   124
  }
ladanyi@506
   125
  {
kpeter@584
   126
    Digraph d;
kpeter@584
   127
    Graph g(d);
kpeter@584
   128
    Digraph::Node n1 = d.addNode();
kpeter@584
   129
    Digraph::Node n2 = d.addNode();
kpeter@584
   130
    Digraph::Node n3 = d.addNode();
kpeter@584
   131
    
kpeter@584
   132
    d.addArc(n1, n2);
kpeter@584
   133
    d.addArc(n2, n1);
kpeter@584
   134
    d.addArc(n2, n3);
kpeter@584
   135
    d.addArc(n3, n2);
ladanyi@506
   136
kpeter@584
   137
    checkDiEulerIt(d);
kpeter@584
   138
    checkDiEulerIt(d, n2);
kpeter@584
   139
    checkDiEulerIt(g);
kpeter@584
   140
    checkDiEulerIt(g, n2);
kpeter@584
   141
    checkEulerIt(g);
kpeter@584
   142
    checkEulerIt(g, n2);
ladanyi@506
   143
kpeter@584
   144
    check(eulerian(d), "This graph is Eulerian");
kpeter@584
   145
    check(eulerian(g), "This graph is Eulerian");
ladanyi@506
   146
  }
kpeter@584
   147
  {
kpeter@584
   148
    Digraph d;
kpeter@584
   149
    Graph g(d);
kpeter@584
   150
    Digraph::Node n1 = d.addNode();
kpeter@584
   151
    Digraph::Node n2 = d.addNode();
kpeter@584
   152
    Digraph::Node n3 = d.addNode();
kpeter@584
   153
    Digraph::Node n4 = d.addNode();
kpeter@584
   154
    Digraph::Node n5 = d.addNode();
kpeter@584
   155
    Digraph::Node n6 = d.addNode();
kpeter@584
   156
    
kpeter@584
   157
    d.addArc(n1, n2);
kpeter@584
   158
    d.addArc(n2, n4);
kpeter@584
   159
    d.addArc(n1, n3);
kpeter@584
   160
    d.addArc(n3, n4);
kpeter@584
   161
    d.addArc(n4, n1);
kpeter@584
   162
    d.addArc(n3, n5);
kpeter@584
   163
    d.addArc(n5, n2);
kpeter@584
   164
    d.addArc(n4, n6);
kpeter@584
   165
    d.addArc(n2, n6);
kpeter@584
   166
    d.addArc(n6, n1);
kpeter@584
   167
    d.addArc(n6, n3);
ladanyi@506
   168
kpeter@584
   169
    checkDiEulerIt(d);
kpeter@584
   170
    checkDiEulerIt(d, n1);
kpeter@584
   171
    checkDiEulerIt(d, n5);
kpeter@584
   172
kpeter@584
   173
    checkDiEulerIt(g);
kpeter@584
   174
    checkDiEulerIt(g, n1);
kpeter@584
   175
    checkDiEulerIt(g, n5);
kpeter@584
   176
    checkEulerIt(g);
kpeter@584
   177
    checkEulerIt(g, n1);
kpeter@584
   178
    checkEulerIt(g, n5);
kpeter@584
   179
kpeter@584
   180
    check(eulerian(d), "This graph is Eulerian");
kpeter@584
   181
    check(eulerian(g), "This graph is Eulerian");
kpeter@584
   182
  }
ladanyi@506
   183
  {
kpeter@584
   184
    Digraph d;
kpeter@584
   185
    Graph g(d);
kpeter@584
   186
    Digraph::Node n0 = d.addNode();
kpeter@584
   187
    Digraph::Node n1 = d.addNode();
kpeter@584
   188
    Digraph::Node n2 = d.addNode();
kpeter@584
   189
    Digraph::Node n3 = d.addNode();
kpeter@584
   190
    Digraph::Node n4 = d.addNode();
kpeter@584
   191
    Digraph::Node n5 = d.addNode();
kpeter@584
   192
    
kpeter@584
   193
    d.addArc(n1, n2);
kpeter@584
   194
    d.addArc(n2, n3);
kpeter@584
   195
    d.addArc(n3, n1);
ladanyi@506
   196
kpeter@584
   197
    checkDiEulerIt(d);
kpeter@584
   198
    checkDiEulerIt(d, n2);
ladanyi@506
   199
kpeter@584
   200
    checkDiEulerIt(g);
kpeter@584
   201
    checkDiEulerIt(g, n2);
kpeter@584
   202
    checkEulerIt(g);
kpeter@584
   203
    checkEulerIt(g, n2);
kpeter@584
   204
kpeter@584
   205
    check(!eulerian(d), "This graph is not Eulerian");
kpeter@584
   206
    check(!eulerian(g), "This graph is not Eulerian");
ladanyi@506
   207
  }
kpeter@584
   208
  {
kpeter@584
   209
    Digraph d;
kpeter@584
   210
    Graph g(d);
kpeter@584
   211
    Digraph::Node n1 = d.addNode();
kpeter@584
   212
    Digraph::Node n2 = d.addNode();
kpeter@584
   213
    Digraph::Node n3 = d.addNode();
kpeter@584
   214
    
kpeter@584
   215
    d.addArc(n1, n2);
kpeter@584
   216
    d.addArc(n2, n3);
ladanyi@506
   217
kpeter@584
   218
    check(!eulerian(d), "This graph is not Eulerian");
kpeter@584
   219
    check(!eulerian(g), "This graph is not Eulerian");
ladanyi@506
   220
  }
ladanyi@506
   221
ladanyi@506
   222
  return 0;
ladanyi@506
   223
}