test/suurballe_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 09:54:14 +0200
changeset 593 7ac52d6a268e
parent 423 ff48c2738fb2
child 623 7c1324b35d89
permissions -rw-r--r--
Extend and modify the interface of matching algorithms (#265)

- Rename decomposition() to status() in MaxMatching.
- Add a new query function statusMap() to MaxMatching.
- Add a new query function matchingMap() to all the three classes.
- Rename matchingValue() to matchingWeight() in the weighted
matching classes.
     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 }