test/graph_utils_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 20 Feb 2009 21:37:19 +0000
changeset 517 2b6d5d22bb23
parent 220 a5d8c039f218
child 572 be6646ac5d89
permissions -rw-r--r--
Merge
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@139
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@139
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
deba@139
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@139
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@139
     8
 *
deba@139
     9
 * Permission to use, modify and distribute this software is granted
deba@139
    10
 * provided that this copyright notice appears in all copies. For
deba@139
    11
 * precise terms see the accompanying LICENSE file.
deba@139
    12
 *
deba@139
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@139
    14
 * express or implied, and with no claim as to its suitability for any
deba@139
    15
 * purpose.
deba@139
    16
 *
deba@139
    17
 */
deba@139
    18
kpeter@171
    19
#include <cstdlib>
kpeter@171
    20
#include <ctime>
deba@139
    21
kpeter@171
    22
#include <lemon/random.h>
deba@139
    23
#include <lemon/list_graph.h>
deba@139
    24
#include <lemon/smart_graph.h>
deba@220
    25
#include <lemon/maps.h>
deba@139
    26
kpeter@171
    27
#include "graph_test.h"
deba@139
    28
#include "test_tools.h"
deba@139
    29
deba@139
    30
using namespace lemon;
deba@139
    31
kpeter@171
    32
template <typename Digraph>
kpeter@171
    33
void checkFindArcs() {
kpeter@171
    34
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@171
    35
kpeter@171
    36
  {
kpeter@171
    37
    Digraph digraph;
kpeter@171
    38
    for (int i = 0; i < 10; ++i) {
kpeter@171
    39
      digraph.addNode();
kpeter@171
    40
    }
kpeter@171
    41
    DescriptorMap<Digraph, Node> nodes(digraph);
kpeter@171
    42
    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
kpeter@171
    43
    for (int i = 0; i < 100; ++i) {
kpeter@171
    44
      int src = rnd[invNodes.size()];
kpeter@171
    45
      int trg = rnd[invNodes.size()];
kpeter@171
    46
      digraph.addArc(invNodes[src], invNodes[trg]);
kpeter@171
    47
    }
kpeter@171
    48
    typename Digraph::template ArcMap<bool> found(digraph, false);
kpeter@171
    49
    DescriptorMap<Digraph, Arc> arcs(digraph);
kpeter@171
    50
    for (NodeIt src(digraph); src != INVALID; ++src) {
kpeter@171
    51
      for (NodeIt trg(digraph); trg != INVALID; ++trg) {
kpeter@171
    52
        for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
kpeter@171
    53
          check(digraph.source(con) == src, "Wrong source.");
kpeter@171
    54
          check(digraph.target(con) == trg, "Wrong target.");
kpeter@171
    55
          check(found[con] == false, "The arc found already.");
kpeter@171
    56
          found[con] = true;
kpeter@171
    57
        }
kpeter@171
    58
      }
kpeter@171
    59
    }
kpeter@171
    60
    for (ArcIt it(digraph); it != INVALID; ++it) {
kpeter@171
    61
      check(found[it] == true, "The arc is not found.");
kpeter@171
    62
    }
kpeter@171
    63
  }
kpeter@171
    64
kpeter@171
    65
  {
kpeter@171
    66
    int num = 5;
kpeter@171
    67
    Digraph fg;
kpeter@171
    68
    std::vector<Node> nodes;
kpeter@171
    69
    for (int i = 0; i < num; ++i) {
kpeter@171
    70
      nodes.push_back(fg.addNode());
kpeter@171
    71
    }
kpeter@171
    72
    for (int i = 0; i < num * num; ++i) {
kpeter@171
    73
      fg.addArc(nodes[i / num], nodes[i % num]);
kpeter@171
    74
    }
kpeter@171
    75
    check(countNodes(fg) == num, "Wrong node number.");
kpeter@171
    76
    check(countArcs(fg) == num*num, "Wrong arc number.");
kpeter@171
    77
    for (NodeIt src(fg); src != INVALID; ++src) {
kpeter@171
    78
      for (NodeIt trg(fg); trg != INVALID; ++trg) {
kpeter@171
    79
        ConArcIt<Digraph> con(fg, src, trg);
kpeter@171
    80
        check(con != INVALID, "There is no connecting arc.");
kpeter@171
    81
        check(fg.source(con) == src, "Wrong source.");
kpeter@171
    82
        check(fg.target(con) == trg, "Wrong target.");
kpeter@171
    83
        check(++con == INVALID, "There is more connecting arc.");
kpeter@171
    84
      }
kpeter@171
    85
    }
kpeter@171
    86
    ArcLookUp<Digraph> al1(fg);
kpeter@171
    87
    DynArcLookUp<Digraph> al2(fg);
kpeter@171
    88
    AllArcLookUp<Digraph> al3(fg);
kpeter@171
    89
    for (NodeIt src(fg); src != INVALID; ++src) {
kpeter@171
    90
      for (NodeIt trg(fg); trg != INVALID; ++trg) {
kpeter@171
    91
        Arc con1 = al1(src, trg);
kpeter@171
    92
        Arc con2 = al2(src, trg);
kpeter@171
    93
        Arc con3 = al3(src, trg);
kpeter@171
    94
        Arc con4 = findArc(fg, src, trg);
alpar@210
    95
        check(con1 == con2 && con2 == con3 && con3 == con4,
alpar@210
    96
              "Different results.")
kpeter@171
    97
        check(con1 != INVALID, "There is no connecting arc.");
kpeter@171
    98
        check(fg.source(con1) == src, "Wrong source.");
kpeter@171
    99
        check(fg.target(con1) == trg, "Wrong target.");
alpar@210
   100
        check(al3(src, trg, con3) == INVALID,
alpar@210
   101
              "There is more connecting arc.");
alpar@210
   102
        check(findArc(fg, src, trg, con4) == INVALID,
alpar@210
   103
              "There is more connecting arc.");
kpeter@171
   104
      }
kpeter@171
   105
    }
kpeter@171
   106
  }
kpeter@171
   107
}
kpeter@171
   108
kpeter@171
   109
template <typename Graph>
kpeter@171
   110
void checkFindEdges() {
kpeter@171
   111
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
kpeter@171
   112
  Graph graph;
kpeter@171
   113
  for (int i = 0; i < 10; ++i) {
kpeter@171
   114
    graph.addNode();
kpeter@171
   115
  }
kpeter@171
   116
  DescriptorMap<Graph, Node> nodes(graph);
kpeter@171
   117
  typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
kpeter@171
   118
  for (int i = 0; i < 100; ++i) {
kpeter@171
   119
    int src = rnd[invNodes.size()];
kpeter@171
   120
    int trg = rnd[invNodes.size()];
kpeter@171
   121
    graph.addEdge(invNodes[src], invNodes[trg]);
kpeter@171
   122
  }
kpeter@171
   123
  typename Graph::template EdgeMap<int> found(graph, 0);
kpeter@171
   124
  DescriptorMap<Graph, Edge> edges(graph);
kpeter@171
   125
  for (NodeIt src(graph); src != INVALID; ++src) {
kpeter@171
   126
    for (NodeIt trg(graph); trg != INVALID; ++trg) {
kpeter@171
   127
      for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
kpeter@171
   128
        check( (graph.u(con) == src && graph.v(con) == trg) ||
alpar@210
   129
               (graph.v(con) == src && graph.u(con) == trg),
alpar@210
   130
               "Wrong end nodes.");
kpeter@171
   131
        ++found[con];
kpeter@171
   132
        check(found[con] <= 2, "The edge found more than twice.");
kpeter@171
   133
      }
kpeter@171
   134
    }
kpeter@171
   135
  }
kpeter@171
   136
  for (EdgeIt it(graph); it != INVALID; ++it) {
kpeter@171
   137
    check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
kpeter@171
   138
           (graph.u(it) == graph.v(it) && found[it] == 1),
kpeter@171
   139
           "The edge is not found correctly.");
kpeter@171
   140
  }
kpeter@171
   141
}
kpeter@171
   142
kpeter@171
   143
template <class Digraph>
kpeter@171
   144
void checkDeg()
deba@139
   145
{
kpeter@171
   146
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@209
   147
kpeter@171
   148
  const int nodeNum = 10;
kpeter@171
   149
  const int arcNum = 100;
kpeter@171
   150
  Digraph digraph;
kpeter@171
   151
  InDegMap<Digraph> inDeg(digraph);
kpeter@171
   152
  OutDegMap<Digraph> outDeg(digraph);
kpeter@171
   153
  std::vector<Node> nodes(nodeNum);
kpeter@171
   154
  for (int i = 0; i < nodeNum; ++i) {
kpeter@171
   155
    nodes[i] = digraph.addNode();
kpeter@171
   156
  }
kpeter@171
   157
  std::vector<Arc> arcs(arcNum);
kpeter@171
   158
  for (int i = 0; i < arcNum; ++i) {
kpeter@171
   159
    arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
kpeter@171
   160
  }
kpeter@171
   161
  for (int i = 0; i < nodeNum; ++i) {
alpar@209
   162
    check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
kpeter@171
   163
          "Wrong in degree map");
kpeter@171
   164
  }
kpeter@171
   165
  for (int i = 0; i < nodeNum; ++i) {
alpar@209
   166
    check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
kpeter@171
   167
          "Wrong out degree map");
kpeter@171
   168
  }
kpeter@171
   169
}
kpeter@171
   170
kpeter@171
   171
template <class Digraph>
kpeter@171
   172
void checkSnapDeg()
kpeter@171
   173
{
kpeter@171
   174
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
kpeter@171
   175
kpeter@171
   176
  Digraph g;
kpeter@171
   177
  Node n1=g.addNode();
kpeter@171
   178
  Node n2=g.addNode();
alpar@209
   179
kpeter@171
   180
  InDegMap<Digraph> ind(g);
alpar@209
   181
deba@139
   182
  g.addArc(n1,n2);
alpar@209
   183
kpeter@171
   184
  typename Digraph::Snapshot snap(g);
alpar@209
   185
kpeter@171
   186
  OutDegMap<Digraph> outd(g);
alpar@209
   187
deba@139
   188
  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
deba@139
   189
  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
deba@139
   190
deba@139
   191
  g.addArc(n1,n2);
deba@139
   192
  g.addArc(n2,n1);
kpeter@171
   193
deba@139
   194
  check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
deba@139
   195
  check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
deba@139
   196
deba@139
   197
  snap.restore();
deba@139
   198
deba@139
   199
  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
deba@139
   200
  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
deba@139
   201
}
deba@139
   202
deba@139
   203
int main() {
kpeter@171
   204
  // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
kpeter@171
   205
  checkFindArcs<ListDigraph>();
kpeter@171
   206
  checkFindArcs<SmartDigraph>();
kpeter@171
   207
  checkFindEdges<ListGraph>();
kpeter@171
   208
  checkFindEdges<SmartGraph>();
deba@139
   209
kpeter@171
   210
  // Checking In/OutDegMap (and Snapshot feature)
kpeter@171
   211
  checkDeg<ListDigraph>();
kpeter@171
   212
  checkDeg<SmartDigraph>();
deba@139
   213
  checkSnapDeg<ListDigraph>();
deba@139
   214
  checkSnapDeg<SmartDigraph>();
deba@139
   215
deba@139
   216
  return 0;
deba@139
   217
}