/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

   typedef concepts::Digraph Digraph;

   typedef concepts::Digraph Digraph;

   typedef Digraph::Node Node;

   typedef Digraph::Node Node;

   typedef Digraph::Arc Arc;

   typedef Digraph::Arc Arc;

   typedef concepts::ReadMap<Arc, VType> LengthMap;

   typedef concepts::ReadMap<Arc, VType> LengthMap;

   typedef Suurballe<Digraph, LengthMap> ST;

   typedef Suurballe<Digraph, LengthMap> ST;

   typedef Suurballe<Digraph, LengthMap>

   typedef Suurballe<Digraph, LengthMap>

     ::SetFlowMap<ST::FlowMap>

     ::SetFlowMap<ST::FlowMap>

     ::SetPotentialMap<ST::PotentialMap>

     ::SetPotentialMap<ST::PotentialMap>

     ::SetPath<SimplePath<Digraph> >

     ::SetPath<SimplePath<Digraph> >

   suurb_test.start(n);

   suurb_test.start(n);

   suurb_test.start(n, k);

   suurb_test.start(n, k);

   k = suurb_test.findFlow(n);

   k = suurb_test.findFlow(n);

   k = suurb_test.findFlow(n, k);

   k = suurb_test.findFlow(n, k);

   suurb_test.findPaths();

   suurb_test.findPaths();

   int f;

   int f;

   VType c;

   VType c;

   c = const_suurb_test.totalLength();

   c = const_suurb_test.totalLength();

   f = const_suurb_test.flow(e);

   f = const_suurb_test.flow(e);

   const SuurballeType::FlowMap& fm =

   const SuurballeType::FlowMap& fm =

   c = const_suurb_test.potential(n);

   c = const_suurb_test.potential(n);

   const SuurballeType::PotentialMap& pm =

   const SuurballeType::PotentialMap& pm =

     const_suurb_test.potentialMap();

     const_suurb_test.potentialMap();

   k = const_suurb_test.pathNum();

   k = const_suurb_test.pathNum();

   Path<Digraph> p = const_suurb_test.path(k);

   Path<Digraph> p = const_suurb_test.path(k);

   ignore_unused_variable_warning(fm);

   ignore_unused_variable_warning(fm);

   ignore_unused_variable_warning(pm);

   ignore_unused_variable_warning(pm);

 }

 }

 // Check the feasibility of the flow

 // Check the feasibility of the flow

     run();

     run();

   // Check run()

   // Check run()

   {

   {

     Suurballe<ListDigraph> suurballe(digraph, length);

     Suurballe<ListDigraph> suurballe(digraph, length);

     // Find 2 paths

     // Find 2 paths

     check(suurballe.run(s, t) == 2, "Wrong number of paths");

     check(suurballe.run(s, t) == 2, "Wrong number of paths");

     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),

     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),

           "The flow is not feasible");

           "The flow is not feasible");

     check(suurballe.totalLength() == 510, "The flow is not optimal");

     check(suurballe.totalLength() == 510, "The flow is not optimal");

     check(checkOptimality(digraph, length, suurballe.flowMap(),

     check(checkOptimality(digraph, length, suurballe.flowMap(),

                           suurballe.potentialMap()),

                           suurballe.potentialMap()),

           "Wrong potentials");

           "Wrong potentials");

     for (int i = 0; i < suurballe.pathNum(); ++i)

     for (int i = 0; i < suurballe.pathNum(); ++i)

       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

     // Find 3 paths

     // Find 3 paths

     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");

     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");

     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),

     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),

           "The flow is not feasible");

           "The flow is not feasible");

     check(suurballe.totalLength() == 1040, "The flow is not optimal");

     check(suurballe.totalLength() == 1040, "The flow is not optimal");

     check(checkOptimality(digraph, length, suurballe.flowMap(),

     check(checkOptimality(digraph, length, suurballe.flowMap(),

                           suurballe.potentialMap()),

                           suurballe.potentialMap()),

           "Wrong potentials");

           "Wrong potentials");

     for (int i = 0; i < suurballe.pathNum(); ++i)

     for (int i = 0; i < suurballe.pathNum(); ++i)

       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

     // Find 5 paths (only 3 can be found)

     // Find 5 paths (only 3 can be found)

     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");

     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");

     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),

     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),

           "The flow is not feasible");

           "The flow is not feasible");

     check(suurballe.totalLength() == 1040, "The flow is not optimal");

     check(suurballe.totalLength() == 1040, "The flow is not optimal");

                           suurballe.potentialMap()),

                           suurballe.potentialMap()),

           "Wrong potentials");

           "Wrong potentials");

     for (int i = 0; i < suurballe.pathNum(); ++i)

     for (int i = 0; i < suurballe.pathNum(); ++i)

       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");

   }

   }

   // Check fullInit() + start()

   // Check fullInit() + start()

   {

   {

     Suurballe<ListDigraph> suurballe(digraph, length);

     Suurballe<ListDigraph> suurballe(digraph, length);

     suurballe.fullInit(s);

     suurballe.fullInit(s);

     // Find 2 paths

     // Find 2 paths

     check(suurballe.start(t) == 2, "Wrong number of paths");

     check(suurballe.start(t) == 2, "Wrong number of paths");

     check(suurballe.totalLength() == 510, "The flow is not optimal");

     check(suurballe.totalLength() == 510, "The flow is not optimal");

     // Find 3 paths

     // Find 3 paths