test/suurballe_test.cc
changeset 2619 30fb4d68b0e8
parent 2553 bfced05fa852
equal deleted inserted replaced
4:c19143472dae 5:8a5d67a9cba7
    15  * purpose.
    15  * purpose.
    16  *
    16  *
    17  */
    17  */
    18 
    18 
    19 #include <iostream>
    19 #include <iostream>
       
    20 #include <fstream>
       
    21 
    20 #include <lemon/list_graph.h>
    22 #include <lemon/list_graph.h>
       
    23 #include <lemon/graph_reader.h>
       
    24 #include <lemon/path.h>
    21 #include <lemon/suurballe.h>
    25 #include <lemon/suurballe.h>
    22 //#include <path.h>
    26 
    23 #include "test_tools.h"
    27 #include "test_tools.h"
    24 
    28 
    25 using namespace lemon;
    29 using namespace lemon;
    26 
    30 
       
    31 // Checks the feasibility of the flow
       
    32 template <typename Graph, typename FlowMap>
       
    33 bool checkFlow( const Graph& gr, const FlowMap& flow, 
       
    34                 typename Graph::Node s, typename Graph::Node t,
       
    35                 int value )
       
    36 {
       
    37   GRAPH_TYPEDEFS(typename Graph);
       
    38   for (EdgeIt e(gr); e != INVALID; ++e)
       
    39     if (!(flow[e] == 0 || flow[e] == 1)) return false;
    27 
    40 
    28 bool passed = true;
    41   for (NodeIt n(gr); n != INVALID; ++n) {
       
    42     int sum = 0;
       
    43     for (OutEdgeIt e(gr, n); e != INVALID; ++e)
       
    44       sum += flow[e];
       
    45     for (InEdgeIt e(gr, n); e != INVALID; ++e)
       
    46       sum -= flow[e];
       
    47     if (n == s && sum != value) return false;
       
    48     if (n == t && sum != -value) return false;
       
    49     if (n != s && n != t && sum != 0) return false;
       
    50   }
       
    51 
       
    52   return true;
       
    53 }
       
    54 
       
    55 // Checks the optimalitiy of the flow
       
    56 template < typename Graph, typename CostMap, 
       
    57            typename FlowMap, typename PotentialMap >
       
    58 bool checkOptimality( const Graph& gr, const CostMap& cost,
       
    59                       const FlowMap& flow, const PotentialMap& pi )
       
    60 {
       
    61   // Checking the Complementary Slackness optimality condition
       
    62   GRAPH_TYPEDEFS(typename Graph);
       
    63   bool opt = true;
       
    64   for (EdgeIt e(gr); e != INVALID; ++e) {
       
    65     typename CostMap::Value red_cost =
       
    66       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
       
    67     opt = (flow[e] == 0 && red_cost >= 0) ||
       
    68           (flow[e] == 1 && red_cost <= 0);
       
    69     if (!opt) break;
       
    70   }
       
    71   return opt;
       
    72 }
       
    73 
       
    74 // Checks a path
       
    75 template < typename Graph, typename Path >
       
    76 bool checkPath( const Graph& gr, const Path& path,
       
    77                 typename Graph::Node s, typename Graph::Node t)
       
    78 {
       
    79   // Checking the Complementary Slackness optimality condition
       
    80   GRAPH_TYPEDEFS(typename Graph);
       
    81   Node n = s;
       
    82   for (int i = 0; i < path.length(); ++i) {
       
    83     if (gr.source(path.nth(i)) != n) return false;
       
    84     n = gr.target(path.nth(i));
       
    85   }
       
    86   return n == t;
       
    87 }
    29 
    88 
    30 
    89 
    31 int main()
    90 int main()
    32 {
    91 {
    33   typedef ListGraph Graph;
    92   GRAPH_TYPEDEFS(ListGraph);
    34   typedef Graph::Node Node;
       
    35   typedef Graph::Edge Edge;
       
    36 
    93 
    37   Graph graph;
    94   // Reading the test graph
       
    95   ListGraph graph;
       
    96   ListGraph::EdgeMap<int> length(graph);
       
    97   Node source, target;
    38 
    98 
    39   //Ahuja könyv példája
    99   std::string fname;
       
   100   if(getenv("srcdir"))
       
   101     fname = std::string(getenv("srcdir"));
       
   102   else fname = ".";
       
   103   fname += "/test/min_cost_flow_test.lgf";
    40 
   104 
    41   Node s=graph.addNode();
   105   std::ifstream input(fname.c_str());
    42   Node v1=graph.addNode();  
   106   check(input, "Input file '" << fname << "' not found");
    43   Node v2=graph.addNode();
   107   GraphReader<ListGraph>(input, graph).
    44   Node v3=graph.addNode();
   108     readEdgeMap("cost", length).
    45   Node v4=graph.addNode();
   109     readNode("source", source).
    46   Node v5=graph.addNode();
   110     readNode("target", target).
    47   Node t=graph.addNode();
   111     run();
       
   112   input.close();
       
   113   
       
   114   // Finding 2 paths
       
   115   {
       
   116     Suurballe<ListGraph> suurballe(graph, length, source, target);
       
   117     check(suurballe.run(2) == 2, "Wrong number of paths");
       
   118     check(checkFlow(graph, suurballe.flowMap(), source, target, 2),
       
   119           "The flow is not feasible");
       
   120     check(suurballe.totalLength() == 510, "The flow is not optimal");
       
   121     check(checkOptimality(graph, length, suurballe.flowMap(), 
       
   122                           suurballe.potentialMap()),
       
   123           "Wrong potentials");
       
   124     for (int i = 0; i < suurballe.pathNum(); ++i)
       
   125       check(checkPath(graph, suurballe.path(i), source, target),
       
   126             "Wrong path");
       
   127   }
    48 
   128 
    49   Edge s_v1=graph.addEdge(s, v1);
   129   // Finding 3 paths
    50   Edge v1_v2=graph.addEdge(v1, v2);
   130   {
    51   Edge s_v3=graph.addEdge(s, v3);
   131     Suurballe<ListGraph> suurballe(graph, length, source, target);
    52   Edge v2_v4=graph.addEdge(v2, v4);
   132     check(suurballe.run(3) == 3, "Wrong number of paths");
    53   Edge v2_v5=graph.addEdge(v2, v5);
   133     check(checkFlow(graph, suurballe.flowMap(), source, target, 3),
    54   Edge v3_v5=graph.addEdge(v3, v5);
   134           "The flow is not feasible");
    55   Edge v4_t=graph.addEdge(v4, t);
   135     check(suurballe.totalLength() == 1040, "The flow is not optimal");
    56   Edge v5_t=graph.addEdge(v5, t);
   136     check(checkOptimality(graph, length, suurballe.flowMap(), 
    57   
   137                           suurballe.potentialMap()),
       
   138           "Wrong potentials");
       
   139     for (int i = 0; i < suurballe.pathNum(); ++i)
       
   140       check(checkPath(graph, suurballe.path(i), source, target),
       
   141             "Wrong path");
       
   142   }
    58 
   143 
    59   Graph::EdgeMap<int> length(graph);
   144   // Finding 5 paths (only 3 can be found)
       
   145   {
       
   146     Suurballe<ListGraph> suurballe(graph, length, source, target);
       
   147     check(suurballe.run(5) == 3, "Wrong number of paths");
       
   148     check(checkFlow(graph, suurballe.flowMap(), source, target, 3),
       
   149           "The flow is not feasible");
       
   150     check(suurballe.totalLength() == 1040, "The flow is not optimal");
       
   151     check(checkOptimality(graph, length, suurballe.flowMap(), 
       
   152                           suurballe.potentialMap()),
       
   153           "Wrong potentials");
       
   154     for (int i = 0; i < suurballe.pathNum(); ++i)
       
   155       check(checkPath(graph, suurballe.path(i), source, target),
       
   156             "Wrong path");
       
   157   }
    60 
   158 
    61   length.set(s_v1, 6);
   159   return 0;
    62   length.set(v1_v2, 4);
       
    63   length.set(s_v3, 10);
       
    64   length.set(v2_v4, 5);
       
    65   length.set(v2_v5, 1);
       
    66   length.set(v3_v5, 5);
       
    67   length.set(v4_t, 8);
       
    68   length.set(v5_t, 8);
       
    69 
       
    70   std::cout << "Minlengthpaths algorithm test..." << std::endl;
       
    71 
       
    72   
       
    73   int k=3;
       
    74   Suurballe< Graph, Graph::EdgeMap<int> >
       
    75     surb_test(graph, length, s, t);
       
    76 
       
    77   check(  surb_test.run(k) == 2 && surb_test.totalLength() == 46,
       
    78 	  "Two paths, total length should be 46");
       
    79 
       
    80   check(  surb_test.checkComplementarySlackness(),
       
    81 	  "Complementary slackness conditions are not met.");
       
    82 
       
    83   //  typedef DirPath<Graph> DPath;
       
    84   //  DPath P(graph);
       
    85 
       
    86   /*
       
    87   surb_test.getPath(P,0);
       
    88   check(P.length() == 4, "First path should contain 4 edges.");  
       
    89   std::cout<<P.length()<<std::endl;
       
    90   surb_test.getPath(P,1);
       
    91   check(P.length() == 3, "Second path: 3 edges.");
       
    92   std::cout<<P.length()<<std::endl;
       
    93   */  
       
    94 
       
    95   k=1;
       
    96   check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,
       
    97 	  "One path, total length should be 19");
       
    98 
       
    99   check(  surb_test.checkComplementarySlackness(),
       
   100 	  "Complementary slackness conditions are not met.");
       
   101  
       
   102   //  surb_test.getPath(P,0);
       
   103   //  check(P.length() == 4, "First path should contain 4 edges.");  
       
   104 
       
   105   std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
       
   106 	    << std::endl;
       
   107 
       
   108   return passed ? 0 : 1;
       
   109 
       
   110 }
   160 }