alpar@463: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@357:  *
alpar@463:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@357:  *
alpar@463:  * Copyright (C) 2003-2009
alpar@357:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@357:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@357:  *
alpar@357:  * Permission to use, modify and distribute this software is granted
alpar@357:  * provided that this copyright notice appears in all copies. For
alpar@357:  * precise terms see the accompanying LICENSE file.
alpar@357:  *
alpar@357:  * This software is provided "AS IS" with no warranty of any kind,
alpar@357:  * express or implied, and with no claim as to its suitability for any
alpar@357:  * purpose.
alpar@357:  *
alpar@357:  */
alpar@357: 
alpar@357: #include <iostream>
alpar@357: 
alpar@357: #include <lemon/list_graph.h>
alpar@357: #include <lemon/lgf_reader.h>
alpar@357: #include <lemon/path.h>
alpar@357: #include <lemon/suurballe.h>
kpeter@670: #include <lemon/concepts/digraph.h>
kpeter@931: #include <lemon/concepts/heap.h>
alpar@357: 
alpar@357: #include "test_tools.h"
alpar@357: 
alpar@357: using namespace lemon;
alpar@357: 
alpar@442: char test_lgf[] =
alpar@442:   "@nodes\n"
kpeter@670:   "label\n"
kpeter@670:   "1\n"
kpeter@670:   "2\n"
kpeter@670:   "3\n"
kpeter@670:   "4\n"
kpeter@670:   "5\n"
kpeter@670:   "6\n"
kpeter@670:   "7\n"
kpeter@670:   "8\n"
kpeter@670:   "9\n"
kpeter@670:   "10\n"
kpeter@670:   "11\n"
kpeter@670:   "12\n"
alpar@442:   "@arcs\n"
kpeter@670:   "      length\n"
kpeter@670:   " 1  2  70\n"
kpeter@670:   " 1  3 150\n"
kpeter@670:   " 1  4  80\n"
kpeter@670:   " 2  8  80\n"
kpeter@670:   " 3  5 140\n"
kpeter@670:   " 4  6  60\n"
kpeter@670:   " 4  7  80\n"
kpeter@670:   " 4  8 110\n"
kpeter@670:   " 5  7  60\n"
kpeter@670:   " 5 11 120\n"
kpeter@670:   " 6  3   0\n"
kpeter@670:   " 6  9 140\n"
kpeter@670:   " 6 10  90\n"
kpeter@670:   " 7  1  30\n"
kpeter@670:   " 8 12  60\n"
kpeter@670:   " 9 12  50\n"
kpeter@670:   "10 12  70\n"
kpeter@670:   "10  2 100\n"
kpeter@670:   "10  7  60\n"
kpeter@670:   "11 10  20\n"
kpeter@670:   "12 11  30\n"
alpar@442:   "@attributes\n"
alpar@442:   "source  1\n"
alpar@442:   "target 12\n"
alpar@442:   "@end\n";
alpar@442: 
kpeter@670: // Check the interface of Suurballe
kpeter@670: void checkSuurballeCompile()
kpeter@670: {
kpeter@670:   typedef int VType;
kpeter@670:   typedef concepts::Digraph Digraph;
kpeter@670: 
kpeter@670:   typedef Digraph::Node Node;
kpeter@670:   typedef Digraph::Arc Arc;
kpeter@670:   typedef concepts::ReadMap<Arc, VType> LengthMap;
kpeter@670:   
kpeter@931:   typedef Suurballe<Digraph, LengthMap> ST;
kpeter@931:   typedef Suurballe<Digraph, LengthMap>
kpeter@931:     ::SetFlowMap<ST::FlowMap>
kpeter@931:     ::SetPotentialMap<ST::PotentialMap>
kpeter@931:     ::SetPath<SimplePath<Digraph> >
kpeter@931:     ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > >
kpeter@931:     ::Create SuurballeType;
kpeter@670: 
kpeter@670:   Digraph g;
kpeter@670:   Node n;
kpeter@670:   Arc e;
kpeter@670:   LengthMap len;
kpeter@670:   SuurballeType::FlowMap flow(g);
kpeter@670:   SuurballeType::PotentialMap pi(g);
kpeter@670: 
kpeter@670:   SuurballeType suurb_test(g, len);
kpeter@670:   const SuurballeType& const_suurb_test = suurb_test;
kpeter@670: 
kpeter@670:   suurb_test
kpeter@670:     .flowMap(flow)
kpeter@670:     .potentialMap(pi);
kpeter@670: 
kpeter@670:   int k;
kpeter@670:   k = suurb_test.run(n, n);
kpeter@670:   k = suurb_test.run(n, n, k);
kpeter@670:   suurb_test.init(n);
kpeter@927:   suurb_test.fullInit(n);
kpeter@927:   suurb_test.start(n);
kpeter@927:   suurb_test.start(n, k);
kpeter@670:   k = suurb_test.findFlow(n);
kpeter@670:   k = suurb_test.findFlow(n, k);
kpeter@670:   suurb_test.findPaths();
kpeter@670:   
kpeter@670:   int f;
kpeter@670:   VType c;
kpeter@670:   c = const_suurb_test.totalLength();
kpeter@670:   f = const_suurb_test.flow(e);
kpeter@670:   const SuurballeType::FlowMap& fm =
kpeter@670:     const_suurb_test.flowMap();
kpeter@670:   c = const_suurb_test.potential(n);
kpeter@670:   const SuurballeType::PotentialMap& pm =
kpeter@670:     const_suurb_test.potentialMap();
kpeter@670:   k = const_suurb_test.pathNum();
kpeter@670:   Path<Digraph> p = const_suurb_test.path(k);
kpeter@670:   
kpeter@670:   ignore_unused_variable_warning(fm);
kpeter@670:   ignore_unused_variable_warning(pm);
kpeter@670: }
kpeter@670: 
kpeter@358: // Check the feasibility of the flow
alpar@357: template <typename Digraph, typename FlowMap>
alpar@463: bool checkFlow( const Digraph& gr, const FlowMap& flow,
alpar@357:                 typename Digraph::Node s, typename Digraph::Node t,
alpar@357:                 int value )
alpar@357: {
alpar@357:   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@357:   for (ArcIt e(gr); e != INVALID; ++e)
alpar@357:     if (!(flow[e] == 0 || flow[e] == 1)) return false;
alpar@357: 
alpar@357:   for (NodeIt n(gr); n != INVALID; ++n) {
alpar@357:     int sum = 0;
alpar@357:     for (OutArcIt e(gr, n); e != INVALID; ++e)
alpar@357:       sum += flow[e];
alpar@357:     for (InArcIt e(gr, n); e != INVALID; ++e)
alpar@357:       sum -= flow[e];
alpar@357:     if (n == s && sum != value) return false;
alpar@357:     if (n == t && sum != -value) return false;
alpar@357:     if (n != s && n != t && sum != 0) return false;
alpar@357:   }
alpar@357: 
alpar@357:   return true;
alpar@357: }
alpar@357: 
kpeter@358: // Check the optimalitiy of the flow
alpar@463: template < typename Digraph, typename CostMap,
alpar@357:            typename FlowMap, typename PotentialMap >
alpar@357: bool checkOptimality( const Digraph& gr, const CostMap& cost,
alpar@357:                       const FlowMap& flow, const PotentialMap& pi )
alpar@357: {
kpeter@358:   // Check the "Complementary Slackness" optimality condition
alpar@357:   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@357:   bool opt = true;
alpar@357:   for (ArcIt e(gr); e != INVALID; ++e) {
alpar@357:     typename CostMap::Value red_cost =
alpar@357:       cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
alpar@357:     opt = (flow[e] == 0 && red_cost >= 0) ||
alpar@357:           (flow[e] == 1 && red_cost <= 0);
alpar@357:     if (!opt) break;
alpar@357:   }
alpar@357:   return opt;
alpar@357: }
alpar@357: 
kpeter@358: // Check a path
kpeter@358: template <typename Digraph, typename Path>
alpar@357: bool checkPath( const Digraph& gr, const Path& path,
alpar@357:                 typename Digraph::Node s, typename Digraph::Node t)
alpar@357: {
alpar@357:   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@357:   Node n = s;
alpar@357:   for (int i = 0; i < path.length(); ++i) {
alpar@357:     if (gr.source(path.nth(i)) != n) return false;
alpar@357:     n = gr.target(path.nth(i));
alpar@357:   }
alpar@357:   return n == t;
alpar@357: }
alpar@357: 
alpar@357: 
alpar@357: int main()
alpar@357: {
alpar@357:   DIGRAPH_TYPEDEFS(ListDigraph);
alpar@357: 
kpeter@358:   // Read the test digraph
alpar@357:   ListDigraph digraph;
alpar@357:   ListDigraph::ArcMap<int> length(digraph);
kpeter@670:   Node s, t;
alpar@357: 
alpar@442:   std::istringstream input(test_lgf);
alpar@357:   DigraphReader<ListDigraph>(digraph, input).
kpeter@670:     arcMap("length", length).
kpeter@670:     node("source", s).
kpeter@670:     node("target", t).
alpar@357:     run();
alpar@463: 
kpeter@932:   // Check run()
alpar@357:   {
kpeter@670:     Suurballe<ListDigraph> suurballe(digraph, length);
kpeter@932:     
kpeter@932:     // Find 2 paths
kpeter@670:     check(suurballe.run(s, t) == 2, "Wrong number of paths");
kpeter@670:     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
alpar@357:           "The flow is not feasible");
alpar@357:     check(suurballe.totalLength() == 510, "The flow is not optimal");
alpar@463:     check(checkOptimality(digraph, length, suurballe.flowMap(),
alpar@357:                           suurballe.potentialMap()),
alpar@357:           "Wrong potentials");
alpar@357:     for (int i = 0; i < suurballe.pathNum(); ++i)
kpeter@670:       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
kpeter@932:    
kpeter@932:     // Find 3 paths
kpeter@670:     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
kpeter@670:     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
alpar@357:           "The flow is not feasible");
alpar@357:     check(suurballe.totalLength() == 1040, "The flow is not optimal");
alpar@463:     check(checkOptimality(digraph, length, suurballe.flowMap(),
alpar@357:                           suurballe.potentialMap()),
alpar@357:           "Wrong potentials");
alpar@357:     for (int i = 0; i < suurballe.pathNum(); ++i)
kpeter@670:       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
kpeter@932:     
kpeter@932:     // Find 5 paths (only 3 can be found)
kpeter@670:     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
kpeter@670:     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
alpar@357:           "The flow is not feasible");
alpar@357:     check(suurballe.totalLength() == 1040, "The flow is not optimal");
alpar@463:     check(checkOptimality(digraph, length, suurballe.flowMap(),
alpar@357:                           suurballe.potentialMap()),
alpar@357:           "Wrong potentials");
alpar@357:     for (int i = 0; i < suurballe.pathNum(); ++i)
kpeter@670:       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
alpar@357:   }
kpeter@932:   
kpeter@932:   // Check fullInit() + start()
kpeter@932:   {
kpeter@932:     Suurballe<ListDigraph> suurballe(digraph, length);
kpeter@932:     suurballe.fullInit(s);
kpeter@932:     
kpeter@932:     // Find 2 paths
kpeter@932:     check(suurballe.start(t) == 2, "Wrong number of paths");
kpeter@932:     check(suurballe.totalLength() == 510, "The flow is not optimal");
kpeter@932: 
kpeter@932:     // Find 3 paths
kpeter@932:     check(suurballe.start(t, 3) == 3, "Wrong number of paths");
kpeter@932:     check(suurballe.totalLength() == 1040, "The flow is not optimal");
kpeter@932: 
kpeter@932:     // Find 5 paths (only 3 can be found)
kpeter@932:     check(suurballe.start(t, 5) == 3, "Wrong number of paths");
kpeter@932:     check(suurballe.totalLength() == 1040, "The flow is not optimal");
kpeter@932:   }
alpar@357: 
alpar@357:   return 0;
alpar@357: }