test/suurballe_test.cc
changeset 414 05357da973ce
parent 345 2f64c4a692a8
child 423 ff48c2738fb2
equal deleted inserted replaced
0:d41f89f1f661 1:db3382f2579f
    26 
    26 
    27 #include "test_tools.h"
    27 #include "test_tools.h"
    28 
    28 
    29 using namespace lemon;
    29 using namespace lemon;
    30 
    30 
    31 // Checks the feasibility of the flow
    31 // Check the feasibility of the flow
    32 template <typename Digraph, typename FlowMap>
    32 template <typename Digraph, typename FlowMap>
    33 bool checkFlow( const Digraph& gr, const FlowMap& flow, 
    33 bool checkFlow( const Digraph& gr, const FlowMap& flow, 
    34                 typename Digraph::Node s, typename Digraph::Node t,
    34                 typename Digraph::Node s, typename Digraph::Node t,
    35                 int value )
    35                 int value )
    36 {
    36 {
    50   }
    50   }
    51 
    51 
    52   return true;
    52   return true;
    53 }
    53 }
    54 
    54 
    55 // Checks the optimalitiy of the flow
    55 // Check the optimalitiy of the flow
    56 template < typename Digraph, typename CostMap, 
    56 template < typename Digraph, typename CostMap, 
    57            typename FlowMap, typename PotentialMap >
    57            typename FlowMap, typename PotentialMap >
    58 bool checkOptimality( const Digraph& gr, const CostMap& cost,
    58 bool checkOptimality( const Digraph& gr, const CostMap& cost,
    59                       const FlowMap& flow, const PotentialMap& pi )
    59                       const FlowMap& flow, const PotentialMap& pi )
    60 {
    60 {
    61   // Checking the Complementary Slackness optimality condition
    61   // Check the "Complementary Slackness" optimality condition
    62   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    62   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    63   bool opt = true;
    63   bool opt = true;
    64   for (ArcIt e(gr); e != INVALID; ++e) {
    64   for (ArcIt e(gr); e != INVALID; ++e) {
    65     typename CostMap::Value red_cost =
    65     typename CostMap::Value red_cost =
    66       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
    66       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
    69     if (!opt) break;
    69     if (!opt) break;
    70   }
    70   }
    71   return opt;
    71   return opt;
    72 }
    72 }
    73 
    73 
    74 // Checks a path
    74 // Check a path
    75 template < typename Digraph, typename Path >
    75 template <typename Digraph, typename Path>
    76 bool checkPath( const Digraph& gr, const Path& path,
    76 bool checkPath( const Digraph& gr, const Path& path,
    77                 typename Digraph::Node s, typename Digraph::Node t)
    77                 typename Digraph::Node s, typename Digraph::Node t)
    78 {
    78 {
    79   // Checking the Complementary Slackness optimality condition
    79   // Check the "Complementary Slackness" optimality condition
    80   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    80   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    81   Node n = s;
    81   Node n = s;
    82   for (int i = 0; i < path.length(); ++i) {
    82   for (int i = 0; i < path.length(); ++i) {
    83     if (gr.source(path.nth(i)) != n) return false;
    83     if (gr.source(path.nth(i)) != n) return false;
    84     n = gr.target(path.nth(i));
    84     n = gr.target(path.nth(i));
    89 
    89 
    90 int main()
    90 int main()
    91 {
    91 {
    92   DIGRAPH_TYPEDEFS(ListDigraph);
    92   DIGRAPH_TYPEDEFS(ListDigraph);
    93 
    93 
    94   // Reading the test digraph
    94   // Read the test digraph
    95   ListDigraph digraph;
    95   ListDigraph digraph;
    96   ListDigraph::ArcMap<int> length(digraph);
    96   ListDigraph::ArcMap<int> length(digraph);
    97   Node source, target;
    97   Node source, target;
    98 
    98 
    99   std::string fname;
    99   std::string fname;
   109     node("source", source).
   109     node("source", source).
   110     node("target", target).
   110     node("target", target).
   111     run();
   111     run();
   112   input.close();
   112   input.close();
   113   
   113   
   114   // Finding 2 paths
   114   // Find 2 paths
   115   {
   115   {
   116     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   116     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   117     check(suurballe.run(2) == 2, "Wrong number of paths");
   117     check(suurballe.run(2) == 2, "Wrong number of paths");
   118     check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
   118     check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
   119           "The flow is not feasible");
   119           "The flow is not feasible");
   124     for (int i = 0; i < suurballe.pathNum(); ++i)
   124     for (int i = 0; i < suurballe.pathNum(); ++i)
   125       check(checkPath(digraph, suurballe.path(i), source, target),
   125       check(checkPath(digraph, suurballe.path(i), source, target),
   126             "Wrong path");
   126             "Wrong path");
   127   }
   127   }
   128 
   128 
   129   // Finding 3 paths
   129   // Find 3 paths
   130   {
   130   {
   131     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   131     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   132     check(suurballe.run(3) == 3, "Wrong number of paths");
   132     check(suurballe.run(3) == 3, "Wrong number of paths");
   133     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
   133     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
   134           "The flow is not feasible");
   134           "The flow is not feasible");
   139     for (int i = 0; i < suurballe.pathNum(); ++i)
   139     for (int i = 0; i < suurballe.pathNum(); ++i)
   140       check(checkPath(digraph, suurballe.path(i), source, target),
   140       check(checkPath(digraph, suurballe.path(i), source, target),
   141             "Wrong path");
   141             "Wrong path");
   142   }
   142   }
   143 
   143 
   144   // Finding 5 paths (only 3 can be found)
   144   // Find 5 paths (only 3 can be found)
   145   {
   145   {
   146     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   146     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   147     check(suurballe.run(5) == 3, "Wrong number of paths");
   147     check(suurballe.run(5) == 3, "Wrong number of paths");
   148     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
   148     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
   149           "The flow is not feasible");
   149           "The flow is not feasible");