test/suurballe_test.cc
author kpeter
Mon, 18 Feb 2008 03:34:16 +0000
changeset 2577 2c6204d4b0f6
parent 2391 14a343be7a5a
child 2586 37fb2c384c78
permissions -rw-r--r--
Add a cost scaling min cost flow algorithm.

Add a cost scaling algorithm, which is performing generalized
push-relabel operations. It is almost as efficient as the capacity
scaling algorithm, but slower than network simplex.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     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 #include <lemon/list_graph.h>
    21 #include <lemon/suurballe.h>
    22 //#include <path.h>
    23 #include "test_tools.h"
    24 
    25 using namespace lemon;
    26 
    27 
    28 bool passed = true;
    29 
    30 
    31 int main()
    32 {
    33   typedef ListGraph Graph;
    34   typedef Graph::Node Node;
    35   typedef Graph::Edge Edge;
    36 
    37   Graph graph;
    38 
    39   //Ahuja könyv példája
    40 
    41   Node s=graph.addNode();
    42   Node v1=graph.addNode();  
    43   Node v2=graph.addNode();
    44   Node v3=graph.addNode();
    45   Node v4=graph.addNode();
    46   Node v5=graph.addNode();
    47   Node t=graph.addNode();
    48 
    49   Edge s_v1=graph.addEdge(s, v1);
    50   Edge v1_v2=graph.addEdge(v1, v2);
    51   Edge s_v3=graph.addEdge(s, v3);
    52   Edge v2_v4=graph.addEdge(v2, v4);
    53   Edge v2_v5=graph.addEdge(v2, v5);
    54   Edge v3_v5=graph.addEdge(v3, v5);
    55   Edge v4_t=graph.addEdge(v4, t);
    56   Edge v5_t=graph.addEdge(v5, t);
    57   
    58 
    59   Graph::EdgeMap<int> length(graph);
    60 
    61   length.set(s_v1, 6);
    62   length.set(v1_v2, 4);
    63   length.set(s_v3, 10);
    64   length.set(v2_v4, 5);
    65   length.set(v2_v5, 1);
    66   length.set(v3_v5, 5);
    67   length.set(v4_t, 8);
    68   length.set(v5_t, 8);
    69 
    70   std::cout << "Minlengthpaths algorithm test..." << std::endl;
    71 
    72   
    73   int k=3;
    74   Suurballe< Graph, Graph::EdgeMap<int> >
    75     surb_test(graph, length, s, t);
    76 
    77   check(  surb_test.run(k) == 2 && surb_test.totalLength() == 46,
    78 	  "Two paths, total length should be 46");
    79 
    80   check(  surb_test.checkComplementarySlackness(),
    81 	  "Complementary slackness conditions are not met.");
    82 
    83   //  typedef DirPath<Graph> DPath;
    84   //  DPath P(graph);
    85 
    86   /*
    87   surb_test.getPath(P,0);
    88   check(P.length() == 4, "First path should contain 4 edges.");  
    89   std::cout<<P.length()<<std::endl;
    90   surb_test.getPath(P,1);
    91   check(P.length() == 3, "Second path: 3 edges.");
    92   std::cout<<P.length()<<std::endl;
    93   */  
    94 
    95   k=1;
    96   check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,
    97 	  "One path, total length should be 19");
    98 
    99   check(  surb_test.checkComplementarySlackness(),
   100 	  "Complementary slackness conditions are not met.");
   101  
   102   //  surb_test.getPath(P,0);
   103   //  check(P.length() == 4, "First path should contain 4 edges.");  
   104 
   105   std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
   106 	    << std::endl;
   107 
   108   return passed ? 0 : 1;
   109 
   110 }