test/bfs_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 293 47fbc814aa31
child 585 65fbcf2f978a
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; -*-
alpar@100
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@100
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@100
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@100
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@100
     8
 *
alpar@100
     9
 * Permission to use, modify and distribute this software is granted
alpar@100
    10
 * provided that this copyright notice appears in all copies. For
alpar@100
    11
 * precise terms see the accompanying LICENSE file.
alpar@100
    12
 *
alpar@100
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@100
    14
 * express or implied, and with no claim as to its suitability for any
alpar@100
    15
 * purpose.
alpar@100
    16
 *
alpar@100
    17
 */
alpar@100
    18
kpeter@171
    19
#include <lemon/concepts/digraph.h>
kpeter@171
    20
#include <lemon/smart_graph.h>
alpar@100
    21
#include <lemon/list_graph.h>
deba@228
    22
#include <lemon/lgf_reader.h>
alpar@100
    23
#include <lemon/bfs.h>
alpar@100
    24
#include <lemon/path.h>
kpeter@171
    25
kpeter@171
    26
#include "graph_test.h"
kpeter@171
    27
#include "test_tools.h"
alpar@100
    28
alpar@100
    29
using namespace lemon;
alpar@100
    30
deba@228
    31
char test_lgf[] =
deba@228
    32
  "@nodes\n"
deba@228
    33
  "label\n"
deba@228
    34
  "0\n"
deba@228
    35
  "1\n"
deba@228
    36
  "2\n"
deba@228
    37
  "3\n"
deba@228
    38
  "4\n"
deba@228
    39
  "5\n"
deba@228
    40
  "@arcs\n"
deba@228
    41
  "     label\n"
deba@228
    42
  "0 1  0\n"
deba@228
    43
  "1 2  1\n"
deba@228
    44
  "2 3  2\n"
deba@228
    45
  "3 4  3\n"
deba@228
    46
  "0 3  4\n"
deba@228
    47
  "0 3  5\n"
deba@228
    48
  "5 2  6\n"
deba@228
    49
  "@attributes\n"
deba@228
    50
  "source 0\n"
deba@228
    51
  "target 4\n";
deba@228
    52
alpar@209
    53
void checkBfsCompile()
alpar@100
    54
{
alpar@100
    55
  typedef concepts::Digraph Digraph;
alpar@100
    56
  typedef Bfs<Digraph> BType;
kpeter@286
    57
  typedef Digraph::Node Node;
kpeter@286
    58
  typedef Digraph::Arc Arc;
alpar@209
    59
alpar@100
    60
  Digraph G;
kpeter@286
    61
  Node s, t;
kpeter@286
    62
  Arc e;
alpar@100
    63
  int l;
alpar@100
    64
  bool b;
alpar@100
    65
  BType::DistMap d(G);
alpar@100
    66
  BType::PredMap p(G);
kpeter@286
    67
  Path<Digraph> pp;
alpar@209
    68
kpeter@286
    69
  {
kpeter@286
    70
    BType bfs_test(G);
alpar@209
    71
kpeter@286
    72
    bfs_test.run(s);
kpeter@286
    73
    bfs_test.run(s,t);
kpeter@286
    74
    bfs_test.run();
alpar@209
    75
kpeter@286
    76
    l  = bfs_test.dist(t);
kpeter@286
    77
    e  = bfs_test.predArc(t);
kpeter@286
    78
    s  = bfs_test.predNode(t);
kpeter@286
    79
    b  = bfs_test.reached(t);
kpeter@286
    80
    d  = bfs_test.distMap();
kpeter@286
    81
    p  = bfs_test.predMap();
kpeter@286
    82
    pp = bfs_test.path(t);
kpeter@286
    83
  }
kpeter@286
    84
  {
kpeter@286
    85
    BType
kpeter@286
    86
      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
kpeter@286
    87
      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
kpeter@286
    88
      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
kpeter@286
    89
      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
kpeter@286
    90
      ::SetStandardProcessedMap
kpeter@286
    91
      ::Create bfs_test(G);
alpar@100
    92
kpeter@286
    93
    bfs_test.run(s);
kpeter@286
    94
    bfs_test.run(s,t);
kpeter@286
    95
    bfs_test.run();
kpeter@286
    96
kpeter@286
    97
    l  = bfs_test.dist(t);
kpeter@286
    98
    e  = bfs_test.predArc(t);
kpeter@286
    99
    s  = bfs_test.predNode(t);
kpeter@286
   100
    b  = bfs_test.reached(t);
kpeter@286
   101
    pp = bfs_test.path(t);
kpeter@286
   102
  }
alpar@100
   103
}
alpar@100
   104
alpar@209
   105
void checkBfsFunctionCompile()
alpar@100
   106
{
alpar@100
   107
  typedef int VType;
alpar@100
   108
  typedef concepts::Digraph Digraph;
alpar@100
   109
  typedef Digraph::Arc Arc;
alpar@100
   110
  typedef Digraph::Node Node;
alpar@209
   111
alpar@100
   112
  Digraph g;
kpeter@278
   113
  bool b;
kpeter@278
   114
  bfs(g).run(Node());
kpeter@278
   115
  b=bfs(g).run(Node(),Node());
kpeter@278
   116
  bfs(g).run();
alpar@100
   117
  bfs(g)
kpeter@278
   118
    .predMap(concepts::ReadWriteMap<Node,Arc>())
kpeter@278
   119
    .distMap(concepts::ReadWriteMap<Node,VType>())
alpar@100
   120
    .reachedMap(concepts::ReadWriteMap<Node,bool>())
alpar@100
   121
    .processedMap(concepts::WriteMap<Node,bool>())
alpar@100
   122
    .run(Node());
kpeter@278
   123
  b=bfs(g)
kpeter@278
   124
    .predMap(concepts::ReadWriteMap<Node,Arc>())
kpeter@278
   125
    .distMap(concepts::ReadWriteMap<Node,VType>())
kpeter@278
   126
    .reachedMap(concepts::ReadWriteMap<Node,bool>())
kpeter@278
   127
    .processedMap(concepts::WriteMap<Node,bool>())
kpeter@278
   128
    .path(concepts::Path<Digraph>())
kpeter@278
   129
    .dist(VType())
kpeter@278
   130
    .run(Node(),Node());
kpeter@278
   131
  bfs(g)
kpeter@278
   132
    .predMap(concepts::ReadWriteMap<Node,Arc>())
kpeter@278
   133
    .distMap(concepts::ReadWriteMap<Node,VType>())
kpeter@278
   134
    .reachedMap(concepts::ReadWriteMap<Node,bool>())
kpeter@278
   135
    .processedMap(concepts::WriteMap<Node,bool>())
kpeter@278
   136
    .run();
alpar@100
   137
}
alpar@100
   138
kpeter@171
   139
template <class Digraph>
kpeter@171
   140
void checkBfs() {
kpeter@171
   141
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@100
   142
alpar@100
   143
  Digraph G;
alpar@100
   144
  Node s, t;
alpar@209
   145
deba@228
   146
  std::istringstream input(test_lgf);
kpeter@293
   147
  digraphReader(G, input).
deba@228
   148
    node("source", s).
deba@228
   149
    node("target", t).
deba@228
   150
    run();
alpar@209
   151
alpar@100
   152
  Bfs<Digraph> bfs_test(G);
alpar@100
   153
  bfs_test.run(s);
alpar@209
   154
kpeter@278
   155
  check(bfs_test.dist(t)==2,"Bfs found a wrong path.");
alpar@100
   156
alpar@100
   157
  Path<Digraph> p = bfs_test.path(t);
deba@228
   158
  check(p.length()==2,"path() found a wrong path.");
alpar@100
   159
  check(checkPath(G, p),"path() found a wrong path.");
alpar@100
   160
  check(pathSource(G, p) == s,"path() found a wrong path.");
alpar@100
   161
  check(pathTarget(G, p) == t,"path() found a wrong path.");
alpar@209
   162
alpar@100
   163
deba@228
   164
  for(ArcIt a(G); a!=INVALID; ++a) {
deba@228
   165
    Node u=G.source(a);
deba@228
   166
    Node v=G.target(a);
alpar@100
   167
    check( !bfs_test.reached(u) ||
deba@222
   168
           (bfs_test.dist(v) <= bfs_test.dist(u)+1),
kpeter@278
   169
           "Wrong output. " << G.id(u) << "->" << G.id(v));
alpar@100
   170
  }
alpar@100
   171
deba@222
   172
  for(NodeIt v(G); v!=INVALID; ++v) {
deba@228
   173
    if (bfs_test.reached(v)) {
deba@228
   174
      check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
deba@228
   175
      if (bfs_test.predArc(v)!=INVALID ) {
deba@228
   176
        Arc a=bfs_test.predArc(v);
deba@228
   177
        Node u=G.source(a);
deba@228
   178
        check(u==bfs_test.predNode(v),"Wrong tree.");
deba@228
   179
        check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
deba@228
   180
              "Wrong distance. Difference: "
kpeter@278
   181
              << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1));
deba@228
   182
      }
alpar@100
   183
    }
alpar@100
   184
  }
kpeter@278
   185
kpeter@278
   186
  {
kpeter@278
   187
    NullMap<Node,Arc> myPredMap;
kpeter@278
   188
    bfs(G).predMap(myPredMap).run(s);
kpeter@278
   189
  }
alpar@100
   190
}
alpar@100
   191
kpeter@171
   192
int main()
kpeter@171
   193
{
kpeter@171
   194
  checkBfs<ListDigraph>();
kpeter@171
   195
  checkBfs<SmartDigraph>();
kpeter@171
   196
  return 0;
kpeter@171
   197
}