test/suurballe_test.cc
author kpeter
Sun, 05 Oct 2008 13:36:43 +0000
changeset 2619 30fb4d68b0e8
parent 2553 bfced05fa852
permissions -rw-r--r--
Improve network simplex algorithm

- Remove "Limited Search" and "Combined" pivot rules.
- Add a new pivot rule "Altering Candidate List".
- Make the edge selection faster in every pivot rule.
- Set the default rule to "Block Search".
- Doc improvements.

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