test/suurballe_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 423 ff48c2738fb2
child 623 7c1324b35d89
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.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <iostream>
    20 
    21 #include <lemon/list_graph.h>
    22 #include <lemon/lgf_reader.h>
    23 #include <lemon/path.h>
    24 #include <lemon/suurballe.h>
    25 
    26 #include "test_tools.h"
    27 
    28 using namespace lemon;
    29 
    30 char test_lgf[] =
    31   "@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"
    45   "@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"
    68   "@attributes\n"
    69   "source  1\n"
    70   "target 12\n"
    71   "@end\n";
    72 
    73 // Check the feasibility of the flow
    74 template <typename Digraph, typename FlowMap>
    75 bool checkFlow( const Digraph& gr, const FlowMap& flow,
    76                 typename Digraph::Node s, typename Digraph::Node t,
    77                 int value )
    78 {
    79   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    80   for (ArcIt e(gr); e != INVALID; ++e)
    81     if (!(flow[e] == 0 || flow[e] == 1)) return false;
    82 
    83   for (NodeIt n(gr); n != INVALID; ++n) {
    84     int sum = 0;
    85     for (OutArcIt e(gr, n); e != INVALID; ++e)
    86       sum += flow[e];
    87     for (InArcIt e(gr, n); e != INVALID; ++e)
    88       sum -= flow[e];
    89     if (n == s && sum != value) return false;
    90     if (n == t && sum != -value) return false;
    91     if (n != s && n != t && sum != 0) return false;
    92   }
    93 
    94   return true;
    95 }
    96 
    97 // Check the optimalitiy of the flow
    98 template < typename Digraph, typename CostMap,
    99            typename FlowMap, typename PotentialMap >
   100 bool checkOptimality( const Digraph& gr, const CostMap& cost,
   101                       const FlowMap& flow, const PotentialMap& pi )
   102 {
   103   // Check the "Complementary Slackness" optimality condition
   104   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   105   bool opt = true;
   106   for (ArcIt e(gr); e != INVALID; ++e) {
   107     typename CostMap::Value red_cost =
   108       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
   109     opt = (flow[e] == 0 && red_cost >= 0) ||
   110           (flow[e] == 1 && red_cost <= 0);
   111     if (!opt) break;
   112   }
   113   return opt;
   114 }
   115 
   116 // Check a path
   117 template <typename Digraph, typename Path>
   118 bool checkPath( const Digraph& gr, const Path& path,
   119                 typename Digraph::Node s, typename Digraph::Node t)
   120 {
   121   // Check the "Complementary Slackness" optimality condition
   122   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   123   Node n = s;
   124   for (int i = 0; i < path.length(); ++i) {
   125     if (gr.source(path.nth(i)) != n) return false;
   126     n = gr.target(path.nth(i));
   127   }
   128   return n == t;
   129 }
   130 
   131 
   132 int main()
   133 {
   134   DIGRAPH_TYPEDEFS(ListDigraph);
   135 
   136   // Read the test digraph
   137   ListDigraph digraph;
   138   ListDigraph::ArcMap<int> length(digraph);
   139   Node source, target;
   140 
   141   std::istringstream input(test_lgf);
   142   DigraphReader<ListDigraph>(digraph, input).
   143     arcMap("cost", length).
   144     node("source", source).
   145     node("target", target).
   146     run();
   147 
   148   // Find 2 paths
   149   {
   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),
   153           "The flow is not feasible");
   154     check(suurballe.totalLength() == 510, "The flow is not optimal");
   155     check(checkOptimality(digraph, length, suurballe.flowMap(),
   156                           suurballe.potentialMap()),
   157           "Wrong potentials");
   158     for (int i = 0; i < suurballe.pathNum(); ++i)
   159       check(checkPath(digraph, suurballe.path(i), source, target),
   160             "Wrong path");
   161   }
   162 
   163   // Find 3 paths
   164   {
   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),
   168           "The flow is not feasible");
   169     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   170     check(checkOptimality(digraph, length, suurballe.flowMap(),
   171                           suurballe.potentialMap()),
   172           "Wrong potentials");
   173     for (int i = 0; i < suurballe.pathNum(); ++i)
   174       check(checkPath(digraph, suurballe.path(i), source, target),
   175             "Wrong path");
   176   }
   177 
   178   // Find 5 paths (only 3 can be found)
   179   {
   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),
   183           "The flow is not feasible");
   184     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   185     check(checkOptimality(digraph, length, suurballe.flowMap(),
   186                           suurballe.potentialMap()),
   187           "Wrong potentials");
   188     for (int i = 0; i < suurballe.pathNum(); ++i)
   189       check(checkPath(digraph, suurballe.path(i), source, target),
   190             "Wrong path");
   191   }
   192 
   193   return 0;
   194 }