test/hao_orlin_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 410 eac19fb31a09
child 596 293551ad254f
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
deba@410
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@410
     2
 *
deba@410
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@410
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
deba@410
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@410
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@410
     8
 *
deba@410
     9
 * Permission to use, modify and distribute this software is granted
deba@410
    10
 * provided that this copyright notice appears in all copies. For
deba@410
    11
 * precise terms see the accompanying LICENSE file.
deba@410
    12
 *
deba@410
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@410
    14
 * express or implied, and with no claim as to its suitability for any
deba@410
    15
 * purpose.
deba@410
    16
 *
deba@410
    17
 */
deba@410
    18
deba@410
    19
#include <sstream>
deba@410
    20
deba@410
    21
#include <lemon/smart_graph.h>
deba@410
    22
#include <lemon/hao_orlin.h>
deba@410
    23
deba@410
    24
#include <lemon/lgf_reader.h>
deba@410
    25
#include "test_tools.h"
deba@410
    26
deba@410
    27
using namespace lemon;
deba@410
    28
using namespace std;
deba@410
    29
deba@410
    30
const std::string lgf =
deba@410
    31
  "@nodes\n"
deba@410
    32
  "label\n"
deba@410
    33
  "0\n"
deba@410
    34
  "1\n"
deba@410
    35
  "2\n"
deba@410
    36
  "3\n"
deba@410
    37
  "4\n"
deba@410
    38
  "5\n"
deba@410
    39
  "@edges\n"
deba@410
    40
  "     label  capacity\n"
deba@410
    41
  "0 1  0      2\n"
deba@410
    42
  "1 2  1      2\n"
deba@410
    43
  "2 0  2      2\n"
deba@410
    44
  "3 4  3      2\n"
deba@410
    45
  "4 5  4      2\n"
deba@410
    46
  "5 3  5      2\n"
deba@410
    47
  "2 3  6      3\n";
deba@410
    48
deba@410
    49
int main() {
deba@410
    50
  SmartGraph graph;
deba@410
    51
  SmartGraph::EdgeMap<int> capacity(graph);
deba@410
    52
deba@410
    53
  istringstream lgfs(lgf);
deba@410
    54
  graphReader(graph, lgfs).
deba@410
    55
    edgeMap("capacity", capacity).run();
deba@410
    56
deba@410
    57
  HaoOrlin<SmartGraph, SmartGraph::EdgeMap<int> > ho(graph, capacity);
deba@410
    58
  ho.run();
deba@410
    59
deba@410
    60
  check(ho.minCutValue() == 3, "Wrong cut value");
deba@410
    61
deba@410
    62
  return 0;
deba@410
    63
}