Files @ r416:26fd85a3087e

Location: LEMON/LEMON-official/test/circulation_test.cc

Load file history 
r416:26fd85a3087e
3.0 KiB
text/x-c++src
Show annotation Show as raw Download as raw
gravatar
alpar (Alpar Juttner)
Def->Set change in lemon/circulation.h
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */



///\ingroup demos

///\file

///\brief Demonstrating the usage of LEMON's General Flow algorithm

///

/// This demo program reads a general network circulation problem from the

/// file 'circulation-input.lgf', runs the preflow based algorithm for

/// finding a feasible solution and writes the output

/// to 'circulation-input.lgf'

///

/// \include circulation_demo.cc



#include <iostream>



#include "test_tools.h"

#include <lemon/list_graph.h>

#include <lemon/circulation.h>

#include <lemon/lgf_reader.h>



using namespace lemon;



char test_lgf[] =

  "@nodes\n"

  "label delta\n"

  "0     0\n"

  "1     13\n"

  "2     0\n"

  "3     0\n"

  "4     0\n"

  "5     0\n"

  "6     0\n"

  "7     0\n"

  "8     -13\n"

  "9     0\n"

  "@edges\n"

  "    label lo_cap up_cap\n"

  "0 1 0     0      20\n"

  "0 2 1     0      0\n"

  "1 1 2     0      3\n"

  "1 2 3     0      8\n"

  "1 3 4     0      8\n"

  "2 5 5     0      5\n"

  "3 2 6     0      5\n"

  "3 5 7     0      5\n"

  "3 6 8     0      5\n"

  "4 3 9     0      3\n"

  "5 7 10    0      3\n"

  "5 6 11    0      10\n"

  "5 8 12    0      10\n"

  "6 8 13    0      8\n"

  "8 9 14    0      20\n"

  "8 1 15    0      5\n"

  "9 5 16    0      5\n"

  "@attributes\n"

  "source 1\n"

  "sink   8\n";



int main (int, char*[])

{



    typedef ListDigraph Digraph;

    typedef Digraph::Node Node;

    typedef Digraph::NodeIt NodeIt;

    typedef Digraph::Arc Arc;

    typedef Digraph::ArcIt ArcIt;

    typedef Digraph::ArcMap<int> ArcMap;

    typedef Digraph::NodeMap<int> NodeMap;

    typedef Digraph::NodeMap<double> DNodeMap;



    Digraph g;

    ArcMap lo(g);

    ArcMap up(g);

    NodeMap delta(g);

    NodeMap nid(g);

    ArcMap eid(g);

    Node source, sink;

    

    std::istringstream input(test_lgf);

    DigraphReader<Digraph>(g,input).

      arcMap("lo_cap", lo).

      arcMap("up_cap", up).

      nodeMap("delta", delta).

      arcMap("label", eid).

      nodeMap("label", nid).

      node("source",source).

      node("sink",sink).

      run();



    Circulation<Digraph> gen(g,lo,up,delta);

    bool ret=gen.run();

    check(ret,"A feasible solution should have been found.");

    check(gen.checkFlow(), "The found flow is corrupt.");

    

    delta[source]=14;

    delta[sink]=-14;

    

    bool ret2=gen.run();

    check(!ret2,"A feasible solution should not have been found.");

    check(gen.checkBarrier(), "The found barrier is corrupt.");



}