src/test/mincostflows_test.cc
author marci
Wed, 12 May 2004 13:54:14 +0000
changeset 623 cd4296da1643
child 630 9ea585de06ea
permissions -rw-r--r--
(none)
     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, 5);
    62   length.set(v4_t, 8);
    63   length.set(v5_t, 8);
    64 
    65   ConstMap<Edge, int> const1map(1);
    66   std::cout << "Mincostflows algorithm test..." << std::endl;
    67 
    68   
    69   int k=3;
    70   MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ConstMap<Edge, int> >
    71     surb_test(graph, length, const1map);
    72 
    73   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
    74 
    75   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
    76 
    77   k=1;
    78   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
    79 
    80   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
    81   
    82 
    83   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
    84        << endl;
    85 
    86   return passed ? 0 : 1;
    87 
    88 }