Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/test/min_cost_flow_test.cc
changeset 1017 f588efc6d607
parent 921 818510fa3d99
child 1164 80bb73097736
equal deleted inserted replaced
2:f666a70877c8 3:b6833b0bec66 
    19 #include <lemon/list_graph.h>
 
    19 #include <lemon/list_graph.h>
 
    20 #include <lemon/min_cost_flow.h>
 
    20 #include <lemon/min_cost_flow.h>
 
    21 //#include <path.h>
 
    21 //#include <path.h>
 
    22 //#include <maps.h>
 
    22 //#include <maps.h>
 
    23 
    23 
    24 using namespace std;
 
       
    25 using namespace lemon;
 
    24 using namespace lemon;
 
    26 
       
    27 
    25 
    28 
    26 
    29 bool passed = true;
 
    27 bool passed = true;
 
    30 /*
 
    28 /*
 
    31 void check(bool rc, char *msg="") {
 
    29 void check(bool rc, char *msg="") {
 
    39 */
 
    37 */
 
    40 
    38 
    41 
    39 
    42 int main()
 
    40 int main()
 
    43 {
 
    41 {
 
       
    42   typedef ListGraph Graph;
 
       
    43   typedef Graph::Node Node;
 
       
    44   typedef Graph::Edge Edge;
 
    44 
    45 
    45   typedef ListGraph::Node Node;
 
    46   Graph graph;
 
    46   typedef ListGraph::Edge Edge;
 
       
    47 
       
    48   ListGraph graph;
 
       
    49 
    47 
    50   //Ahuja könyv példája
 
    48   //Ahuja könyv példája
 
    51 
    49 
    52   Node s=graph.addNode();
 
    50   Node s=graph.addNode();
 
    53   Node v1=graph.addNode();  
    51   Node v1=graph.addNode();  
    65   Edge v3_v5=graph.addEdge(v3, v5);
 
    63   Edge v3_v5=graph.addEdge(v3, v5);
 
    66   Edge v4_t=graph.addEdge(v4, t);
 
    64   Edge v4_t=graph.addEdge(v4, t);
 
    67   Edge v5_t=graph.addEdge(v5, t);
 
    65   Edge v5_t=graph.addEdge(v5, t);
 
    68   
    66   
    69 
    67 
    70   ListGraph::EdgeMap<int> length(graph);
 
    68   Graph::EdgeMap<int> length(graph);
 
    71 
    69 
    72   length.set(s_v1, 6);
 
    70   length.set(s_v1, 6);
 
    73   length.set(v1_v2, 4);
 
    71   length.set(v1_v2, 4);
 
    74   length.set(s_v3, 10);
 
    72   length.set(s_v3, 10);
 
    75   length.set(v2_v4, 5);
 
    73   length.set(v2_v4, 5);
 
    76   length.set(v2_v5, 1);
 
    74   length.set(v2_v5, 1);
 
    77   length.set(v3_v5, 4);
 
    75   length.set(v3_v5, 4);
 
    78   length.set(v4_t, 8);
 
    76   length.set(v4_t, 8);
 
    79   length.set(v5_t, 8);
 
    77   length.set(v5_t, 8);
 
    80 
    78 
    81   ListGraph::EdgeMap<int> capacity(graph);
 
    79   Graph::EdgeMap<int> capacity(graph);
 
    82 
    80 
    83   capacity.set(s_v1, 2);
 
    81   capacity.set(s_v1, 2);
 
    84   capacity.set(v1_v2, 2);
 
    82   capacity.set(v1_v2, 2);
 
    85   capacity.set(s_v3, 1);
 
    83   capacity.set(s_v3, 1);
 
    86   capacity.set(v2_v4, 1);
 
    84   capacity.set(v2_v4, 1);
 
    90   capacity.set(v5_t, 2);
 
    88   capacity.set(v5_t, 2);
 
    91 
    89 
    92   //  ConstMap<Edge, int> const1map(1);
 
    90   //  ConstMap<Edge, int> const1map(1);
 
    93   std::cout << "Mincostflows algorithm test..." << std::endl;
 
    91   std::cout << "Mincostflows algorithm test..." << std::endl;
 
    94 
    92 
    95   MinCostFlow< ListGraph, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> >
 
    93   MinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
 
    96     surb_test(graph, length, capacity);
 
    94     surb_test(graph, length, capacity, s, t);
 
    97 
    95 
    98   int k=1;
 
    96   int k=1;
 
    99 
    97 
   100   check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
 
    98   surb_test.augment();
 
       
    99   check(  surb_test.flowValue() == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
 
       
   100 
       
   101   check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
 
   101 
   102 
   102   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
 
   103   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
 
   103   
   104   
   104   k=2;
 
   105   k=2;
 
   105   
   106   
   106   check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
 
   107   check(  surb_test.run(k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
 
   107 
   108 
   108   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
 
   109   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
 
   109   
   110   
   110   
   111   surb_test.augment();
 
       
   112   surb_test.augment();
 
       
   113   surb_test.augment();
 
   111   k=4;
 
   114   k=4;
 
   112 
   115 
   113   check(  surb_test.run(s,t,k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
 
   116   check(  surb_test.run(k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
 
   114 
   117 
   115   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
 
   118   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
 
   116 
   119 
   117 
   120 
   118   cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
 
   121   std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
 
   119        << endl;
 
   122 	    << std::endl;
 
   120 
   123 
   121   return passed ? 0 : 1;
 
   124   return passed ? 0 : 1;
 
   122 
   125 
   123 }
 
   126 }
lemon-0.x