src/work/athos/mincostflows_test.cc
author alpar
Fri, 07 May 2004 06:57:50 +0000
changeset 567 efaa79ee8d14
parent 551 d167149bde95
permissions -rw-r--r--
time_measure.cc was renamed to time_measure_test.cc
Add an alternative dijsktra_test.cc
     1 #include <iostream>
     2 #include <list_graph.h>
     3 #include <mincostflows.h>
     4 //#include <path.h>
     5 //#include <maps.h>
     6 
     7 using namespace std;
     8 using namespace hugo;
     9 
    10 
    11 
    12 bool passed = true;
    13 
    14 void check(bool rc, char *msg="") {
    15   passed = passed && rc;
    16   if(!rc) {
    17     std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
    18  
    19 
    20   }
    21 }
    22 
    23 
    24 
    25 int main()
    26 {
    27 
    28   typedef ListGraph::Node Node;
    29   typedef ListGraph::Edge Edge;
    30 
    31   ListGraph graph;
    32 
    33   //Ahuja könyv példája
    34 
    35   Node s=graph.addNode();
    36   Node v1=graph.addNode();  
    37   Node v2=graph.addNode();
    38   Node v3=graph.addNode();
    39   Node v4=graph.addNode();
    40   Node v5=graph.addNode();
    41   Node t=graph.addNode();
    42 
    43   Edge s_v1=graph.addEdge(s, v1);
    44   Edge v1_v2=graph.addEdge(v1, v2);
    45   Edge s_v3=graph.addEdge(s, v3);
    46   Edge v2_v4=graph.addEdge(v2, v4);
    47   Edge v2_v5=graph.addEdge(v2, v5);
    48   Edge v3_v5=graph.addEdge(v3, v5);
    49   Edge v4_t=graph.addEdge(v4, t);
    50   Edge v5_t=graph.addEdge(v5, t);
    51   
    52 
    53   ListGraph::EdgeMap<int> length(graph);
    54 
    55   length.set(s_v1, 6);
    56   length.set(v1_v2, 4);
    57   length.set(s_v3, 10);
    58   length.set(v2_v4, 5);
    59   length.set(v2_v5, 1);
    60   length.set(v3_v5, 5);
    61   length.set(v4_t, 8);
    62   length.set(v5_t, 8);
    63 
    64   ConstMap<Edge, int> const1map(1);
    65   std::cout << "Mincostflows algorithm test..." << std::endl;
    66 
    67   
    68   int k=3;
    69   MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ConstMap<Edge, int> >
    70     surb_test(graph, length, const1map);
    71 
    72   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
    73 
    74   check(surb_test.checkSolution(), "Is the primal-dual solution pair really optimal?");
    75 
    76   k=1;
    77   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
    78 
    79   check(surb_test.checkSolution(), "Is the primal-dual solution pair really optimal?");
    80   
    81   //cout << surb_test.run(s,t,k) << surb_test.totalLength()<<endl;
    82   /*
    83   typedef DirPath<ListGraph> DPath;
    84   DPath P(graph);
    85 
    86   surb_test.getPath(P,0);
    87   check(P.length() == 4, "First path should contain 4 edges.");  
    88 
    89   surb_test.getPath(P,1);
    90   check(P.length() == 3, "Second path: 3 edges.");
    91   
    92   k=1;
    93   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
    94  
    95   surb_test.getPath(P,0);
    96   check(P.length() == 4, "First path should contain 4 edges.");  
    97   */
    98   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
    99        << endl;
   100 
   101   return passed ? 0 : 1;
   102 
   103 }