1/** \file
2 * \brief Tests for Min-Cost Flow Algorithms
3 *
4 * \author Stephan Beyer
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#include "ogdf/graphalg/MinCostFlowReinelt.h"
33#include <testing.h>
34
35template<typename TCost>
36void testModule(const char *name, MinCostFlowModule<TCost> *alg, TCost base)
37{
38 describe(name, [&]() {
39 Graph G;
40 node s = G.newNode();
41 node a = G.newNode();
42 node b = G.newNode();
43 node t = G.newNode();
44 edge sa = G.newEdge(s, a);
45 edge sb = G.newEdge(s, b);
46 edge at = G.newEdge(a, t);
47 edge bt = G.newEdge(b, t);
48 edge ab = G.newEdge(a, b);
49 EdgeArray<int> lb(G, 0);
50 it("works with costs all being zero", [&]() {
51 EdgeArray<int> cap(G, 10000);
52 cap[ab] = 1;
53 EdgeArray<TCost> cost(G, 0);
54 NodeArray<int> supply(G, 0);
55 supply[s] = 20000;
56 supply[t] = -20000;
57 EdgeArray<int> flow(G);
58 bool feasible = alg->call(G, lb, cap, cost, supply, flow);
59
60 AssertThat(feasible, Equals(true));
61 AssertThat(flow[sa], Equals(10000));
62 AssertThat(flow[sb], Equals(10000));
63 AssertThat(flow[at], Equals(10000));
64 AssertThat(flow[bt], Equals(10000));
65 AssertThat(flow[ab], Equals(0));
66 });
67 it("works with non-negative cost", [&]() {
68 EdgeArray<int> cap(G, 10000);
69 cap[ab] = 1;
70 EdgeArray<TCost> cost(G, 100*base);
71 cost[at] = 99*base;
72 cost[ab] = 0;
73 cost[sa] = base;
74 cost[bt] = base;
75 NodeArray<int> supply(G, 0);
76 supply[s] = 10000;
77 supply[t] = -10000;
78 EdgeArray<int> flow(G);
79 bool feasible = alg->call(G, lb, cap, cost, supply, flow);
80
81 AssertThat(feasible, Equals(true));
82 AssertThat(flow[sa], Equals(10000));
83 AssertThat(flow[sb], Equals(0));
84 AssertThat(flow[at], Equals(9999));
85 AssertThat(flow[bt], Equals(1));
86 AssertThat(flow[ab], Equals(1));
87 });
88 it("works with positive and negative cost", [&]() {
89 EdgeArray<int> cap(G, 10000);
90 cap[ab] = 1;
91 EdgeArray<TCost> cost(G, base);
92 cost[ab] = -base;
93 NodeArray<int> supply(G, 0);
94 supply[s] = 10000;
95 supply[t] = -10000;
96 EdgeArray<int> flow(G);
97 bool feasible = alg->call(G, lb, cap, cost, supply, flow);
98
99 AssertThat(feasible, Equals(true));
100 AssertThat(flow[sa], Equals(10000));
101 AssertThat(flow[sb], Equals(0));
102 AssertThat(flow[at], Equals(9999));
103 AssertThat(flow[bt], Equals(1));
104 AssertThat(flow[ab], Equals(1));
105 });
106 it("is unfeasible if supply = demand > edge capacities", [&]() {
107 EdgeArray<int> cap(G, 10000);
108 cap[sb] = cap[at] = 5000;
109 cap[ab] = 1;
110 EdgeArray<TCost> cost(G, -base);
111 NodeArray<int> supply(G, 0);
112 supply[s] = 15000;
113 supply[t] = -15000;
114 EdgeArray<int> flow(G);
115 bool feasible = alg->call(G, lb, cap, cost, supply, flow);
116
117 AssertThat(feasible, Equals(false));
118 });
119 });
120 delete alg;
121}
122
123go_bandit([]() {
124describe("Min-Cost Flow algorithms", []() {
125 testModule<int>("MinCostFlowReinelt with integral cost", new MinCostFlowReinelt<int>(), 1);
126 testModule<double>("MinCostFlowReinelt wit real (double) cost [1]", new MinCostFlowReinelt<double>(), 1.92);
127 testModule<double>("MinCostFlowReinelt wit real (double) cost [2]", new MinCostFlowReinelt<double>(), 0.1432);
128});
129});
130