test/suurballe_test.cc
changeset 964 7fdaa05a69a1
parent 858 9f6ed854d409
child 970 d216e1c8b3fa
equal deleted inserted replaced
7:6a1afa5d496c 8:42ae42ed6143
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    79   typedef concepts::Digraph Digraph;
    79   typedef concepts::Digraph Digraph;
    80 
    80 
    81   typedef Digraph::Node Node;
    81   typedef Digraph::Node Node;
    82   typedef Digraph::Arc Arc;
    82   typedef Digraph::Arc Arc;
    83   typedef concepts::ReadMap<Arc, VType> LengthMap;
    83   typedef concepts::ReadMap<Arc, VType> LengthMap;
    84   
    84 
    85   typedef Suurballe<Digraph, LengthMap> ST;
    85   typedef Suurballe<Digraph, LengthMap> ST;
    86   typedef Suurballe<Digraph, LengthMap>
    86   typedef Suurballe<Digraph, LengthMap>
    87     ::SetFlowMap<ST::FlowMap>
    87     ::SetFlowMap<ST::FlowMap>
    88     ::SetPotentialMap<ST::PotentialMap>
    88     ::SetPotentialMap<ST::PotentialMap>
    89     ::SetPath<SimplePath<Digraph> >
    89     ::SetPath<SimplePath<Digraph> >
   112   suurb_test.start(n);
   112   suurb_test.start(n);
   113   suurb_test.start(n, k);
   113   suurb_test.start(n, k);
   114   k = suurb_test.findFlow(n);
   114   k = suurb_test.findFlow(n);
   115   k = suurb_test.findFlow(n, k);
   115   k = suurb_test.findFlow(n, k);
   116   suurb_test.findPaths();
   116   suurb_test.findPaths();
   117   
   117 
   118   int f;
   118   int f;
   119   VType c;
   119   VType c;
   120   c = const_suurb_test.totalLength();
   120   c = const_suurb_test.totalLength();
   121   f = const_suurb_test.flow(e);
   121   f = const_suurb_test.flow(e);
   122   const SuurballeType::FlowMap& fm =
   122   const SuurballeType::FlowMap& fm =
   124   c = const_suurb_test.potential(n);
   124   c = const_suurb_test.potential(n);
   125   const SuurballeType::PotentialMap& pm =
   125   const SuurballeType::PotentialMap& pm =
   126     const_suurb_test.potentialMap();
   126     const_suurb_test.potentialMap();
   127   k = const_suurb_test.pathNum();
   127   k = const_suurb_test.pathNum();
   128   Path<Digraph> p = const_suurb_test.path(k);
   128   Path<Digraph> p = const_suurb_test.path(k);
   129   
   129 
   130   ignore_unused_variable_warning(fm);
   130   ignore_unused_variable_warning(fm);
   131   ignore_unused_variable_warning(pm);
   131   ignore_unused_variable_warning(pm);
   132 }
   132 }
   133 
   133 
   134 // Check the feasibility of the flow
   134 // Check the feasibility of the flow
   206     run();
   206     run();
   207 
   207 
   208   // Check run()
   208   // Check run()
   209   {
   209   {
   210     Suurballe<ListDigraph> suurballe(digraph, length);
   210     Suurballe<ListDigraph> suurballe(digraph, length);
   211     
   211 
   212     // Find 2 paths
   212     // Find 2 paths
   213     check(suurballe.run(s, t) == 2, "Wrong number of paths");
   213     check(suurballe.run(s, t) == 2, "Wrong number of paths");
   214     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
   214     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
   215           "The flow is not feasible");
   215           "The flow is not feasible");
   216     check(suurballe.totalLength() == 510, "The flow is not optimal");
   216     check(suurballe.totalLength() == 510, "The flow is not optimal");
   217     check(checkOptimality(digraph, length, suurballe.flowMap(),
   217     check(checkOptimality(digraph, length, suurballe.flowMap(),
   218                           suurballe.potentialMap()),
   218                           suurballe.potentialMap()),
   219           "Wrong potentials");
   219           "Wrong potentials");
   220     for (int i = 0; i < suurballe.pathNum(); ++i)
   220     for (int i = 0; i < suurballe.pathNum(); ++i)
   221       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   221       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   222    
   222 
   223     // Find 3 paths
   223     // Find 3 paths
   224     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
   224     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
   225     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   225     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   226           "The flow is not feasible");
   226           "The flow is not feasible");
   227     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   227     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   228     check(checkOptimality(digraph, length, suurballe.flowMap(),
   228     check(checkOptimality(digraph, length, suurballe.flowMap(),
   229                           suurballe.potentialMap()),
   229                           suurballe.potentialMap()),
   230           "Wrong potentials");
   230           "Wrong potentials");
   231     for (int i = 0; i < suurballe.pathNum(); ++i)
   231     for (int i = 0; i < suurballe.pathNum(); ++i)
   232       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   232       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   233     
   233 
   234     // Find 5 paths (only 3 can be found)
   234     // Find 5 paths (only 3 can be found)
   235     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
   235     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
   236     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   236     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   237           "The flow is not feasible");
   237           "The flow is not feasible");
   238     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   238     check(suurballe.totalLength() == 1040, "The flow is not optimal");
   240                           suurballe.potentialMap()),
   240                           suurballe.potentialMap()),
   241           "Wrong potentials");
   241           "Wrong potentials");
   242     for (int i = 0; i < suurballe.pathNum(); ++i)
   242     for (int i = 0; i < suurballe.pathNum(); ++i)
   243       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   243       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   244   }
   244   }
   245   
   245 
   246   // Check fullInit() + start()
   246   // Check fullInit() + start()
   247   {
   247   {
   248     Suurballe<ListDigraph> suurballe(digraph, length);
   248     Suurballe<ListDigraph> suurballe(digraph, length);
   249     suurballe.fullInit(s);
   249     suurballe.fullInit(s);
   250     
   250 
   251     // Find 2 paths
   251     // Find 2 paths
   252     check(suurballe.start(t) == 2, "Wrong number of paths");
   252     check(suurballe.start(t) == 2, "Wrong number of paths");
   253     check(suurballe.totalLength() == 510, "The flow is not optimal");
   253     check(suurballe.totalLength() == 510, "The flow is not optimal");
   254 
   254 
   255     // Find 3 paths
   255     // Find 3 paths