COIN-OR::LEMON - Graph Library

Changeset 670:7c1324b35d89 in lemon for test


Ignore:
Timestamp:
04/25/09 02:12:41 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Modify the interface of Suurballe (#266, #181)

  • Move the parameters s and t from the constructor to the run() function. It makes the interface capable for multiple run(s,t,k) calls (possible improvement in the future) and it is more similar to Dijkstra.
  • Simliarly init() and findFlow(k) were replaced by init(s) and findFlow(t,k). The separation of parameters s and t is for the future plans of supporting multiple targets with one source node. For more information see #181.
  • LEMON_ASSERT for the Length type (check if it is integer).
  • Doc improvements.
  • Rearrange query functions.
  • Extend test file.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/suurballe_test.cc

    r463 r670  
    2323#include <lemon/path.h>
    2424#include <lemon/suurballe.h>
     25#include <lemon/concepts/digraph.h>
    2526
    2627#include "test_tools.h"
     
    3031char test_lgf[] =
    3132  "@nodes\n"
    32   "label supply1 supply2 supply3\n"
    33   "1     0        20      27\n"
    34   "2     0       -4        0\n"
    35   "3     0        0        0\n"
    36   "4     0        0        0\n"
    37   "5     0        9        0\n"
    38   "6     0       -6        0\n"
    39   "7     0        0        0\n"
    40   "8     0        0        0\n"
    41   "9     0        3        0\n"
    42   "10    0       -2        0\n"
    43   "11    0        0        0\n"
    44   "12    0       -20     -27\n"
     33  "label\n"
     34  "1\n"
     35  "2\n"
     36  "3\n"
     37  "4\n"
     38  "5\n"
     39  "6\n"
     40  "7\n"
     41  "8\n"
     42  "9\n"
     43  "10\n"
     44  "11\n"
     45  "12\n"
    4546  "@arcs\n"
    46   "      cost capacity lower1 lower2\n"
    47   " 1  2  70  11       0      8\n"
    48   " 1  3 150   3       0      1\n"
    49   " 1  4  80  15       0      2\n"
    50   " 2  8  80  12       0      0\n"
    51   " 3  5 140   5       0      3\n"
    52   " 4  6  60  10       0      1\n"
    53   " 4  7  80   2       0      0\n"
    54   " 4  8 110   3       0      0\n"
    55   " 5  7  60  14       0      0\n"
    56   " 5 11 120  12       0      0\n"
    57   " 6  3   0   3       0      0\n"
    58   " 6  9 140   4       0      0\n"
    59   " 6 10  90   8       0      0\n"
    60   " 7  1  30   5       0      0\n"
    61   " 8 12  60  16       0      4\n"
    62   " 9 12  50   6       0      0\n"
    63   "10 12  70  13       0      5\n"
    64   "10  2 100   7       0      0\n"
    65   "10  7  60  10       0      0\n"
    66   "11 10  20  14       0      6\n"
    67   "12 11  30  10       0      0\n"
     47  "      length\n"
     48  " 1  2  70\n"
     49  " 1  3 150\n"
     50  " 1  4  80\n"
     51  " 2  8  80\n"
     52  " 3  5 140\n"
     53  " 4  6  60\n"
     54  " 4  7  80\n"
     55  " 4  8 110\n"
     56  " 5  7  60\n"
     57  " 5 11 120\n"
     58  " 6  3   0\n"
     59  " 6  9 140\n"
     60  " 6 10  90\n"
     61  " 7  1  30\n"
     62  " 8 12  60\n"
     63  " 9 12  50\n"
     64  "10 12  70\n"
     65  "10  2 100\n"
     66  "10  7  60\n"
     67  "11 10  20\n"
     68  "12 11  30\n"
    6869  "@attributes\n"
    6970  "source  1\n"
    7071  "target 12\n"
    7172  "@end\n";
     73
     74// Check the interface of Suurballe
     75void checkSuurballeCompile()
     76{
     77  typedef int VType;
     78  typedef concepts::Digraph Digraph;
     79
     80  typedef Digraph::Node Node;
     81  typedef Digraph::Arc Arc;
     82  typedef concepts::ReadMap<Arc, VType> LengthMap;
     83 
     84  typedef Suurballe<Digraph, LengthMap> SuurballeType;
     85
     86  Digraph g;
     87  Node n;
     88  Arc e;
     89  LengthMap len;
     90  SuurballeType::FlowMap flow(g);
     91  SuurballeType::PotentialMap pi(g);
     92
     93  SuurballeType suurb_test(g, len);
     94  const SuurballeType& const_suurb_test = suurb_test;
     95
     96  suurb_test
     97    .flowMap(flow)
     98    .potentialMap(pi);
     99
     100  int k;
     101  k = suurb_test.run(n, n);
     102  k = suurb_test.run(n, n, k);
     103  suurb_test.init(n);
     104  k = suurb_test.findFlow(n);
     105  k = suurb_test.findFlow(n, k);
     106  suurb_test.findPaths();
     107 
     108  int f;
     109  VType c;
     110  c = const_suurb_test.totalLength();
     111  f = const_suurb_test.flow(e);
     112  const SuurballeType::FlowMap& fm =
     113    const_suurb_test.flowMap();
     114  c = const_suurb_test.potential(n);
     115  const SuurballeType::PotentialMap& pm =
     116    const_suurb_test.potentialMap();
     117  k = const_suurb_test.pathNum();
     118  Path<Digraph> p = const_suurb_test.path(k);
     119 
     120  ignore_unused_variable_warning(fm);
     121  ignore_unused_variable_warning(pm);
     122}
    72123
    73124// Check the feasibility of the flow
     
    119170                typename Digraph::Node s, typename Digraph::Node t)
    120171{
    121   // Check the "Complementary Slackness" optimality condition
    122172  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    123173  Node n = s;
     
    137187  ListDigraph digraph;
    138188  ListDigraph::ArcMap<int> length(digraph);
    139   Node source, target;
     189  Node s, t;
    140190
    141191  std::istringstream input(test_lgf);
    142192  DigraphReader<ListDigraph>(digraph, input).
    143     arcMap("cost", length).
    144     node("source", source).
    145     node("target", target).
     193    arcMap("length", length).
     194    node("source", s).
     195    node("target", t).
    146196    run();
    147197
    148198  // Find 2 paths
    149199  {
    150     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
    151     check(suurballe.run(2) == 2, "Wrong number of paths");
    152     check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
     200    Suurballe<ListDigraph> suurballe(digraph, length);
     201    check(suurballe.run(s, t) == 2, "Wrong number of paths");
     202    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
    153203          "The flow is not feasible");
    154204    check(suurballe.totalLength() == 510, "The flow is not optimal");
     
    157207          "Wrong potentials");
    158208    for (int i = 0; i < suurballe.pathNum(); ++i)
    159       check(checkPath(digraph, suurballe.path(i), source, target),
    160             "Wrong path");
     209      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    161210  }
    162211
    163212  // Find 3 paths
    164213  {
    165     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
    166     check(suurballe.run(3) == 3, "Wrong number of paths");
    167     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
     214    Suurballe<ListDigraph> suurballe(digraph, length);
     215    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
     216    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
    168217          "The flow is not feasible");
    169218    check(suurballe.totalLength() == 1040, "The flow is not optimal");
     
    172221          "Wrong potentials");
    173222    for (int i = 0; i < suurballe.pathNum(); ++i)
    174       check(checkPath(digraph, suurballe.path(i), source, target),
    175             "Wrong path");
     223      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    176224  }
    177225
    178226  // Find 5 paths (only 3 can be found)
    179227  {
    180     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
    181     check(suurballe.run(5) == 3, "Wrong number of paths");
    182     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
     228    Suurballe<ListDigraph> suurballe(digraph, length);
     229    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
     230    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
    183231          "The flow is not feasible");
    184232    check(suurballe.totalLength() == 1040, "The flow is not optimal");
     
    187235          "Wrong potentials");
    188236    for (int i = 0; i < suurballe.pathNum(); ++i)
    189       check(checkPath(digraph, suurballe.path(i), source, target),
    190             "Wrong path");
     237      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    191238  }
    192239
Note: See TracChangeset for help on using the changeset viewer.