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