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