Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

MinCostFlowModule.h
Go to the documentation of this file.
1 
35 #pragma once
36 
37 #include <ogdf/basic/Graph.h>
38 
41 
42 
43 namespace ogdf {
44 
45 
49 template<typename TCost>
51 {
52 public:
55 
56  // destruction
57  virtual ~MinCostFlowModule() { }
58 
73  virtual bool call(
74  const Graph &G, // directed graph
75  const EdgeArray<int> &lowerBound, // lower bound for flow
76  const EdgeArray<int> &upperBound, // upper bound for flow
77  const EdgeArray<TCost> &cost, // cost of an edge
78  const NodeArray<int> &supply, // supply (if neg. demand) of a node
79  EdgeArray<int> &flow) // computed flow
80  {
81  NodeArray<TCost> dual(G);
82  return call(G, lowerBound, upperBound, cost, supply, flow, dual);
83  }
84 
100  virtual bool call(
101  const Graph &G, // directed graph
102  const EdgeArray<int> &lowerBound, // lower bound for flow
103  const EdgeArray<int> &upperBound, // upper bound for flow
104  const EdgeArray<TCost> &cost, // cost of an edge
105  const NodeArray<int> &supply, // supply (if neg. demand) of a node
106  EdgeArray<int> &flow, // computed flow
107  NodeArray<TCost> &dual // computed dual variables
108  ) = 0;
109 
110 
111  //
112  // static functions
113  //
114 
119  static void generateProblem(
120  Graph &G,
121  int n,
122  int m,
123  EdgeArray<int> &lowerBound,
124  EdgeArray<int> &upperBound,
125  EdgeArray<TCost> &cost,
126  NodeArray<int> &supply);
127 
128 
142  static bool checkProblem(
143  const Graph &G,
144  const EdgeArray<int> &lowerBound,
145  const EdgeArray<int> &upperBound,
146  const NodeArray<int> &supply);
147 
148 
149 
169  static bool checkComputedFlow(
170  const Graph &G,
171  const EdgeArray<int> &lowerBound,
172  const EdgeArray<int> &upperBound,
173  const EdgeArray<TCost> &cost,
174  const NodeArray<int> &supply,
175  const EdgeArray<int> &flow,
176  TCost &value);
177 
196  static bool checkComputedFlow(
197  const Graph &G,
198  const EdgeArray<int> &lowerBound,
199  const EdgeArray<int> &upperBound,
200  const EdgeArray<TCost> &cost,
201  const NodeArray<int> &supply,
202  const EdgeArray<int> &flow)
203  {
204  TCost value;
205  return checkComputedFlow(
206  G,lowerBound,upperBound,cost,supply,flow,value);
207  }
208 };
209 
210 // Implementation
211 
212 template<typename TCost>
214  Graph &G,
215  int n,
216  int m,
217  EdgeArray<int> &lowerBound,
218  EdgeArray<int> &upperBound,
219  EdgeArray<TCost> &cost,
220  NodeArray<int> &supply)
221 {
222  ogdf::randomGraph(G,n,m);
223 
224  node s = G.firstNode();
225  node t = G.lastNode();
226 
227  for(node v : G.nodes) {
228  G.newEdge(s,v);
229  G.newEdge(v,t);
230  }
231 
232  for(edge e : G.edges) {
233  lowerBound[e] = 0;
234  upperBound[e] = (e->source() != s) ? ogdf::randomNumber(1,10) : ogdf::randomNumber(2,13);
235  cost[e] = static_cast<TCost>(ogdf::randomNumber(0,100));
236  }
237 
238 
239  for(node v = G.firstNode(), vl = G.lastNode(); true; v = v->succ(), vl = vl->pred()) {
240  if (v == vl) {
241  supply[v] = 0;
242  break;
243  }
244 
245  supply[v] = -(supply[vl] = ogdf::randomNumber(-1,1));
246 
247  if (vl == v->succ())
248  break;
249  }
250 
251 }
252 
253 template<typename TCost>
255  const Graph &G,
256  const EdgeArray<int> &lowerBound,
257  const EdgeArray<int> &upperBound,
258  const NodeArray<int> &supply)
259 {
260  if(!isConnected(G))
261  return false;
262 
263  for(edge e : G.edges) {
264  if (lowerBound[e] > upperBound[e])
265  return false;
266  }
267 
268  int sum = 0;
269  for(node v : G.nodes) {
270  sum += supply[v];
271  }
272 
273  return sum == 0;
274 }
275 
276 
277 template<typename TCost>
279  const Graph &G,
280  const EdgeArray<int> &lowerBound,
281  const EdgeArray<int> &upperBound,
282  const EdgeArray<TCost> &cost,
283  const NodeArray<int> &supply,
284  const EdgeArray<int> &flow,
285  TCost &value)
286 {
287  value = 0;
288 
289  for (edge e : G.edges) {
290  if (flow[e] < lowerBound[e] || upperBound[e] < flow[e]) {
291  return false;
292  }
293 
294  value += flow[e] * cost[e];
295  }
296 
297  for (node v : G.nodes) {
298  int sum = 0;
299 
300  for(adjEntry adj : v->adjEntries) {
301  edge e = adj->theEdge();
302 
303  if (e->isSelfLoop()) {
304  continue;
305  }
306 
307  if (e->source() == v) {
308  sum += flow[e];
309  } else {
310  sum -= flow[e];
311  }
312  }
313  if (sum != supply[v]) {
314  return false;
315  }
316  }
317 
318  return true;
319 }
320 
321 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::randomGraph
void randomGraph(Graph &G, int n, int m)
Creates a random graph.
Graph.h
Includes declaration of graph class.
ogdf::MinCostFlowModule::checkComputedFlow
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.
Definition: MinCostFlowModule.h:278
graph_generators.h
Declaration of graph generators.
ogdf::NodeElement::pred
node pred() const
Returns the predecessor in the list of all nodes.
Definition: Graph_d.h:220
ogdf::isConnected
bool isConnected(const Graph &G)
Returns true iff G is connected.
ogdf::NodeArray< int >
ogdf::EdgeArray< int >
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::MinCostFlowModule::~MinCostFlowModule
virtual ~MinCostFlowModule()
Definition: MinCostFlowModule.h:57
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
ogdf::MinCostFlowModule::checkComputedFlow
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.
Definition: MinCostFlowModule.h:196
ogdf::EdgeElement::isSelfLoop
bool isSelfLoop() const
Returns true iff the edge is a self-loop (source node = target node).
Definition: Graph_d.h:344
ogdf::MinCostFlowModule
Interface for min-cost flow algorithms.
Definition: MinCostFlowModule.h:50
ogdf::NodeElement::adjEntries
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition: Graph_d.h:200
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::MinCostFlowModule::MinCostFlowModule
MinCostFlowModule()
Initializes a min-cost flow module.
Definition: MinCostFlowModule.h:54
ogdf::MinCostFlowModule::checkProblem
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.
Definition: MinCostFlowModule.h:254
ogdf::Math::sum
Container::value_type sum(const Container &values)
Returns the sum of an iterable container of given values.
Definition: Math.h:245
ogdf::NodeElement::succ
node succ() const
Returns the successor in the list of all nodes.
Definition: Graph_d.h:218
ogdf::MinCostFlowModule::call
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.
Definition: MinCostFlowModule.h:73
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::randomNumber
int randomNumber(int low, int high)
Returns random integer between low and high (including).
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::MinCostFlowModule::generateProblem
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.
Definition: MinCostFlowModule.h:213
simple_graph_alg.h
Declaration of simple graph algorithms.