test/suurballe_test.cc
changeset 434 5c69a36729cb
parent 346 7f26c4b32651
child 440 88ed40ad0d4f
equal deleted inserted replaced
1:db3382f2579f 2:d359e06e7366
    15  * purpose.
    15  * purpose.
    16  *
    16  *
    17  */
    17  */
    18 
    18 
    19 #include <iostream>
    19 #include <iostream>
    20 #include <fstream>
       
    21 
    20 
    22 #include <lemon/list_graph.h>
    21 #include <lemon/list_graph.h>
    23 #include <lemon/lgf_reader.h>
    22 #include <lemon/lgf_reader.h>
    24 #include <lemon/path.h>
    23 #include <lemon/path.h>
    25 #include <lemon/suurballe.h>
    24 #include <lemon/suurballe.h>
    26 
    25 
    27 #include "test_tools.h"
    26 #include "test_tools.h"
    28 
    27 
    29 using namespace lemon;
    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";
    30 
    72 
    31 // Check the feasibility of the flow
    73 // Check the feasibility of the flow
    32 template <typename Digraph, typename FlowMap>
    74 template <typename Digraph, typename FlowMap>
    33 bool checkFlow( const Digraph& gr, const FlowMap& flow, 
    75 bool checkFlow( const Digraph& gr, const FlowMap& flow, 
    34                 typename Digraph::Node s, typename Digraph::Node t,
    76                 typename Digraph::Node s, typename Digraph::Node t,
    94   // Read the test digraph
   136   // Read the test digraph
    95   ListDigraph digraph;
   137   ListDigraph digraph;
    96   ListDigraph::ArcMap<int> length(digraph);
   138   ListDigraph::ArcMap<int> length(digraph);
    97   Node source, target;
   139   Node source, target;
    98 
   140 
    99   std::string fname;
   141   std::istringstream input(test_lgf);
   100   if(getenv("srcdir"))
       
   101     fname = std::string(getenv("srcdir"));
       
   102   else fname = ".";
       
   103   fname += "/test/min_cost_flow_test.lgf";
       
   104 
       
   105   std::ifstream input(fname.c_str());
       
   106   check(input, "Input file '" << fname << "' not found");
       
   107   DigraphReader<ListDigraph>(digraph, input).
   142   DigraphReader<ListDigraph>(digraph, input).
   108     arcMap("cost", length).
   143     arcMap("cost", length).
   109     node("source", source).
   144     node("source", source).
   110     node("target", target).
   145     node("target", target).
   111     run();
   146     run();
   112   input.close();
       
   113   
   147   
   114   // Find 2 paths
   148   // Find 2 paths
   115   {
   149   {
   116     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   150     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   117     check(suurballe.run(2) == 2, "Wrong number of paths");
   151     check(suurballe.run(2) == 2, "Wrong number of paths");