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