test/dfs_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 14 Mar 2010 09:14:05 +0100
changeset 866 2d9c6566a604
parent 440 88ed40ad0d4f
child 877 141f9c0db4a3
child 937 17e36e175725
permissions -rw-r--r--
Add doc/references.dox to .hgignore
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/dfs.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
  "6\n"
deba@228
    41
  "@arcs\n"
deba@228
    42
  "     label\n"
deba@228
    43
  "0 1  0\n"
deba@228
    44
  "1 2  1\n"
deba@228
    45
  "2 3  2\n"
deba@228
    46
  "1 4  3\n"
deba@228
    47
  "4 2  4\n"
deba@228
    48
  "4 5  5\n"
deba@228
    49
  "5 0  6\n"
deba@228
    50
  "6 3  7\n"
deba@228
    51
  "@attributes\n"
deba@228
    52
  "source 0\n"
deba@228
    53
  "target 5\n";
deba@228
    54
alpar@209
    55
void checkDfsCompile()
alpar@100
    56
{
alpar@100
    57
  typedef concepts::Digraph Digraph;
alpar@100
    58
  typedef Dfs<Digraph> DType;
kpeter@286
    59
  typedef Digraph::Node Node;
kpeter@286
    60
  typedef Digraph::Arc Arc;
alpar@209
    61
alpar@100
    62
  Digraph G;
kpeter@286
    63
  Node s, t;
kpeter@286
    64
  Arc e;
kpeter@585
    65
  int l, i;
alpar@100
    66
  bool b;
alpar@100
    67
  DType::DistMap d(G);
alpar@100
    68
  DType::PredMap p(G);
kpeter@286
    69
  Path<Digraph> pp;
kpeter@585
    70
  concepts::ReadMap<Arc,bool> am;
alpar@209
    71
kpeter@286
    72
  {
kpeter@286
    73
    DType dfs_test(G);
kpeter@585
    74
    const DType& const_dfs_test = dfs_test;
alpar@209
    75
kpeter@286
    76
    dfs_test.run(s);
kpeter@286
    77
    dfs_test.run(s,t);
kpeter@286
    78
    dfs_test.run();
alpar@209
    79
kpeter@585
    80
    dfs_test.init();
kpeter@585
    81
    dfs_test.addSource(s);
kpeter@585
    82
    e = dfs_test.processNextArc();
kpeter@585
    83
    e = const_dfs_test.nextArc();
kpeter@585
    84
    b = const_dfs_test.emptyQueue();
kpeter@585
    85
    i = const_dfs_test.queueSize();
kpeter@585
    86
    
kpeter@585
    87
    dfs_test.start();
kpeter@585
    88
    dfs_test.start(t);
kpeter@585
    89
    dfs_test.start(am);
kpeter@585
    90
kpeter@585
    91
    l  = const_dfs_test.dist(t);
kpeter@585
    92
    e  = const_dfs_test.predArc(t);
kpeter@585
    93
    s  = const_dfs_test.predNode(t);
kpeter@585
    94
    b  = const_dfs_test.reached(t);
kpeter@585
    95
    d  = const_dfs_test.distMap();
kpeter@585
    96
    p  = const_dfs_test.predMap();
kpeter@585
    97
    pp = const_dfs_test.path(t);
kpeter@286
    98
  }
kpeter@286
    99
  {
kpeter@286
   100
    DType
kpeter@286
   101
      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
kpeter@286
   102
      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
kpeter@286
   103
      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
kpeter@585
   104
      ::SetStandardProcessedMap
kpeter@286
   105
      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
kpeter@286
   106
      ::Create dfs_test(G);
alpar@100
   107
kpeter@585
   108
    concepts::ReadWriteMap<Node,Arc> pred_map;
kpeter@585
   109
    concepts::ReadWriteMap<Node,int> dist_map;
kpeter@585
   110
    concepts::ReadWriteMap<Node,bool> reached_map;
kpeter@585
   111
    concepts::WriteMap<Node,bool> processed_map;
kpeter@585
   112
    
kpeter@585
   113
    dfs_test
kpeter@585
   114
      .predMap(pred_map)
kpeter@585
   115
      .distMap(dist_map)
kpeter@585
   116
      .reachedMap(reached_map)
kpeter@585
   117
      .processedMap(processed_map);
kpeter@585
   118
kpeter@286
   119
    dfs_test.run(s);
kpeter@286
   120
    dfs_test.run(s,t);
kpeter@286
   121
    dfs_test.run();
kpeter@585
   122
    dfs_test.init();
kpeter@585
   123
kpeter@585
   124
    dfs_test.addSource(s);
kpeter@585
   125
    e = dfs_test.processNextArc();
kpeter@585
   126
    e = dfs_test.nextArc();
kpeter@585
   127
    b = dfs_test.emptyQueue();
kpeter@585
   128
    i = dfs_test.queueSize();
kpeter@585
   129
    
kpeter@585
   130
    dfs_test.start();
kpeter@585
   131
    dfs_test.start(t);
kpeter@585
   132
    dfs_test.start(am);
kpeter@286
   133
kpeter@286
   134
    l  = dfs_test.dist(t);
kpeter@286
   135
    e  = dfs_test.predArc(t);
kpeter@286
   136
    s  = dfs_test.predNode(t);
kpeter@286
   137
    b  = dfs_test.reached(t);
kpeter@286
   138
    pp = dfs_test.path(t);
kpeter@286
   139
  }
alpar@100
   140
}
alpar@100
   141
alpar@209
   142
void checkDfsFunctionCompile()
alpar@100
   143
{
alpar@100
   144
  typedef int VType;
alpar@100
   145
  typedef concepts::Digraph Digraph;
alpar@100
   146
  typedef Digraph::Arc Arc;
alpar@100
   147
  typedef Digraph::Node Node;
alpar@209
   148
alpar@100
   149
  Digraph g;
kpeter@278
   150
  bool b;
kpeter@278
   151
  dfs(g).run(Node());
kpeter@278
   152
  b=dfs(g).run(Node(),Node());
kpeter@278
   153
  dfs(g).run();
alpar@100
   154
  dfs(g)
kpeter@278
   155
    .predMap(concepts::ReadWriteMap<Node,Arc>())
kpeter@278
   156
    .distMap(concepts::ReadWriteMap<Node,VType>())
alpar@100
   157
    .reachedMap(concepts::ReadWriteMap<Node,bool>())
alpar@100
   158
    .processedMap(concepts::WriteMap<Node,bool>())
alpar@209
   159
    .run(Node());
kpeter@278
   160
  b=dfs(g)
kpeter@278
   161
    .predMap(concepts::ReadWriteMap<Node,Arc>())
kpeter@278
   162
    .distMap(concepts::ReadWriteMap<Node,VType>())
kpeter@278
   163
    .reachedMap(concepts::ReadWriteMap<Node,bool>())
kpeter@278
   164
    .processedMap(concepts::WriteMap<Node,bool>())
kpeter@278
   165
    .path(concepts::Path<Digraph>())
kpeter@278
   166
    .dist(VType())
kpeter@278
   167
    .run(Node(),Node());
kpeter@278
   168
  dfs(g)
kpeter@278
   169
    .predMap(concepts::ReadWriteMap<Node,Arc>())
kpeter@278
   170
    .distMap(concepts::ReadWriteMap<Node,VType>())
kpeter@278
   171
    .reachedMap(concepts::ReadWriteMap<Node,bool>())
kpeter@278
   172
    .processedMap(concepts::WriteMap<Node,bool>())
kpeter@278
   173
    .run();
alpar@100
   174
}
alpar@100
   175
kpeter@171
   176
template <class Digraph>
kpeter@171
   177
void checkDfs() {
kpeter@171
   178
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@100
   179
alpar@100
   180
  Digraph G;
alpar@100
   181
  Node s, t;
alpar@209
   182
deba@228
   183
  std::istringstream input(test_lgf);
kpeter@293
   184
  digraphReader(G, input).
deba@228
   185
    node("source", s).
deba@228
   186
    node("target", t).
deba@228
   187
    run();
alpar@209
   188
alpar@100
   189
  Dfs<Digraph> dfs_test(G);
alpar@209
   190
  dfs_test.run(s);
alpar@209
   191
alpar@100
   192
  Path<Digraph> p = dfs_test.path(t);
kpeter@171
   193
  check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
alpar@100
   194
  check(checkPath(G, p),"path() found a wrong path.");
alpar@100
   195
  check(pathSource(G, p) == s,"path() found a wrong path.");
alpar@100
   196
  check(pathTarget(G, p) == t,"path() found a wrong path.");
alpar@209
   197
alpar@100
   198
  for(NodeIt v(G); v!=INVALID; ++v) {
deba@228
   199
    if (dfs_test.reached(v)) {
deba@228
   200
      check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
deba@228
   201
      if (dfs_test.predArc(v)!=INVALID ) {
deba@228
   202
        Arc e=dfs_test.predArc(v);
deba@228
   203
        Node u=G.source(e);
deba@228
   204
        check(u==dfs_test.predNode(v),"Wrong tree.");
deba@228
   205
        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
deba@228
   206
              "Wrong distance. (" << dfs_test.dist(u) << "->"
kpeter@278
   207
              << dfs_test.dist(v) << ")");
deba@228
   208
      }
alpar@100
   209
    }
alpar@100
   210
  }
kpeter@278
   211
kpeter@278
   212
  {
kpeter@278
   213
    NullMap<Node,Arc> myPredMap;
kpeter@278
   214
    dfs(G).predMap(myPredMap).run(s);
kpeter@278
   215
  }
alpar@100
   216
}
alpar@100
   217
kpeter@171
   218
int main()
kpeter@171
   219
{
kpeter@171
   220
  checkDfs<ListDigraph>();
kpeter@171
   221
  checkDfs<SmartDigraph>();
kpeter@171
   222
  return 0;
kpeter@171
   223
}