test/dfs_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 293 47fbc814aa31
child 585 65fbcf2f978a
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; -*-
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;
alpar@100
    65
  int l;
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;
alpar@209
    70
kpeter@286
    71
  {
kpeter@286
    72
    DType dfs_test(G);
alpar@209
    73
kpeter@286
    74
    dfs_test.run(s);
kpeter@286
    75
    dfs_test.run(s,t);
kpeter@286
    76
    dfs_test.run();
alpar@209
    77
kpeter@286
    78
    l  = dfs_test.dist(t);
kpeter@286
    79
    e  = dfs_test.predArc(t);
kpeter@286
    80
    s  = dfs_test.predNode(t);
kpeter@286
    81
    b  = dfs_test.reached(t);
kpeter@286
    82
    d  = dfs_test.distMap();
kpeter@286
    83
    p  = dfs_test.predMap();
kpeter@286
    84
    pp = dfs_test.path(t);
kpeter@286
    85
  }
kpeter@286
    86
  {
kpeter@286
    87
    DType
kpeter@286
    88
      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
kpeter@286
    89
      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
kpeter@286
    90
      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
kpeter@286
    91
      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
kpeter@286
    92
      ::SetStandardProcessedMap
kpeter@286
    93
      ::Create dfs_test(G);
alpar@100
    94
kpeter@286
    95
    dfs_test.run(s);
kpeter@286
    96
    dfs_test.run(s,t);
kpeter@286
    97
    dfs_test.run();
kpeter@286
    98
kpeter@286
    99
    l  = dfs_test.dist(t);
kpeter@286
   100
    e  = dfs_test.predArc(t);
kpeter@286
   101
    s  = dfs_test.predNode(t);
kpeter@286
   102
    b  = dfs_test.reached(t);
kpeter@286
   103
    pp = dfs_test.path(t);
kpeter@286
   104
  }
alpar@100
   105
}
alpar@100
   106
alpar@209
   107
void checkDfsFunctionCompile()
alpar@100
   108
{
alpar@100
   109
  typedef int VType;
alpar@100
   110
  typedef concepts::Digraph Digraph;
alpar@100
   111
  typedef Digraph::Arc Arc;
alpar@100
   112
  typedef Digraph::Node Node;
alpar@209
   113
alpar@100
   114
  Digraph g;
kpeter@278
   115
  bool b;
kpeter@278
   116
  dfs(g).run(Node());
kpeter@278
   117
  b=dfs(g).run(Node(),Node());
kpeter@278
   118
  dfs(g).run();
alpar@100
   119
  dfs(g)
kpeter@278
   120
    .predMap(concepts::ReadWriteMap<Node,Arc>())
kpeter@278
   121
    .distMap(concepts::ReadWriteMap<Node,VType>())
alpar@100
   122
    .reachedMap(concepts::ReadWriteMap<Node,bool>())
alpar@100
   123
    .processedMap(concepts::WriteMap<Node,bool>())
alpar@209
   124
    .run(Node());
kpeter@278
   125
  b=dfs(g)
kpeter@278
   126
    .predMap(concepts::ReadWriteMap<Node,Arc>())
kpeter@278
   127
    .distMap(concepts::ReadWriteMap<Node,VType>())
kpeter@278
   128
    .reachedMap(concepts::ReadWriteMap<Node,bool>())
kpeter@278
   129
    .processedMap(concepts::WriteMap<Node,bool>())
kpeter@278
   130
    .path(concepts::Path<Digraph>())
kpeter@278
   131
    .dist(VType())
kpeter@278
   132
    .run(Node(),Node());
kpeter@278
   133
  dfs(g)
kpeter@278
   134
    .predMap(concepts::ReadWriteMap<Node,Arc>())
kpeter@278
   135
    .distMap(concepts::ReadWriteMap<Node,VType>())
kpeter@278
   136
    .reachedMap(concepts::ReadWriteMap<Node,bool>())
kpeter@278
   137
    .processedMap(concepts::WriteMap<Node,bool>())
kpeter@278
   138
    .run();
alpar@100
   139
}
alpar@100
   140
kpeter@171
   141
template <class Digraph>
kpeter@171
   142
void checkDfs() {
kpeter@171
   143
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@100
   144
alpar@100
   145
  Digraph G;
alpar@100
   146
  Node s, t;
alpar@209
   147
deba@228
   148
  std::istringstream input(test_lgf);
kpeter@293
   149
  digraphReader(G, input).
deba@228
   150
    node("source", s).
deba@228
   151
    node("target", t).
deba@228
   152
    run();
alpar@209
   153
alpar@100
   154
  Dfs<Digraph> dfs_test(G);
alpar@209
   155
  dfs_test.run(s);
alpar@209
   156
alpar@100
   157
  Path<Digraph> p = dfs_test.path(t);
kpeter@171
   158
  check(p.length() == dfs_test.dist(t),"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
  for(NodeIt v(G); v!=INVALID; ++v) {
deba@228
   164
    if (dfs_test.reached(v)) {
deba@228
   165
      check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
deba@228
   166
      if (dfs_test.predArc(v)!=INVALID ) {
deba@228
   167
        Arc e=dfs_test.predArc(v);
deba@228
   168
        Node u=G.source(e);
deba@228
   169
        check(u==dfs_test.predNode(v),"Wrong tree.");
deba@228
   170
        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
deba@228
   171
              "Wrong distance. (" << dfs_test.dist(u) << "->"
kpeter@278
   172
              << dfs_test.dist(v) << ")");
deba@228
   173
      }
alpar@100
   174
    }
alpar@100
   175
  }
kpeter@278
   176
kpeter@278
   177
  {
kpeter@278
   178
    NullMap<Node,Arc> myPredMap;
kpeter@278
   179
    dfs(G).predMap(myPredMap).run(s);
kpeter@278
   180
  }
alpar@100
   181
}
alpar@100
   182
kpeter@171
   183
int main()
kpeter@171
   184
{
kpeter@171
   185
  checkDfs<ListDigraph>();
kpeter@171
   186
  checkDfs<SmartDigraph>();
kpeter@171
   187
  return 0;
kpeter@171
   188
}