test/graph_utils_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 220 a5d8c039f218
child 572 be6646ac5d89
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
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
}