# source:lemon-1.2/test/circulation_test.cc@400:fa341dd6ab23

Last change on this file since 400:fa341dd6ab23 was 400:fa341dd6ab23, checked in by Alpar Juttner <alpar@…>, 15 years ago

Transform circulation demo to test

File size: 3.0 KB
Line
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19///\ingroup demos
20///\file
21///\brief Demonstrating the usage of LEMON's General Flow algorithm
22///
23/// This demo program reads a general network circulation problem from the
24/// file 'circulation-input.lgf', runs the preflow based algorithm for
25/// finding a feasible solution and writes the output
26/// to 'circulation-input.lgf'
27///
28/// \include circulation_demo.cc
29
30#include <iostream>
31
32#include "test_tools.h"
33#include <lemon/list_graph.h>
34#include <lemon/circulation.h>
36
37using namespace lemon;
38
39char test_lgf[] =
40  "@nodes\n"
41  "label delta\n"
42  "0     0\n"
43  "1     13\n"
44  "2     0\n"
45  "3     0\n"
46  "4     0\n"
47  "5     0\n"
48  "6     0\n"
49  "7     0\n"
50  "8     -13\n"
51  "9     0\n"
52  "@edges\n"
53  "    label lo_cap up_cap\n"
54  "0 1 0     0      20\n"
55  "0 2 1     0      0\n"
56  "1 1 2     0      3\n"
57  "1 2 3     0      8\n"
58  "1 3 4     0      8\n"
59  "2 5 5     0      5\n"
60  "3 2 6     0      5\n"
61  "3 5 7     0      5\n"
62  "3 6 8     0      5\n"
63  "4 3 9     0      3\n"
64  "5 7 10    0      3\n"
65  "5 6 11    0      10\n"
66  "5 8 12    0      10\n"
67  "6 8 13    0      8\n"
68  "8 9 14    0      20\n"
69  "8 1 15    0      5\n"
70  "9 5 16    0      5\n"
71  "@attributes\n"
72  "source 1\n"
73  "sink   8\n";
74
75int main (int, char*[])
76{
77
78    typedef ListDigraph Digraph;
79    typedef Digraph::Node Node;
80    typedef Digraph::NodeIt NodeIt;
81    typedef Digraph::Arc Arc;
82    typedef Digraph::ArcIt ArcIt;
83    typedef Digraph::ArcMap<int> ArcMap;
84    typedef Digraph::NodeMap<int> NodeMap;
85    typedef Digraph::NodeMap<double> DNodeMap;
86
87    Digraph g;
88    ArcMap lo(g);
89    ArcMap up(g);
90    NodeMap delta(g);
91    NodeMap nid(g);
92    ArcMap eid(g);
93    Node source, sink;
94
95    std::istringstream input(test_lgf);
97      arcMap("lo_cap", lo).
98      arcMap("up_cap", up).
99      nodeMap("delta", delta).
100      arcMap("label", eid).
101      nodeMap("label", nid).
102      node("source",source).
103      node("sink",sink).
104      run();
105
106    Circulation<Digraph> gen(g,lo,up,delta);
107    bool ret=gen.run();
108    check(ret,"A feasible solution should have been found.");
109    check(gen.checkFlow(), "The found flow is corrupt.");
110
111    delta[source]=14;
112    delta[sink]=-14;
113
114    bool ret2=gen.run();
115    check(!ret2,"A feasible solution should not have been found.");
116    check(gen.checkBarrier(), "The found barrier is corrupt.");
117
118}
Note: See TracBrowser for help on using the repository browser.