RhodeCode

  for (int i = 0; i < path.length(); ++i) {

    if (gr.source(path.nth(i)) != n) return false;

    n = gr.target(path.nth(i));

  }

  return n == t;

}

int main()

{

  DIGRAPH_TYPEDEFS(ListDigraph);

  // Read the test digraph

  ListDigraph digraph;

  ListDigraph::ArcMap<int> length(digraph);

  Node s, t;

  std::istringstream input(test_lgf);

  DigraphReader<ListDigraph>(digraph, input).

    arcMap("length", length).

    node("source", s).

    node("target", t).

    run();

  {

    Suurballe<ListDigraph> suurballe(digraph, length);

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

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

          "The flow is not feasible");

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

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

                          suurballe.potentialMap()),

          "Wrong potentials");

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

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

  // Find 3 paths

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

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

          "The flow is not feasible");

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

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

                          suurballe.potentialMap()),

          "Wrong potentials");

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

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

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

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

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

          "The flow is not feasible");

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

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

                          suurballe.potentialMap()),

          "Wrong potentials");

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

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

  }

  return 0;

}