test/euler_test.cc
author Balazs Dezso <deba@inf.elte.hu>
Sun, 04 Oct 2009 00:28:42 +0200
changeset 746 e4554cd6b2bf
parent 531 ba7bafdc458d
child 877 141f9c0db4a3
child 997 761fe0846f49
permissions -rw-r--r--
Faster add row operation (#203)

One virtual function call instead of more
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>
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;
kpeter@592
    88
  
kpeter@592
    89
  {
kpeter@592
    90
    Digraph d;
kpeter@592
    91
    Graph g(d);
kpeter@592
    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();
ladanyi@522
   104
kpeter@592
   105
    checkDiEulerIt(d);
kpeter@592
   106
    checkDiEulerIt(g);
kpeter@592
   107
    checkEulerIt(g);
ladanyi@522
   108
kpeter@592
   109
    check(eulerian(d), "This graph is Eulerian");
kpeter@592
   110
    check(eulerian(g), "This graph is Eulerian");
ladanyi@522
   111
  }
kpeter@592
   112
  {
kpeter@592
   113
    Digraph d;
kpeter@592
   114
    Graph g(d);
kpeter@592
   115
    Digraph::Node n = d.addNode();
kpeter@592
   116
    d.addArc(n, n);
ladanyi@522
   117
kpeter@592
   118
    checkDiEulerIt(d);
kpeter@592
   119
    checkDiEulerIt(g);
kpeter@592
   120
    checkEulerIt(g);
kpeter@592
   121
kpeter@592
   122
    check(eulerian(d), "This graph is Eulerian");
kpeter@592
   123
    check(eulerian(g), "This graph is Eulerian");
kpeter@592
   124
  }
ladanyi@522
   125
  {
kpeter@592
   126
    Digraph d;
kpeter@592
   127
    Graph g(d);
kpeter@592
   128
    Digraph::Node n1 = d.addNode();
kpeter@592
   129
    Digraph::Node n2 = d.addNode();
kpeter@592
   130
    Digraph::Node n3 = d.addNode();
kpeter@592
   131
    
kpeter@592
   132
    d.addArc(n1, n2);
kpeter@592
   133
    d.addArc(n2, n1);
kpeter@592
   134
    d.addArc(n2, n3);
kpeter@592
   135
    d.addArc(n3, n2);
ladanyi@522
   136
kpeter@592
   137
    checkDiEulerIt(d);
kpeter@592
   138
    checkDiEulerIt(d, n2);
kpeter@592
   139
    checkDiEulerIt(g);
kpeter@592
   140
    checkDiEulerIt(g, n2);
kpeter@592
   141
    checkEulerIt(g);
kpeter@592
   142
    checkEulerIt(g, n2);
ladanyi@522
   143
kpeter@592
   144
    check(eulerian(d), "This graph is Eulerian");
kpeter@592
   145
    check(eulerian(g), "This graph is Eulerian");
ladanyi@522
   146
  }
kpeter@592
   147
  {
kpeter@592
   148
    Digraph d;
kpeter@592
   149
    Graph g(d);
kpeter@592
   150
    Digraph::Node n1 = d.addNode();
kpeter@592
   151
    Digraph::Node n2 = d.addNode();
kpeter@592
   152
    Digraph::Node n3 = d.addNode();
kpeter@592
   153
    Digraph::Node n4 = d.addNode();
kpeter@592
   154
    Digraph::Node n5 = d.addNode();
kpeter@592
   155
    Digraph::Node n6 = d.addNode();
kpeter@592
   156
    
kpeter@592
   157
    d.addArc(n1, n2);
kpeter@592
   158
    d.addArc(n2, n4);
kpeter@592
   159
    d.addArc(n1, n3);
kpeter@592
   160
    d.addArc(n3, n4);
kpeter@592
   161
    d.addArc(n4, n1);
kpeter@592
   162
    d.addArc(n3, n5);
kpeter@592
   163
    d.addArc(n5, n2);
kpeter@592
   164
    d.addArc(n4, n6);
kpeter@592
   165
    d.addArc(n2, n6);
kpeter@592
   166
    d.addArc(n6, n1);
kpeter@592
   167
    d.addArc(n6, n3);
ladanyi@522
   168
kpeter@592
   169
    checkDiEulerIt(d);
kpeter@592
   170
    checkDiEulerIt(d, n1);
kpeter@592
   171
    checkDiEulerIt(d, n5);
kpeter@592
   172
kpeter@592
   173
    checkDiEulerIt(g);
kpeter@592
   174
    checkDiEulerIt(g, n1);
kpeter@592
   175
    checkDiEulerIt(g, n5);
kpeter@592
   176
    checkEulerIt(g);
kpeter@592
   177
    checkEulerIt(g, n1);
kpeter@592
   178
    checkEulerIt(g, n5);
kpeter@592
   179
kpeter@592
   180
    check(eulerian(d), "This graph is Eulerian");
kpeter@592
   181
    check(eulerian(g), "This graph is Eulerian");
kpeter@592
   182
  }
ladanyi@522
   183
  {
kpeter@592
   184
    Digraph d;
kpeter@592
   185
    Graph g(d);
kpeter@592
   186
    Digraph::Node n0 = d.addNode();
kpeter@592
   187
    Digraph::Node n1 = d.addNode();
kpeter@592
   188
    Digraph::Node n2 = d.addNode();
kpeter@592
   189
    Digraph::Node n3 = d.addNode();
kpeter@592
   190
    Digraph::Node n4 = d.addNode();
kpeter@592
   191
    Digraph::Node n5 = d.addNode();
kpeter@592
   192
    
kpeter@592
   193
    d.addArc(n1, n2);
kpeter@592
   194
    d.addArc(n2, n3);
kpeter@592
   195
    d.addArc(n3, n1);
ladanyi@522
   196
kpeter@592
   197
    checkDiEulerIt(d);
kpeter@592
   198
    checkDiEulerIt(d, n2);
ladanyi@522
   199
kpeter@592
   200
    checkDiEulerIt(g);
kpeter@592
   201
    checkDiEulerIt(g, n2);
kpeter@592
   202
    checkEulerIt(g);
kpeter@592
   203
    checkEulerIt(g, n2);
kpeter@592
   204
kpeter@592
   205
    check(!eulerian(d), "This graph is not Eulerian");
kpeter@592
   206
    check(!eulerian(g), "This graph is not Eulerian");
ladanyi@522
   207
  }
kpeter@592
   208
  {
kpeter@592
   209
    Digraph d;
kpeter@592
   210
    Graph g(d);
kpeter@592
   211
    Digraph::Node n1 = d.addNode();
kpeter@592
   212
    Digraph::Node n2 = d.addNode();
kpeter@592
   213
    Digraph::Node n3 = d.addNode();
kpeter@592
   214
    
kpeter@592
   215
    d.addArc(n1, n2);
kpeter@592
   216
    d.addArc(n2, n3);
ladanyi@522
   217
kpeter@592
   218
    check(!eulerian(d), "This graph is not Eulerian");
kpeter@592
   219
    check(!eulerian(g), "This graph is not Eulerian");
ladanyi@522
   220
  }
ladanyi@522
   221
ladanyi@522
   222
  return 0;
ladanyi@522
   223
}