test/digraph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Mon, 03 Nov 2008 22:30:21 +0100
changeset 355 aa75d24ba7d0
parent 353 37557a46e298
child 364 b4a01426c0d9
permissions -rw-r--r--
Bug fix in FullDigraphBase::findArc()
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@57
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@57
     4
 *
alpar@107
     5
 * Copyright (C) 2003-2008
deba@57
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@57
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@57
     8
 *
deba@57
     9
 * Permission to use, modify and distribute this software is granted
deba@57
    10
 * provided that this copyright notice appears in all copies. For
deba@57
    11
 * precise terms see the accompanying LICENSE file.
deba@57
    12
 *
deba@57
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@57
    14
 * express or implied, and with no claim as to its suitability for any
deba@57
    15
 * purpose.
deba@57
    16
 *
deba@57
    17
 */
deba@57
    18
deba@57
    19
#include <lemon/concepts/digraph.h>
deba@57
    20
#include <lemon/list_graph.h>
kpeter@171
    21
#include <lemon/smart_graph.h>
deba@353
    22
#include <lemon/full_graph.h>
deba@57
    23
//#include <lemon/hypercube_graph.h>
deba@57
    24
deba@57
    25
#include "test_tools.h"
kpeter@171
    26
#include "graph_test.h"
deba@57
    27
deba@57
    28
using namespace lemon;
deba@57
    29
using namespace lemon::concepts;
deba@57
    30
deba@228
    31
template <class Digraph>
deba@228
    32
void checkDigraph() {
deba@228
    33
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
deba@228
    34
  Digraph G;
deba@228
    35
deba@228
    36
  checkGraphNodeList(G, 0);
deba@228
    37
  checkGraphArcList(G, 0);
deba@228
    38
deba@228
    39
  Node
deba@228
    40
    n1 = G.addNode(),
deba@228
    41
    n2 = G.addNode(),
deba@228
    42
    n3 = G.addNode();
deba@228
    43
  checkGraphNodeList(G, 3);
deba@228
    44
  checkGraphArcList(G, 0);
deba@228
    45
deba@228
    46
  Arc a1 = G.addArc(n1, n2);
deba@228
    47
  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
deba@228
    48
  checkGraphNodeList(G, 3);
deba@228
    49
  checkGraphArcList(G, 1);
deba@228
    50
deba@228
    51
  checkGraphOutArcList(G, n1, 1);
deba@228
    52
  checkGraphOutArcList(G, n2, 0);
deba@228
    53
  checkGraphOutArcList(G, n3, 0);
deba@228
    54
deba@228
    55
  checkGraphInArcList(G, n1, 0);
deba@228
    56
  checkGraphInArcList(G, n2, 1);
deba@228
    57
  checkGraphInArcList(G, n3, 0);
deba@228
    58
deba@228
    59
  checkGraphConArcList(G, 1);
deba@228
    60
deba@228
    61
  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
deba@228
    62
  checkGraphNodeList(G, 3);
deba@228
    63
  checkGraphArcList(G, 4);
deba@228
    64
deba@228
    65
  checkGraphOutArcList(G, n1, 1);
deba@228
    66
  checkGraphOutArcList(G, n2, 3);
deba@228
    67
  checkGraphOutArcList(G, n3, 0);
deba@228
    68
deba@228
    69
  checkGraphInArcList(G, n1, 1);
deba@228
    70
  checkGraphInArcList(G, n2, 1);
deba@228
    71
  checkGraphInArcList(G, n3, 2);
deba@228
    72
deba@228
    73
  checkGraphConArcList(G, 4);
deba@228
    74
deba@228
    75
  checkNodeIds(G);
deba@228
    76
  checkArcIds(G);
deba@228
    77
  checkGraphNodeMap(G);
deba@228
    78
  checkGraphArcMap(G);
deba@228
    79
deba@228
    80
}
deba@228
    81
deba@353
    82
void checkFullDigraph(int num) {
deba@353
    83
  typedef FullDigraph Digraph;
deba@353
    84
  DIGRAPH_TYPEDEFS(Digraph);
deba@353
    85
  Digraph G(num);
deba@353
    86
deba@353
    87
  checkGraphNodeList(G, num);
deba@353
    88
  checkGraphArcList(G, num * num);
deba@353
    89
deba@353
    90
  for (NodeIt n(G); n != INVALID; ++n) {
deba@353
    91
    checkGraphOutArcList(G, n, num);
deba@353
    92
    checkGraphInArcList(G, n, num);
deba@353
    93
  }
deba@353
    94
deba@353
    95
  checkGraphConArcList(G, num * num);
deba@353
    96
deba@353
    97
  checkNodeIds(G);
deba@353
    98
  checkArcIds(G);
deba@353
    99
  checkGraphNodeMap(G);
deba@353
   100
  checkGraphArcMap(G);
deba@353
   101
deba@353
   102
  for (int i = 0; i < G.nodeNum(); ++i) {
deba@353
   103
    check(G.index(G(i)) == i, "Wrong index");
deba@353
   104
  }
deba@353
   105
deba@353
   106
  for (NodeIt s(G); s != INVALID; ++s) {
deba@353
   107
    for (NodeIt t(G); t != INVALID; ++t) {
deba@353
   108
      Arc a = G.arc(s, t);
deba@353
   109
      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
deba@353
   110
    }
deba@353
   111
  }
deba@353
   112
deba@353
   113
}
deba@353
   114
deba@228
   115
deba@228
   116
void checkConcepts() {
kpeter@171
   117
  { // Checking digraph components
deba@57
   118
    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
deba@57
   119
alpar@209
   120
    checkConcept<IDableDigraphComponent<>,
deba@57
   121
      IDableDigraphComponent<> >();
deba@57
   122
alpar@209
   123
    checkConcept<IterableDigraphComponent<>,
deba@57
   124
      IterableDigraphComponent<> >();
deba@57
   125
alpar@209
   126
    checkConcept<MappableDigraphComponent<>,
deba@57
   127
      MappableDigraphComponent<> >();
deba@57
   128
  }
kpeter@171
   129
  { // Checking skeleton digraph
deba@57
   130
    checkConcept<Digraph, Digraph>();
deba@57
   131
  }
kpeter@171
   132
  { // Checking ListDigraph
kpeter@171
   133
    checkConcept<Digraph, ListDigraph>();
deba@57
   134
    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
deba@57
   135
    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
deba@57
   136
    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
deba@57
   137
    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
kpeter@171
   138
  }
kpeter@171
   139
  { // Checking SmartDigraph
kpeter@171
   140
    checkConcept<Digraph, SmartDigraph>();
kpeter@171
   141
    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
kpeter@171
   142
    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
kpeter@171
   143
    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
kpeter@171
   144
  }
kpeter@354
   145
  { // Checking FullDigraph
kpeter@354
   146
    checkConcept<Digraph, FullDigraph>();
kpeter@354
   147
  }
kpeter@171
   148
//  { // Checking HyperCubeDigraph
kpeter@171
   149
//    checkConcept<Digraph, HyperCubeDigraph>();
kpeter@171
   150
//  }
kpeter@171
   151
}
deba@57
   152
kpeter@171
   153
template <typename Digraph>
deba@228
   154
void checkDigraphValidity() {
kpeter@171
   155
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@171
   156
  Digraph g;
kpeter@171
   157
kpeter@171
   158
  Node
kpeter@171
   159
    n1 = g.addNode(),
kpeter@171
   160
    n2 = g.addNode(),
kpeter@171
   161
    n3 = g.addNode();
kpeter@171
   162
kpeter@171
   163
  Arc
kpeter@171
   164
    e1 = g.addArc(n1, n2),
kpeter@171
   165
    e2 = g.addArc(n2, n3);
kpeter@171
   166
kpeter@171
   167
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   168
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   169
kpeter@171
   170
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   171
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
kpeter@171
   172
}
kpeter@171
   173
kpeter@171
   174
template <typename Digraph>
deba@228
   175
void checkDigraphValidityErase() {
kpeter@171
   176
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@171
   177
  Digraph g;
kpeter@171
   178
kpeter@171
   179
  Node
kpeter@171
   180
    n1 = g.addNode(),
kpeter@171
   181
    n2 = g.addNode(),
kpeter@171
   182
    n3 = g.addNode();
kpeter@171
   183
kpeter@171
   184
  Arc
kpeter@171
   185
    e1 = g.addArc(n1, n2),
kpeter@171
   186
    e2 = g.addArc(n2, n3);
kpeter@171
   187
kpeter@171
   188
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   189
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   190
kpeter@171
   191
  g.erase(n1);
kpeter@171
   192
kpeter@171
   193
  check(!g.valid(n1), "Wrong validity check");
kpeter@171
   194
  check(g.valid(n2), "Wrong validity check");
kpeter@171
   195
  check(g.valid(n3), "Wrong validity check");
kpeter@171
   196
  check(!g.valid(e1), "Wrong validity check");
kpeter@171
   197
  check(g.valid(e2), "Wrong validity check");
kpeter@171
   198
kpeter@171
   199
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   200
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
kpeter@171
   201
}
kpeter@171
   202
deba@228
   203
void checkDigraphs() {
kpeter@171
   204
  { // Checking ListDigraph
deba@57
   205
    checkDigraph<ListDigraph>();
deba@228
   206
    checkDigraphValidityErase<ListDigraph>();
deba@57
   207
  }
kpeter@171
   208
  { // Checking SmartDigraph
kpeter@171
   209
    checkDigraph<SmartDigraph>();
deba@228
   210
    checkDigraphValidity<SmartDigraph>();
kpeter@171
   211
  }
deba@353
   212
  { // Checking FullDigraph
deba@353
   213
    checkFullDigraph(8);
deba@353
   214
  }
kpeter@171
   215
}
deba@57
   216
kpeter@171
   217
int main() {
deba@228
   218
  checkDigraphs();
deba@228
   219
  checkConcepts();
deba@57
   220
  return 0;
deba@57
   221
}