test/min_cost_flow_test.cc
author alpar
Wed, 04 Jan 2006 13:19:12 +0000
changeset 1873 d73c7f115f53
parent 1359 1581f961cfaa
child 1875 98698b69a902
permissions -rw-r--r--
IterableBool{Upper/Lower}NodeMaps
     1 /* -*- C++ -*-
     2  * test/min_cost_flow_test.cc - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #include <iostream>
    18 #include "test_tools.h"
    19 #include <lemon/list_graph.h>
    20 #include <lemon/min_cost_flow.h>
    21 //#include <path.h>
    22 //#include <maps.h>
    23 
    24 using namespace lemon;
    25 
    26 
    27 bool passed = true;
    28 /*
    29 void check(bool rc, char *msg="") {
    30   passed = passed && rc;
    31   if(!rc) {
    32     std::cerr << "Test failed! ("<< msg << ")" << std::endl; \
    33  
    34 
    35   }
    36 }
    37 */
    38 
    39 
    40 int main()
    41 {
    42   typedef ListGraph Graph;
    43   typedef Graph::Node Node;
    44   typedef Graph::Edge Edge;
    45 
    46   Graph graph;
    47 
    48   //Ahuja könyv példája
    49 
    50   Node s=graph.addNode();
    51   Node v1=graph.addNode();  
    52   Node v2=graph.addNode();
    53   Node v3=graph.addNode();
    54   Node v4=graph.addNode();
    55   Node v5=graph.addNode();
    56   Node t=graph.addNode();
    57 
    58   Edge s_v1=graph.addEdge(s, v1);
    59   Edge v1_v2=graph.addEdge(v1, v2);
    60   Edge s_v3=graph.addEdge(s, v3);
    61   Edge v2_v4=graph.addEdge(v2, v4);
    62   Edge v2_v5=graph.addEdge(v2, v5);
    63   Edge v3_v5=graph.addEdge(v3, v5);
    64   Edge v4_t=graph.addEdge(v4, t);
    65   Edge v5_t=graph.addEdge(v5, t);
    66   
    67 
    68   Graph::EdgeMap<int> length(graph);
    69 
    70   length.set(s_v1, 6);
    71   length.set(v1_v2, 4);
    72   length.set(s_v3, 10);
    73   length.set(v2_v4, 5);
    74   length.set(v2_v5, 1);
    75   length.set(v3_v5, 4);
    76   length.set(v4_t, 8);
    77   length.set(v5_t, 8);
    78 
    79   Graph::EdgeMap<int> capacity(graph);
    80 
    81   capacity.set(s_v1, 2);
    82   capacity.set(v1_v2, 2);
    83   capacity.set(s_v3, 1);
    84   capacity.set(v2_v4, 1);
    85   capacity.set(v2_v5, 1);
    86   capacity.set(v3_v5, 1);
    87   capacity.set(v4_t, 1);
    88   capacity.set(v5_t, 2);
    89 
    90   //  ConstMap<Edge, int> const1map(1);
    91   std::cout << "Mincostflows algorithm test..." << std::endl;
    92 
    93   MinCostFlow< Graph, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    94     surb_test(graph, length, capacity, s, t);
    95 
    96   int k=1;
    97 
    98   surb_test.augment();
    99   check(  surb_test.flowValue() == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
   100 
   101   check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
   102 
   103   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
   104   
   105   k=2;
   106   
   107   check(  surb_test.run(k) == 2 && surb_test.totalLength() == 41,"Two paths, total length should be 41");
   108 
   109   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
   110   
   111   surb_test.augment();
   112   surb_test.augment();
   113   surb_test.augment();
   114   k=4;
   115 
   116   check(  surb_test.run(k) == 3 && surb_test.totalLength() == 64,"Three paths, total length should be 64");
   117 
   118   check(surb_test.checkComplementarySlackness(), "Is the primal-dual solution pair really optimal?");
   119 
   120 
   121   std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
   122 	    << std::endl;
   123 
   124   return passed ? 0 : 1;
   125 
   126 }