src/test/min_cost_flow_test.cc
author alpar
Wed, 22 Sep 2004 12:42:19 +0000
changeset 904 b40afcf42a4d
child 906 17f31d280385
permissions -rw-r--r--
Do not document registry and map defines.
     1 #include <iostream>
     2 #include "test_tools.h"
     3 #include <hugo/list_graph.h>
     4 #include <hugo/min_cost_flow.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   MinCostFlow< 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 }