1#include <ogdf/graphalg/MaxFlowEdmondsKarp.h>
2#include <ogdf/basic/graph_generators.h>
3#include <ogdf/graphalg/MinSTCutMaxFlow.h>
4#include <ogdf/graphalg/MinSTCutDijkstra.h>
5#include <ogdf/graphalg/MinSTCutBFS.h>
6
7#include <graphs.h>
8
9using std::string;
10
11template<typename T>
12void describeMSTCutFromMaxFlowSuite(const string &name) {
13describe("MinSTCutMaxFlow<" + name + ">", [] {
14 it("can handle an isolated node", [](){
15 Graph graph;
16 node v = graph.newNode();
17 EdgeArray<T> weights(graph, 4);
18
19 EdgeArray<T> flow;
20 MaxFlowEdmondsKarp<T> maxFlowEdmondsKarp(graph);
21 maxFlowEdmondsKarp.computeFlow(weights, v, v, flow);
22 MinSTCutMaxFlow<T> minSTCut;
23 minSTCut.call(graph, weights, flow, v, v);
24 });
25
26 it("works on a simple example", [](){
27 Graph graph;
28 node s = graph.newNode();
29 node t = graph.newNode();
30 node v1 = graph.newNode();
31 node v2 = graph.newNode();
32
33 graph.newEdge(s, v1);
34 graph.newEdge(v2, t);
35
36 EdgeArray<T> weights(graph, 4);
37 weights[graph.newEdge(s, v2)] = 1;
38 weights[graph.newEdge(v1, t)] = 2;
39
40 EdgeArray<T> flow;
41 MaxFlowEdmondsKarp<T> mfek(graph);
42 mfek.computeFlow(weights, s, t, flow);
43 MinSTCutMaxFlow<T> minSTCut;
44 minSTCut.call(graph, weights, flow, s, t);
45
46 AssertThat(minSTCut.isInFrontCut(s), Equals(true));
47 AssertThat(minSTCut.isInFrontCut(v1), Equals(true));
48 AssertThat(minSTCut.isInBackCut(t), Equals(true));
49 AssertThat(minSTCut.isInBackCut(v2), Equals(true));
50 });
51
52 it("works on a more complex example", [](){
53 Graph graph;
54 emptyGraph(graph, 8);
55 List<node> nodes;
56 graph.allNodes(nodes);
57 EdgeArray<T> weights(graph);
58 weights[graph.newEdge(*nodes.get(0), *nodes.get(1))] = 16;
59 weights[graph.newEdge(*nodes.get(0), *nodes.get(2))] = 13;
60 weights[graph.newEdge(*nodes.get(1), *nodes.get(2))] = 10;
61 weights[graph.newEdge(*nodes.get(1), *nodes.get(3))] = 12;
62 weights[graph.newEdge(*nodes.get(2), *nodes.get(1))] = 4;
63 weights[graph.newEdge(*nodes.get(2), *nodes.get(4))] = 14;
64 weights[graph.newEdge(*nodes.get(3), *nodes.get(2))] = 9;
65 weights[graph.newEdge(*nodes.get(3), *nodes.get(5))] = 20;
66 weights[graph.newEdge(*nodes.get(4), *nodes.get(3))] = 7;
67 weights[graph.newEdge(*nodes.get(4), *nodes.get(5))] = 4;
68
69 weights[graph.newEdge(*nodes.get(5), *nodes.get(6))] = 100;
70 weights[graph.newEdge(*nodes.get(7), *nodes.get(5))] = 100;
71
72 EdgeArray<T> flow;
73 MaxFlowEdmondsKarp<T> mfek(graph);
74 mfek.computeFlow(weights, *nodes.get(0), *nodes.get(5), flow);
75 MinSTCutMaxFlow<T> minSTCut;
76 minSTCut.call(graph, weights, flow, *nodes.get(0), *nodes.get(5));
77
78 AssertThat(minSTCut.isInFrontCut(*nodes.get(0)), Equals(true));
79 AssertThat(minSTCut.isInFrontCut(*nodes.get(1)), Equals(true));
80 AssertThat(minSTCut.isInFrontCut(*nodes.get(2)), Equals(true));
81 AssertThat(minSTCut.isInFrontCut(*nodes.get(4)), Equals(true));
82
83 AssertThat(minSTCut.isInBackCut(*nodes.get(3)), Equals(true));
84 AssertThat(minSTCut.isInBackCut(*nodes.get(5)), Equals(true));
85
86 AssertThat(minSTCut.isInFrontCut(*nodes.get(6)), Equals(false));
87 AssertThat(minSTCut.isInBackCut(*nodes.get(6)), Equals(false));
88 AssertThat(minSTCut.isOfType(*nodes.get(6), MinSTCutMaxFlow<T>::cutType::NO_CUT), Equals(true));
89 AssertThat(minSTCut.isInBackCut(*nodes.get(7)), Equals(true));
90 AssertThat(minSTCut.isInFrontCut(*nodes.get(7)), Equals(false));
91 });
92
93 describe("detection of complementary back cuts", [] {
94 MinSTCutMaxFlow<T> minSTCut;
95 forEachGraphItWorks({GraphProperty::connected}, [&] (const Graph& graph, const std::string& graphName, const std::set<GraphProperty>& props) {
96 EdgeArray<T> caps(graph);
97
98 for(edge e : graph.edges) {
99 caps[e] = randomNumber(1, 10);
100 }
101
102 for(node v : graph.nodes) if(v != graph.firstNode()) {
103 List<edge> cutEdges;
104 minSTCut.call(graph, caps, graph.firstNode(), v, cutEdges, nullptr);
105
106 bool isComplement = true;
107
108 for(node w : graph.nodes) {
109 isComplement &= minSTCut.isInFrontCut(w) != minSTCut.isInBackCut(w);
110 }
111
112 AssertThat(minSTCut.frontCutIsComplementOfBackCut(), Equals(isComplement));
113 }
114 });
115 });
116});
117}
118
119template<typename T>
120void describeMSTCutSuite(MinSTCutModule<T> &minst, const string &name, const string &type, bool canHandleNonPlanar) {
121describe("MinSTCut"+ name + "<" + type + ">", [&] {
122 it("works on a planar unweighted example", [&]() {
123 Graph graph;
124 node s = graph.newNode();
125 node t = graph.newNode();
126 node v1 = graph.newNode();
127 node v2 = graph.newNode();
128 node v3 = graph.newNode();
129 node v4 = graph.newNode();
130 node v5 = graph.newNode();
131
132 edge e1 = graph.newEdge(s, v1);
133 edge e2 = graph.newEdge(s, v2);
134 edge e_st = graph.newEdge(s, t);
135 graph.newEdge(v2, v4);
136 graph.newEdge(v2, v5);
137 graph.newEdge(v1, v3);
138 graph.newEdge(v1, v4);
139 graph.newEdge(v5, t);
140 graph.newEdge(v4, t);
141 graph.newEdge(v3, t);
142
143 List<edge> edgeList;
144 minst.call(graph, s, t, edgeList, e_st);
145
146 AssertThat(edgeList.size(), Equals(2));
147 AssertThat(edgeList.popFrontRet(), Equals(e2));
148 AssertThat(edgeList.popFrontRet(), Equals(e1));
149 });
150
151 it("works on a planar weighted example", [&]() {
152 Graph graph;
153 node s = graph.newNode();
154 node t = graph.newNode();
155 node v1 = graph.newNode();
156 node v2 = graph.newNode();
157 node v3 = graph.newNode();
158
159 graph.newEdge(s, v1);
160 graph.newEdge(s, v2);
161 graph.newEdge(s, v3);
162 edge e_st = graph.newEdge(s, t);
163
164 EdgeArray<T> weights(graph, 4);
165 edge e1, e2, e3;
166 weights[e1 = graph.newEdge(v3, t)] = 2;
167 weights[e2 = graph.newEdge(v2, t)] = 2;
168 weights[e3 = graph.newEdge(v1, t)] = 2;
169
170 List<edge> edgeList;
171 minst.call(graph, weights, s, t, edgeList, e_st);
172
173 AssertThat(edgeList.size(), Equals(3));
174 AssertThat(edgeList.popFrontRet(), Equals(e1));
175 AssertThat(edgeList.popFrontRet(), Equals(e2));
176 AssertThat(edgeList.popFrontRet(), Equals(e3));
177 });
178 if(canHandleNonPlanar) {
179 it("works on a non-planar weighted example", [&]() {
180 Graph graph;
181 completeGraph(graph, 5);
182
183 EdgeArray<T> weight(graph, 5);
184
185 node s = graph.chooseNode();
186 node t = graph.newNode();
187 edge e = graph.newEdge(s,t);
188 weight[e] = 1;
189 List<edge> edgeList;
190 minst.call(graph, weight, s, t, edgeList);
191
192 AssertThat(((MinSTCutMaxFlow<T>&) minst).isInFrontCut(s), IsTrue());
193 AssertThat(((MinSTCutMaxFlow<T>&) minst).isInBackCut(t), IsTrue());
194
195 AssertThat(edgeList.size(), Equals(1));
196 AssertThat(edgeList.front(), Equals(e));
197 });
198 it("works on a non-planar unweighted example", [&]() {
199 Graph graph;
200 completeGraph(graph, 5);
201
202 List<node> nodes;
203 graph.allNodes(nodes);
204 node s = *nodes.get(0);
205 node t = *nodes.get(1);
206 List<edge> edgeList;
207 minst.call(graph, s, t, edgeList);
208
209 AssertThat(edgeList.size(), Equals(4));
210 });
211 }
212
213});
214}
215
216go_bandit([](){
217 describe("MinSTCut from a flow", []() {
218 describeMSTCutFromMaxFlowSuite<int>("int");
219 describeMSTCutFromMaxFlowSuite<double>("double");
220 });
221 describe("MinSTCut from a graph", []() {
222 MinSTCutMaxFlow<int> mFint(true, new MaxFlowGoldbergTarjan<int>());
223 describeMSTCutSuite<int>(mFint, "MaxFlow(GoldbergTarjan)", "int", true);
224 MinSTCutMaxFlow<double> mFdouble;
225 describeMSTCutSuite<double>(mFdouble, "MaxFlow(EdmondsKarp)", "double", true);
226 MinSTCutDijkstra<int> mDint;
227 describeMSTCutSuite<int>(mDint, "Dijkstra", "int", false);
228 MinSTCutDijkstra<double> mDdouble;
229 describeMSTCutSuite<double>(mDdouble, "Dijkstra", "double", false);
230 MinSTCutBFS<int> mBint;
231 describeMSTCutSuite<int>(mBint, "BFS", "int", false);
232 MinSTCutBFS<double> mBdouble;
233 describeMSTCutSuite<double>(mBdouble, "BFS", "double", false);
234 });
235});
236