alpar@345: /* -*- C++ -*-
alpar@345:  *
alpar@345:  * This file is a part of LEMON, a generic C++ optimization library
alpar@345:  *
alpar@345:  * Copyright (C) 2003-2008
alpar@345:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@345:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@345:  *
alpar@345:  * Permission to use, modify and distribute this software is granted
alpar@345:  * provided that this copyright notice appears in all copies. For
alpar@345:  * precise terms see the accompanying LICENSE file.
alpar@345:  *
alpar@345:  * This software is provided "AS IS" with no warranty of any kind,
alpar@345:  * express or implied, and with no claim as to its suitability for any
alpar@345:  * purpose.
alpar@345:  *
alpar@345:  */
alpar@345: 
alpar@345: #include <iostream>
alpar@345: #include <fstream>
alpar@345: 
alpar@345: #include <lemon/list_graph.h>
alpar@345: #include <lemon/lgf_reader.h>
alpar@345: #include <lemon/path.h>
alpar@345: #include <lemon/suurballe.h>
alpar@345: 
alpar@345: #include "test_tools.h"
alpar@345: 
alpar@345: using namespace lemon;
alpar@345: 
kpeter@346: // Check the feasibility of the flow
alpar@345: template <typename Digraph, typename FlowMap>
alpar@345: bool checkFlow( const Digraph& gr, const FlowMap& flow, 
alpar@345:                 typename Digraph::Node s, typename Digraph::Node t,
alpar@345:                 int value )
alpar@345: {
alpar@345:   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@345:   for (ArcIt e(gr); e != INVALID; ++e)
alpar@345:     if (!(flow[e] == 0 || flow[e] == 1)) return false;
alpar@345: 
alpar@345:   for (NodeIt n(gr); n != INVALID; ++n) {
alpar@345:     int sum = 0;
alpar@345:     for (OutArcIt e(gr, n); e != INVALID; ++e)
alpar@345:       sum += flow[e];
alpar@345:     for (InArcIt e(gr, n); e != INVALID; ++e)
alpar@345:       sum -= flow[e];
alpar@345:     if (n == s && sum != value) return false;
alpar@345:     if (n == t && sum != -value) return false;
alpar@345:     if (n != s && n != t && sum != 0) return false;
alpar@345:   }
alpar@345: 
alpar@345:   return true;
alpar@345: }
alpar@345: 
kpeter@346: // Check the optimalitiy of the flow
alpar@345: template < typename Digraph, typename CostMap, 
alpar@345:            typename FlowMap, typename PotentialMap >
alpar@345: bool checkOptimality( const Digraph& gr, const CostMap& cost,
alpar@345:                       const FlowMap& flow, const PotentialMap& pi )
alpar@345: {
kpeter@346:   // Check the "Complementary Slackness" optimality condition
alpar@345:   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@345:   bool opt = true;
alpar@345:   for (ArcIt e(gr); e != INVALID; ++e) {
alpar@345:     typename CostMap::Value red_cost =
alpar@345:       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
alpar@345:     opt = (flow[e] == 0 && red_cost >= 0) ||
alpar@345:           (flow[e] == 1 && red_cost <= 0);
alpar@345:     if (!opt) break;
alpar@345:   }
alpar@345:   return opt;
alpar@345: }
alpar@345: 
kpeter@346: // Check a path
kpeter@346: template <typename Digraph, typename Path>
alpar@345: bool checkPath( const Digraph& gr, const Path& path,
alpar@345:                 typename Digraph::Node s, typename Digraph::Node t)
alpar@345: {
kpeter@346:   // Check the "Complementary Slackness" optimality condition
alpar@345:   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@345:   Node n = s;
alpar@345:   for (int i = 0; i < path.length(); ++i) {
alpar@345:     if (gr.source(path.nth(i)) != n) return false;
alpar@345:     n = gr.target(path.nth(i));
alpar@345:   }
alpar@345:   return n == t;
alpar@345: }
alpar@345: 
alpar@345: 
alpar@345: int main()
alpar@345: {
alpar@345:   DIGRAPH_TYPEDEFS(ListDigraph);
alpar@345: 
kpeter@346:   // Read the test digraph
alpar@345:   ListDigraph digraph;
alpar@345:   ListDigraph::ArcMap<int> length(digraph);
alpar@345:   Node source, target;
alpar@345: 
alpar@345:   std::string fname;
alpar@345:   if(getenv("srcdir"))
alpar@345:     fname = std::string(getenv("srcdir"));
alpar@345:   else fname = ".";
alpar@345:   fname += "/test/min_cost_flow_test.lgf";
alpar@345: 
alpar@345:   std::ifstream input(fname.c_str());
alpar@345:   check(input, "Input file '" << fname << "' not found");
alpar@345:   DigraphReader<ListDigraph>(digraph, input).
alpar@345:     arcMap("cost", length).
alpar@345:     node("source", source).
alpar@345:     node("target", target).
alpar@345:     run();
alpar@345:   input.close();
alpar@345:   
kpeter@346:   // Find 2 paths
alpar@345:   {
alpar@345:     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
alpar@345:     check(suurballe.run(2) == 2, "Wrong number of paths");
alpar@345:     check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
alpar@345:           "The flow is not feasible");
alpar@345:     check(suurballe.totalLength() == 510, "The flow is not optimal");
alpar@345:     check(checkOptimality(digraph, length, suurballe.flowMap(), 
alpar@345:                           suurballe.potentialMap()),
alpar@345:           "Wrong potentials");
alpar@345:     for (int i = 0; i < suurballe.pathNum(); ++i)
alpar@345:       check(checkPath(digraph, suurballe.path(i), source, target),
alpar@345:             "Wrong path");
alpar@345:   }
alpar@345: 
kpeter@346:   // Find 3 paths
alpar@345:   {
alpar@345:     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
alpar@345:     check(suurballe.run(3) == 3, "Wrong number of paths");
alpar@345:     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
alpar@345:           "The flow is not feasible");
alpar@345:     check(suurballe.totalLength() == 1040, "The flow is not optimal");
alpar@345:     check(checkOptimality(digraph, length, suurballe.flowMap(), 
alpar@345:                           suurballe.potentialMap()),
alpar@345:           "Wrong potentials");
alpar@345:     for (int i = 0; i < suurballe.pathNum(); ++i)
alpar@345:       check(checkPath(digraph, suurballe.path(i), source, target),
alpar@345:             "Wrong path");
alpar@345:   }
alpar@345: 
kpeter@346:   // Find 5 paths (only 3 can be found)
alpar@345:   {
alpar@345:     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
alpar@345:     check(suurballe.run(5) == 3, "Wrong number of paths");
alpar@345:     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
alpar@345:           "The flow is not feasible");
alpar@345:     check(suurballe.totalLength() == 1040, "The flow is not optimal");
alpar@345:     check(checkOptimality(digraph, length, suurballe.flowMap(), 
alpar@345:                           suurballe.potentialMap()),
alpar@345:           "Wrong potentials");
alpar@345:     for (int i = 0; i < suurballe.pathNum(); ++i)
alpar@345:       check(checkPath(digraph, suurballe.path(i), source, target),
alpar@345:             "Wrong path");
alpar@345:   }
alpar@345: 
alpar@345:   return 0;
alpar@345: }