/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

 *

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

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

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <iostream>

#include <fstream>

#include <lemon/list_graph.h>

#include <lemon/graph_reader.h>

#include <lemon/path.h>

#include <lemon/suurballe.h>

#include "test_tools.h"

using namespace lemon;

// Checks the feasibility of the flow

template <typename Graph, typename FlowMap>

bool checkFlow( const Graph& gr, const FlowMap& flow, 

                typename Graph::Node s, typename Graph::Node t,

                int value )

{

  GRAPH_TYPEDEFS(typename Graph);

  for (EdgeIt e(gr); e != INVALID; ++e)

    if (!(flow[e] == 0 || flow[e] == 1)) return false;

  for (NodeIt n(gr); n != INVALID; ++n) {

    int sum = 0;

    for (OutEdgeIt e(gr, n); e != INVALID; ++e)

      sum += flow[e];

    for (InEdgeIt e(gr, n); e != INVALID; ++e)

      sum -= flow[e];

    if (n == s && sum != value) return false;

    if (n == t && sum != -value) return false;

    if (n != s && n != t && sum != 0) return false;

  }

  return true;

}

// Checks the optimalitiy of the flow

template < typename Graph, typename CostMap, 

           typename FlowMap, typename PotentialMap >

bool checkOptimality( const Graph& gr, const CostMap& cost,

                      const FlowMap& flow, const PotentialMap& pi )

{

  // Checking the Complementary Slackness optimality condition

  GRAPH_TYPEDEFS(typename Graph);

  bool opt = true;

  for (EdgeIt e(gr); e != INVALID; ++e) {

    typename CostMap::Value red_cost =

      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];

    opt = (flow[e] == 0 && red_cost >= 0) ||

          (flow[e] == 1 && red_cost <= 0);

    if (!opt) break;

  }

  return opt;

}

// Checks a path

template < typename Graph, typename Path >

bool checkPath( const Graph& gr, const Path& path,

                typename Graph::Node s, typename Graph::Node t)

{

  // Checking the Complementary Slackness optimality condition

  GRAPH_TYPEDEFS(typename Graph);

  Node n = s;

  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()

{

  GRAPH_TYPEDEFS(ListGraph);

  // Reading the test graph

  ListGraph graph;

  ListGraph::EdgeMap<int> length(graph);

  Node source, target;

  std::string fname;

  if(getenv("srcdir"))

    fname = std::string(getenv("srcdir"));

  else fname = ".";

  fname += "/test/min_cost_flow_test.lgf";

  std::ifstream input(fname.c_str());

  check(input, "Input file '" << fname << "' not found");

  GraphReader<ListGraph>(input, graph).

    readEdgeMap("cost", length).

    readNode("source", source).

    readNode("target", target).

    run();

  input.close();

  // Finding 2 paths

  {

    Suurballe<ListGraph> suurballe(graph, length, source, target);

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

    check(checkFlow(graph, suurballe.flowMap(), source, target, 2),

          "The flow is not feasible");

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

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

                          suurballe.potentialMap()),

          "Wrong potentials");

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

      check(checkPath(graph, suurballe.path(i), source, target),

            "Wrong path");

  }

  // Finding 3 paths

  {

    Suurballe<ListGraph> suurballe(graph, length, source, target);

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

    check(checkFlow(graph, suurballe.flowMap(), source, target, 3),

          "The flow is not feasible");

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

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

                          suurballe.potentialMap()),

          "Wrong potentials");

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

      check(checkPath(graph, suurballe.path(i), source, target),

            "Wrong path");

  }

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

  {

    Suurballe<ListGraph> suurballe(graph, length, source, target);

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

    check(checkFlow(graph, suurballe.flowMap(), source, target, 3),

          "The flow is not feasible");

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

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

                          suurballe.potentialMap()),

          "Wrong potentials");

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

      check(checkPath(graph, suurballe.path(i), source, target),

            "Wrong path");

  }

  return 0;

}