# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
MinCostFlowModule.h
Go to the documentation of this file.
1
35#pragma once
36
37#include <ogdf/basic/Graph.h>
40
41namespace ogdf {
42
43
47template<typename TCost>
49public:
52
53 // destruction
54 virtual ~MinCostFlowModule() { }
55
70 virtual bool call(const Graph& G, // directed graph
71 const EdgeArray<int>& lowerBound, // lower bound for flow
72 const EdgeArray<int>& upperBound, // upper bound for flow
73 const EdgeArray<TCost>& cost, // cost of an edge
74 const NodeArray<int>& supply, // supply (if neg. demand) of a node
75 EdgeArray<int>& flow) // computed flow
76 {
77 NodeArray<TCost> dual(G);
78 return call(G, lowerBound, upperBound, cost, supply, flow, dual);
79 }
80
96 virtual bool call(const Graph& G, // directed graph
97 const EdgeArray<int>& lowerBound, // lower bound for flow
98 const EdgeArray<int>& upperBound, // upper bound for flow
99 const EdgeArray<TCost>& cost, // cost of an edge
100 const NodeArray<int>& supply, // supply (if neg. demand) of a node
101 EdgeArray<int>& flow, // computed flow
102 NodeArray<TCost>& dual // computed dual variables
103 ) = 0;
104
105
106 //
107 // static functions
108 //
109
114 static void generateProblem(Graph& G, int n, int m, EdgeArray<int>& lowerBound,
116
117
131 static bool checkProblem(const Graph& G, const EdgeArray<int>& lowerBound,
132 const EdgeArray<int>& upperBound, const NodeArray<int>& supply);
133
134
154 static bool checkComputedFlow(const Graph& G, const EdgeArray<int>& lowerBound,
155 const EdgeArray<int>& upperBound, const EdgeArray<TCost>& cost,
156 const NodeArray<int>& supply, const EdgeArray<int>& flow, TCost& value);
157
176 static bool checkComputedFlow(const Graph& G, const EdgeArray<int>& lowerBound,
177 const EdgeArray<int>& upperBound, const EdgeArray<TCost>& cost,
178 const NodeArray<int>& supply, const EdgeArray<int>& flow) {
179 TCost value;
180 return checkComputedFlow(G, lowerBound, upperBound, cost, supply, flow, value);
181 }
182};
183
184// Implementation
185
186template<typename TCost>
189 ogdf::randomGraph(G, n, m);
190
191 node s = G.firstNode();
192 node t = G.lastNode();
193
194 for (node v : G.nodes) {
195 G.newEdge(s, v);
196 G.newEdge(v, t);
197 }
198
199 for (edge e : G.edges) {
200 lowerBound[e] = 0;
201 upperBound[e] = (e->source() != s) ? ogdf::randomNumber(1, 10) : ogdf::randomNumber(2, 13);
202 cost[e] = static_cast<TCost>(ogdf::randomNumber(0, 100));
203 }
204
205
206 for (node v = G.firstNode(), vl = G.lastNode(); true; v = v->succ(), vl = vl->pred()) {
207 if (v == vl) {
208 supply[v] = 0;
209 break;
210 }
211
212 supply[v] = -(supply[vl] = ogdf::randomNumber(-1, 1));
213
214 if (vl == v->succ()) {
215 break;
216 }
217 }
218}
219
220template<typename TCost>
222 const EdgeArray<int>& upperBound, const NodeArray<int>& supply) {
223 if (!isConnected(G)) {
224 return false;
225 }
226
227 for (edge e : G.edges) {
228 if (lowerBound[e] > upperBound[e]) {
229 return false;
230 }
231 }
232
233 int sum = 0;
234 for (node v : G.nodes) {
235 sum += supply[v];
236 }
237
238 return sum == 0;
239}
240
241template<typename TCost>
243 const EdgeArray<int>& upperBound, const EdgeArray<TCost>& cost,
244 const NodeArray<int>& supply, const EdgeArray<int>& flow, TCost& value) {
245 value = 0;
246
247 for (edge e : G.edges) {
248 if (flow[e] < lowerBound[e] || upperBound[e] < flow[e]) {
249 return false;
250 }
251
252 value += flow[e] * cost[e];
253 }
254
255 for (node v : G.nodes) {
256 int sum = 0;
257
260
261 if (e->isSelfLoop()) {
262 continue;
263 }
264
265 if (e->source() == v) {
266 sum += flow[e];
267 } else {
268 sum -= flow[e];
269 }
270 }
271 if (sum != supply[v]) {
272 return false;
273 }
274 }
275
276 return true;
277}
278
279}
Includes declaration of graph class.
Definition Graph_d.h:79
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
bool isSelfLoop() const
Returns true iff the edge is a self-loop (source node = target node).
Definition Graph_d.h:356
node source() const
Returns the source node of the edge.
Definition Graph_d.h:335
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Interface for min-cost flow algorithms.
static bool checkComputedFlow(const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, const EdgeArray< int > &flow, TCost &value)
checks if a computed flow is a feasible solution to the given problem instance.
virtual bool call(const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, EdgeArray< int > &flow, NodeArray< TCost > &dual)=0
Computes a min-cost flow in the directed graph G.
static void generateProblem(Graph &G, int n, int m, EdgeArray< int > &lowerBound, EdgeArray< int > &upperBound, EdgeArray< TCost > &cost, NodeArray< int > &supply)
Generates an instance of a min-cost flow problem with n nodes and m + n edges.
static bool checkComputedFlow(const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, const EdgeArray< int > &flow)
checks if a computed flow is a feasible solution to the given problem instance.
MinCostFlowModule()
Initializes a min-cost flow module.
static bool checkProblem(const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const NodeArray< int > &supply)
Checks if a given min-cost flow problem instance satisfies the preconditions.
virtual bool call(const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, EdgeArray< int > &flow)
Computes a min-cost flow in the directed graph G.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Declaration of graph generators.
bool isConnected(const Graph &G)
Returns true iff G is connected.
void randomGraph(Graph &G, int n, int m)
Creates a random graph.
int randomNumber(int low, int high)
Returns random integer between low and high (including).