test/suurballe_test.cc
author Balazs Dezso <deba@inf.elte.hu>
Tue, 02 Dec 2008 23:33:47 +0100
changeset 490 7f8560cb9d65
parent 345 2f64c4a692a8
child 423 ff48c2738fb2
permissions -rw-r--r--
Port MinCostArborescence algorithm from SVN #3509
alpar@345
     1
/* -*- C++ -*-
alpar@345
     2
 *
alpar@345
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@345
     4
 *
alpar@345
     5
 * Copyright (C) 2003-2008
alpar@345
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@345
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@345
     8
 *
alpar@345
     9
 * Permission to use, modify and distribute this software is granted
alpar@345
    10
 * provided that this copyright notice appears in all copies. For
alpar@345
    11
 * precise terms see the accompanying LICENSE file.
alpar@345
    12
 *
alpar@345
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@345
    14
 * express or implied, and with no claim as to its suitability for any
alpar@345
    15
 * purpose.
alpar@345
    16
 *
alpar@345
    17
 */
alpar@345
    18
alpar@345
    19
#include <iostream>
alpar@345
    20
#include <fstream>
alpar@345
    21
alpar@345
    22
#include <lemon/list_graph.h>
alpar@345
    23
#include <lemon/lgf_reader.h>
alpar@345
    24
#include <lemon/path.h>
alpar@345
    25
#include <lemon/suurballe.h>
alpar@345
    26
alpar@345
    27
#include "test_tools.h"
alpar@345
    28
alpar@345
    29
using namespace lemon;
alpar@345
    30
kpeter@346
    31
// Check the feasibility of the flow
alpar@345
    32
template <typename Digraph, typename FlowMap>
alpar@345
    33
bool checkFlow( const Digraph& gr, const FlowMap& flow, 
alpar@345
    34
                typename Digraph::Node s, typename Digraph::Node t,
alpar@345
    35
                int value )
alpar@345
    36
{
alpar@345
    37
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@345
    38
  for (ArcIt e(gr); e != INVALID; ++e)
alpar@345
    39
    if (!(flow[e] == 0 || flow[e] == 1)) return false;
alpar@345
    40
alpar@345
    41
  for (NodeIt n(gr); n != INVALID; ++n) {
alpar@345
    42
    int sum = 0;
alpar@345
    43
    for (OutArcIt e(gr, n); e != INVALID; ++e)
alpar@345
    44
      sum += flow[e];
alpar@345
    45
    for (InArcIt e(gr, n); e != INVALID; ++e)
alpar@345
    46
      sum -= flow[e];
alpar@345
    47
    if (n == s && sum != value) return false;
alpar@345
    48
    if (n == t && sum != -value) return false;
alpar@345
    49
    if (n != s && n != t && sum != 0) return false;
alpar@345
    50
  }
alpar@345
    51
alpar@345
    52
  return true;
alpar@345
    53
}
alpar@345
    54
kpeter@346
    55
// Check the optimalitiy of the flow
alpar@345
    56
template < typename Digraph, typename CostMap, 
alpar@345
    57
           typename FlowMap, typename PotentialMap >
alpar@345
    58
bool checkOptimality( const Digraph& gr, const CostMap& cost,
alpar@345
    59
                      const FlowMap& flow, const PotentialMap& pi )
alpar@345
    60
{
kpeter@346
    61
  // Check the "Complementary Slackness" optimality condition
alpar@345
    62
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@345
    63
  bool opt = true;
alpar@345
    64
  for (ArcIt e(gr); e != INVALID; ++e) {
alpar@345
    65
    typename CostMap::Value red_cost =
alpar@345
    66
      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
alpar@345
    67
    opt = (flow[e] == 0 && red_cost >= 0) ||
alpar@345
    68
          (flow[e] == 1 && red_cost <= 0);
alpar@345
    69
    if (!opt) break;
alpar@345
    70
  }
alpar@345
    71
  return opt;
alpar@345
    72
}
alpar@345
    73
kpeter@346
    74
// Check a path
kpeter@346
    75
template <typename Digraph, typename Path>
alpar@345
    76
bool checkPath( const Digraph& gr, const Path& path,
alpar@345
    77
                typename Digraph::Node s, typename Digraph::Node t)
alpar@345
    78
{
kpeter@346
    79
  // Check the "Complementary Slackness" optimality condition
alpar@345
    80
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@345
    81
  Node n = s;
alpar@345
    82
  for (int i = 0; i < path.length(); ++i) {
alpar@345
    83
    if (gr.source(path.nth(i)) != n) return false;
alpar@345
    84
    n = gr.target(path.nth(i));
alpar@345
    85
  }
alpar@345
    86
  return n == t;
alpar@345
    87
}
alpar@345
    88
alpar@345
    89
alpar@345
    90
int main()
alpar@345
    91
{
alpar@345
    92
  DIGRAPH_TYPEDEFS(ListDigraph);
alpar@345
    93
kpeter@346
    94
  // Read the test digraph
alpar@345
    95
  ListDigraph digraph;
alpar@345
    96
  ListDigraph::ArcMap<int> length(digraph);
alpar@345
    97
  Node source, target;
alpar@345
    98
alpar@345
    99
  std::string fname;
alpar@345
   100
  if(getenv("srcdir"))
alpar@345
   101
    fname = std::string(getenv("srcdir"));
alpar@345
   102
  else fname = ".";
alpar@345
   103
  fname += "/test/min_cost_flow_test.lgf";
alpar@345
   104
alpar@345
   105
  std::ifstream input(fname.c_str());
alpar@345
   106
  check(input, "Input file '" << fname << "' not found");
alpar@345
   107
  DigraphReader<ListDigraph>(digraph, input).
alpar@345
   108
    arcMap("cost", length).
alpar@345
   109
    node("source", source).
alpar@345
   110
    node("target", target).
alpar@345
   111
    run();
alpar@345
   112
  input.close();
alpar@345
   113
  
kpeter@346
   114
  // Find 2 paths
alpar@345
   115
  {
alpar@345
   116
    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
alpar@345
   117
    check(suurballe.run(2) == 2, "Wrong number of paths");
alpar@345
   118
    check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
alpar@345
   119
          "The flow is not feasible");
alpar@345
   120
    check(suurballe.totalLength() == 510, "The flow is not optimal");
alpar@345
   121
    check(checkOptimality(digraph, length, suurballe.flowMap(), 
alpar@345
   122
                          suurballe.potentialMap()),
alpar@345
   123
          "Wrong potentials");
alpar@345
   124
    for (int i = 0; i < suurballe.pathNum(); ++i)
alpar@345
   125
      check(checkPath(digraph, suurballe.path(i), source, target),
alpar@345
   126
            "Wrong path");
alpar@345
   127
  }
alpar@345
   128
kpeter@346
   129
  // Find 3 paths
alpar@345
   130
  {
alpar@345
   131
    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
alpar@345
   132
    check(suurballe.run(3) == 3, "Wrong number of paths");
alpar@345
   133
    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
alpar@345
   134
          "The flow is not feasible");
alpar@345
   135
    check(suurballe.totalLength() == 1040, "The flow is not optimal");
alpar@345
   136
    check(checkOptimality(digraph, length, suurballe.flowMap(), 
alpar@345
   137
                          suurballe.potentialMap()),
alpar@345
   138
          "Wrong potentials");
alpar@345
   139
    for (int i = 0; i < suurballe.pathNum(); ++i)
alpar@345
   140
      check(checkPath(digraph, suurballe.path(i), source, target),
alpar@345
   141
            "Wrong path");
alpar@345
   142
  }
alpar@345
   143
kpeter@346
   144
  // Find 5 paths (only 3 can be found)
alpar@345
   145
  {
alpar@345
   146
    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
alpar@345
   147
    check(suurballe.run(5) == 3, "Wrong number of paths");
alpar@345
   148
    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
alpar@345
   149
          "The flow is not feasible");
alpar@345
   150
    check(suurballe.totalLength() == 1040, "The flow is not optimal");
alpar@345
   151
    check(checkOptimality(digraph, length, suurballe.flowMap(), 
alpar@345
   152
                          suurballe.potentialMap()),
alpar@345
   153
          "Wrong potentials");
alpar@345
   154
    for (int i = 0; i < suurballe.pathNum(); ++i)
alpar@345
   155
      check(checkPath(digraph, suurballe.path(i), source, target),
alpar@345
   156
            "Wrong path");
alpar@345
   157
  }
alpar@345
   158
alpar@345
   159
  return 0;
alpar@345
   160
}