src/test/mincostflows_test.cc
changeset 896 3a98a1aa5a8f
parent 611 83530dad618a
equal deleted inserted replaced
1:c700e70e004f -1:000000000000
     1 #include <iostream>
       
     2 #include "test_tools.h"
       
     3 #include <hugo/list_graph.h>
       
     4 #include <hugo/mincostflows.h>
       
     5 //#include <path.h>
       
     6 //#include <maps.h>
       
     7 
       
     8 using namespace std;
       
     9 using namespace hugo;
       
    10 
       
    11 
       
    12 
       
    13 bool passed = true;
       
    14 /*
       
    15 void check(bool rc, char *msg="") {
       
    16   passed = passed && rc;
       
    17   if(!rc) {
       
    18     std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
       
    19  
       
    20 
       
    21   }
       
    22 }
       
    23 */
       
    24 
       
    25 
       
    26 int main()
       
    27 {
       
    28 
       
    29   typedef ListGraph::Node Node;
       
    30   typedef ListGraph::Edge Edge;
       
    31 
       
    32   ListGraph graph;
       
    33 
       
    34   //Ahuja könyv példája
       
    35 
       
    36   Node s=graph.addNode();
       
    37   Node v1=graph.addNode();  
       
    38   Node v2=graph.addNode();
       
    39   Node v3=graph.addNode();
       
    40   Node v4=graph.addNode();
       
    41   Node v5=graph.addNode();
       
    42   Node t=graph.addNode();
       
    43 
       
    44   Edge s_v1=graph.addEdge(s, v1);
       
    45   Edge v1_v2=graph.addEdge(v1, v2);
       
    46   Edge s_v3=graph.addEdge(s, v3);
       
    47   Edge v2_v4=graph.addEdge(v2, v4);
       
    48   Edge v2_v5=graph.addEdge(v2, v5);
       
    49   Edge v3_v5=graph.addEdge(v3, v5);
       
    50   Edge v4_t=graph.addEdge(v4, t);
       
    51   Edge v5_t=graph.addEdge(v5, t);
       
    52   
       
    53 
       
    54   ListGraph::EdgeMap<int> length(graph);
       
    55 
       
    56   length.set(s_v1, 6);
       
    57   length.set(v1_v2, 4);
       
    58   length.set(s_v3, 10);
       
    59   length.set(v2_v4, 5);
       
    60   length.set(v2_v5, 1);
       
    61   length.set(v3_v5, 4);
       
    62   length.set(v4_t, 8);
       
    63   length.set(v5_t, 8);
       
    64 
       
    65   ListGraph::EdgeMap<int> capacity(graph);
       
    66 
       
    67   capacity.set(s_v1, 2);
       
    68   capacity.set(v1_v2, 2);
       
    69   capacity.set(s_v3, 1);
       
    70   capacity.set(v2_v4, 1);
       
    71   capacity.set(v2_v5, 1);
       
    72   capacity.set(v3_v5, 1);
       
    73   capacity.set(v4_t, 1);
       
    74   capacity.set(v5_t, 2);
       
    75 
       
    76   //  ConstMap<Edge, int> const1map(1);
       
    77   std::cout << "Mincostflows algorithm test..." << std::endl;
       
    78 
       
    79   MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> >
       
    80     surb_test(graph, length, capacity);
       
    81 
       
    82   int k=1;
       
    83 
       
    84   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
       
    85 
       
    86   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
       
    87   
       
    88   k=2;
       
    89   
       
    90   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
       
    91 
       
    92   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
       
    93   
       
    94   
       
    95   k=4;
       
    96 
       
    97   check(  surb_test.run(s,t,k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
       
    98 
       
    99   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
       
   100 
       
   101 
       
   102   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
       
   103        << endl;
       
   104 
       
   105   return passed ? 0 : 1;
       
   106 
       
   107 }