test/graph_copy_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 282 dc9e8d2c0df9
child 893 d395358592df
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@200
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@200
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
deba@200
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@200
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@200
     8
 *
deba@200
     9
 * Permission to use, modify and distribute this software is granted
deba@200
    10
 * provided that this copyright notice appears in all copies. For
deba@200
    11
 * precise terms see the accompanying LICENSE file.
deba@200
    12
 *
deba@200
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@200
    14
 * express or implied, and with no claim as to its suitability for any
deba@200
    15
 * purpose.
deba@200
    16
 *
deba@200
    17
 */
deba@200
    18
deba@200
    19
#include <lemon/smart_graph.h>
deba@200
    20
#include <lemon/list_graph.h>
deba@200
    21
#include <lemon/lgf_reader.h>
deba@200
    22
#include <lemon/error.h>
deba@200
    23
deba@200
    24
#include "test_tools.h"
deba@200
    25
deba@200
    26
using namespace std;
deba@200
    27
using namespace lemon;
deba@200
    28
deba@200
    29
void digraph_copy_test() {
deba@200
    30
  const int nn = 10;
deba@200
    31
deba@200
    32
  SmartDigraph from;
deba@200
    33
  SmartDigraph::NodeMap<int> fnm(from);
deba@200
    34
  SmartDigraph::ArcMap<int> fam(from);
deba@200
    35
  SmartDigraph::Node fn = INVALID;
deba@200
    36
  SmartDigraph::Arc fa = INVALID;
deba@200
    37
deba@200
    38
  std::vector<SmartDigraph::Node> fnv;
deba@200
    39
  for (int i = 0; i < nn; ++i) {
deba@200
    40
    SmartDigraph::Node node = from.addNode();
deba@200
    41
    fnv.push_back(node);
deba@200
    42
    fnm[node] = i * i;
deba@200
    43
    if (i == 0) fn = node;
deba@200
    44
  }
deba@200
    45
deba@200
    46
  for (int i = 0; i < nn; ++i) {
deba@200
    47
    for (int j = 0; j < nn; ++j) {
deba@200
    48
      SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);
deba@200
    49
      fam[arc] = i + j * j;
deba@200
    50
      if (i == 0 && j == 0) fa = arc;
deba@200
    51
    }
deba@200
    52
  }
deba@200
    53
deba@200
    54
  ListDigraph to;
deba@200
    55
  ListDigraph::NodeMap<int> tnm(to);
deba@200
    56
  ListDigraph::ArcMap<int> tam(to);
deba@200
    57
  ListDigraph::Node tn;
deba@200
    58
  ListDigraph::Arc ta;
deba@200
    59
deba@200
    60
  SmartDigraph::NodeMap<ListDigraph::Node> nr(from);
deba@200
    61
  SmartDigraph::ArcMap<ListDigraph::Arc> er(from);
deba@200
    62
deba@200
    63
  ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
deba@200
    64
  ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
deba@200
    65
kpeter@282
    66
  digraphCopy(from, to).
kpeter@282
    67
    nodeMap(fnm, tnm).arcMap(fam, tam).
deba@200
    68
    nodeRef(nr).arcRef(er).
deba@200
    69
    nodeCrossRef(ncr).arcCrossRef(ecr).
kpeter@282
    70
    node(fn, tn).arc(fa, ta).run();
deba@200
    71
deba@200
    72
  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
deba@200
    73
    check(ncr[nr[it]] == it, "Wrong copy.");
deba@200
    74
    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
deba@200
    75
  }
deba@200
    76
deba@200
    77
  for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {
deba@200
    78
    check(ecr[er[it]] == it, "Wrong copy.");
deba@200
    79
    check(fam[it] == tam[er[it]], "Wrong copy.");
deba@200
    80
    check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");
deba@200
    81
    check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");
deba@200
    82
  }
deba@200
    83
deba@200
    84
  for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {
deba@200
    85
    check(nr[ncr[it]] == it, "Wrong copy.");
deba@200
    86
  }
deba@200
    87
deba@200
    88
  for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
deba@200
    89
    check(er[ecr[it]] == it, "Wrong copy.");
deba@200
    90
  }
deba@200
    91
  check(tn == nr[fn], "Wrong copy.");
deba@200
    92
  check(ta == er[fa], "Wrong copy.");
deba@200
    93
}
deba@200
    94
deba@200
    95
void graph_copy_test() {
deba@200
    96
  const int nn = 10;
deba@200
    97
deba@200
    98
  SmartGraph from;
deba@200
    99
  SmartGraph::NodeMap<int> fnm(from);
deba@200
   100
  SmartGraph::ArcMap<int> fam(from);
deba@200
   101
  SmartGraph::EdgeMap<int> fem(from);
deba@200
   102
  SmartGraph::Node fn = INVALID;
deba@200
   103
  SmartGraph::Arc fa = INVALID;
deba@200
   104
  SmartGraph::Edge fe = INVALID;
deba@200
   105
deba@200
   106
  std::vector<SmartGraph::Node> fnv;
deba@200
   107
  for (int i = 0; i < nn; ++i) {
deba@200
   108
    SmartGraph::Node node = from.addNode();
deba@200
   109
    fnv.push_back(node);
deba@200
   110
    fnm[node] = i * i;
deba@200
   111
    if (i == 0) fn = node;
deba@200
   112
  }
deba@200
   113
deba@200
   114
  for (int i = 0; i < nn; ++i) {
deba@200
   115
    for (int j = 0; j < nn; ++j) {
deba@200
   116
      SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);
deba@200
   117
      fem[edge] = i * i + j * j;
deba@200
   118
      fam[from.direct(edge, true)] = i + j * j;
deba@200
   119
      fam[from.direct(edge, false)] = i * i + j;
deba@200
   120
      if (i == 0 && j == 0) fa = from.direct(edge, true);
deba@200
   121
      if (i == 0 && j == 0) fe = edge;
deba@200
   122
    }
deba@200
   123
  }
alpar@209
   124
deba@200
   125
  ListGraph to;
deba@200
   126
  ListGraph::NodeMap<int> tnm(to);
deba@200
   127
  ListGraph::ArcMap<int> tam(to);
deba@200
   128
  ListGraph::EdgeMap<int> tem(to);
deba@200
   129
  ListGraph::Node tn;
deba@200
   130
  ListGraph::Arc ta;
deba@200
   131
  ListGraph::Edge te;
deba@200
   132
deba@200
   133
  SmartGraph::NodeMap<ListGraph::Node> nr(from);
deba@200
   134
  SmartGraph::ArcMap<ListGraph::Arc> ar(from);
deba@200
   135
  SmartGraph::EdgeMap<ListGraph::Edge> er(from);
deba@200
   136
deba@200
   137
  ListGraph::NodeMap<SmartGraph::Node> ncr(to);
deba@200
   138
  ListGraph::ArcMap<SmartGraph::Arc> acr(to);
deba@200
   139
  ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
deba@200
   140
kpeter@282
   141
  graphCopy(from, to).
kpeter@282
   142
    nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).
deba@200
   143
    nodeRef(nr).arcRef(ar).edgeRef(er).
deba@200
   144
    nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
kpeter@282
   145
    node(fn, tn).arc(fa, ta).edge(fe, te).run();
deba@200
   146
deba@200
   147
  for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
deba@200
   148
    check(ncr[nr[it]] == it, "Wrong copy.");
deba@200
   149
    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
deba@200
   150
  }
deba@200
   151
deba@200
   152
  for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {
deba@200
   153
    check(acr[ar[it]] == it, "Wrong copy.");
deba@200
   154
    check(fam[it] == tam[ar[it]], "Wrong copy.");
deba@200
   155
    check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
deba@200
   156
    check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
deba@200
   157
  }
deba@200
   158
deba@200
   159
  for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) {
deba@200
   160
    check(ecr[er[it]] == it, "Wrong copy.");
deba@200
   161
    check(fem[it] == tem[er[it]], "Wrong copy.");
alpar@209
   162
    check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),
alpar@209
   163
          "Wrong copy.");
alpar@209
   164
    check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),
alpar@209
   165
          "Wrong copy.");
alpar@209
   166
    check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),
alpar@209
   167
          "Wrong copy.");
deba@200
   168
  }
deba@200
   169
deba@200
   170
  for (ListGraph::NodeIt it(to); it != INVALID; ++it) {
deba@200
   171
    check(nr[ncr[it]] == it, "Wrong copy.");
deba@200
   172
  }
deba@200
   173
deba@200
   174
  for (ListGraph::ArcIt it(to); it != INVALID; ++it) {
deba@200
   175
    check(ar[acr[it]] == it, "Wrong copy.");
deba@200
   176
  }
deba@200
   177
  for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {
deba@200
   178
    check(er[ecr[it]] == it, "Wrong copy.");
deba@200
   179
  }
deba@200
   180
  check(tn == nr[fn], "Wrong copy.");
deba@200
   181
  check(ta == ar[fa], "Wrong copy.");
deba@200
   182
  check(te == er[fe], "Wrong copy.");
deba@200
   183
}
deba@200
   184
deba@200
   185
deba@200
   186
int main() {
deba@200
   187
  digraph_copy_test();
deba@200
   188
  graph_copy_test();
deba@200
   189
alpar@209
   190
  return 0;
deba@200
   191
}