Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MaxFlowGoldbergTarjan.h
Go to the documentation of this file.
1
33#pragma once
34
36
37//#define OGDF_GT_USE_GAP_RELABEL_HEURISTIC
38#define OGDF_GT_USE_MAX_ACTIVE_LABEL
39#ifdef OGDF_GT_USE_GAP_RELABEL_HEURISTIC
40//#define OGDF_GT_GRH_STEPS 1 // gap relabel frequency: call gapRelabel() after OGDF_GT_GRH_STEPS relabel() operations (1 == off)
41#endif
42#define OGDF_GT_USE_PUSH_RELABEL_SECOND_STAGE
43
44// world666 is much better without OGDF_GT_USE_PUSH_RELABEL_SECOND_STAGE
45
46namespace ogdf {
47
49
52template<typename TCap>
55 NodeArray<TCap> m_ex; // ex_f(v) values will be saved here to save runtime
56#ifdef OGDF_GT_USE_MAX_ACTIVE_LABEL
57 NodeArray<ListIterator<node>> m_activeLabelListPosition; // holds the iterator of every active node in the corresp. list of m_labeList
58 Array<List<node>> m_activeLabelList; // array indexed by label, contains list of active nodes with that label
59 int m_maxLabel = 0; // the maximum label among all active nodes
60#endif
61#ifdef OGDF_GT_USE_GAP_RELABEL_HEURISTIC
62 NodeArray<ListIterator<node>> m_labelListPosition; // holds the iterator of every node in the corresp. list of m_labeList
63 Array<List<node>> m_labelList; // array indexed by label, contains list of nodes with that label
64#endif
65
68
69 inline TCap getCap(const edge e) const {
70 return e->target() == *this->m_s ? 0 : (*this->m_cap)[e];
71 }
72
73 inline bool isResidualEdge(const adjEntry adj) const {
74 const edge e = adj->theEdge();
75 if (adj->theNode() == e->source()) {
76 return this->m_et->less((*this->m_flow)[e], getCap(e));
77 }
78 return this->m_et->greater((*this->m_flow)[e], (TCap)0);
79 }
80
81 inline bool isAdmissible(const adjEntry adj) const {
82 OGDF_ASSERT(adj);
83 return isResidualEdge(adj) && m_label[adj->theNode()] == m_label[adj->twinNode()] + 1;
84 }
85
86 inline bool isActive(const node v) const {
87 OGDF_ASSERT((v != *this->m_s && v != *this->m_t)
88 || (m_label[*this->m_s] == this->m_G->numberOfNodes() && m_label[*this->m_t] == 0));
89 return this->m_et->greater(m_ex[v], (TCap)0) && this->m_G->numberOfNodes() > m_label[v]
90 && m_label[v] > 0;
91 }
92
93#ifdef OGDF_GT_USE_MAX_ACTIVE_LABEL
94 inline void setActive(const node v) {
95 const int label = m_label[v];
96 OGDF_ASSERT(0 < label);
99 m_activeLabelListPosition[v] = m_activeLabelList[label].pushBack(v);
100 if (label > m_maxLabel) {
101 m_maxLabel = label;
102 }
103 }
104
105 inline void findNewMaxLabel() {
106 while (m_maxLabel > 0 && m_activeLabelList[m_maxLabel].empty()) {
107 --m_maxLabel;
108 }
109 }
110
111 inline void setInactive(const node v) {
114 m_activeLabelListPosition[v] = nullptr;
116 }
117#endif
118
119 // sets label of v, maintaining m_labelList (moves node v to the correct list in the array)
120 inline void setLabel(const node v, int label) {
121#ifdef OGDF_GT_USE_GAP_RELABEL_HEURISTIC
122 if (m_labelListPosition[v].valid()) {
123 m_labelList[m_label[v]].del(
124 m_labelListPosition[v]); // delete node from old list using noted position
125 }
127 m_labelList[label].pushBack(v); // push node to new list and update iterator
128#endif
129#ifdef OGDF_GT_USE_MAX_ACTIVE_LABEL
130 if (m_activeLabelListPosition[v].valid()) {
131 OGDF_ASSERT(0 < m_label[v]);
132 OGDF_ASSERT(m_label[v] < this->m_G->numberOfNodes());
133 setInactive(v);
134 }
135 m_label[v] = label; // update label
136 if (v != *this->m_s && v != *this->m_t && isActive(v)) {
137 setActive(v);
138 }
139#else
140 m_label[v] = label; // update label
141#endif
142 }
143
144#ifdef OGDF_GT_USE_GAP_RELABEL_HEURISTIC
145 void gapRelabel() {
146# ifdef OGDF_GT_USE_MAX_ACTIVE_LABEL
147 // XXX: this is a test but it seems to work and it seems to be fast!
148 const int n = m_maxLabel + 1;
149# else
150 const int n = this->m_G->numberOfNodes();
151# endif
152 for (int i = 1; i < n - 1; ++i) {
153 if (m_labelList[i].empty()) {
154 for (int j = i + 1; j < n; ++j) {
155 while (!m_labelList[j].empty()) {
156 setLabel(m_labelList[j].front(), this->m_G->numberOfNodes());
157 }
158 }
159 break;
160 }
161 }
162 }
163#endif
164
165 void push(const adjEntry adj) {
166 const edge e = adj->theEdge();
167 const node v = adj->theNode();
168 if (v == e->source()) {
169 const TCap value = min(m_ex[v], getCap(e) - (*this->m_flow)[e]);
170 OGDF_ASSERT(this->m_et->geq(value, (TCap)0));
171 (*this->m_flow)[e] += value;
172 m_ex[v] -= value;
173 m_ex[adj->twinNode()] += value;
174 } else {
175 const TCap value = min(m_ex[v], (*this->m_flow)[adj]);
176 OGDF_ASSERT(this->m_et->geq(value, (TCap)0));
177 (*this->m_flow)[adj] -= value;
178 m_ex[v] -= value;
179 m_ex[adj->twinNode()] += value;
180 }
181 }
182
184 // breadth-first search to relabel nodes with their respective distance to the sink in the residual graph
185 const int n = this->m_G->numberOfNodes();
186 NodeArray<int> dist(*this->m_G, n); // distance array
187 List<node> queue; // reachable, not processed nodes
188 dist[*this->m_t] = 0;
189 queue.pushBack(*this->m_t);
190 while (!queue.empty()) { // is there a node to check?
191 node w = queue.popFrontRet();
192 for (adjEntry adj : w->adjEntries) {
193 node x = adj->twinNode();
194 if (isResidualEdge(adj->twin()) && dist[x] == n) { // not already seen
195 dist[x] = dist[w] + 1; // set distance of node to sink
196 queue.pushBack(x);
197 }
198 }
199 }
200 // set distance of unreachable nodes to "number of nodes" thus making them inactive
201 for (node w : this->m_G->nodes) {
202 setLabel(w, dist[w]);
203 }
204 }
205
206 void relabel(const node v) {
207 int minLabel = this->m_G->numberOfNodes() - 1;
208 for (adjEntry adj : v->adjEntries) {
209 if (isResidualEdge(adj)) {
210 const int label = m_label[adj->twinNode()];
211 if (label < minLabel) {
212 minLabel = label;
213 }
214 }
215 }
216 if (minLabel + 1 != m_label[v]) { // == can happen after global relabel
217 setLabel(v, minLabel + 1);
218 }
219 }
220
221 void relabelStage2(const node v) {
222 int minLabel = this->m_G->numberOfNodes() - 1;
223 for (adjEntry adj : v->adjEntries) {
224 if (isResidualEdge(adj)) {
225 const int label = m_label[adj->twinNode()];
226 if (label < minLabel) {
227 minLabel = label;
228 }
229 }
230 }
231 OGDF_ASSERT(minLabel + 1 != m_label[v]);
232 m_label[v] = minLabel + 1;
233 }
234
235public:
236 // first stage: push excess towards sink
237 TCap computeValue(const EdgeArray<TCap>& cap, const node& s, const node& t) {
238 // TODO: init this stuff in the module?
239 this->m_s = &s;
240 this->m_t = &t;
241 this->m_cap = &cap;
242 this->m_flow->init(*this->m_G, (TCap)0);
244
245 m_label.init(*this->m_G);
246 m_ex.init(*this->m_G, 0);
247#ifdef OGDF_GT_USE_MAX_ACTIVE_LABEL
248 m_activeLabelListPosition.init(*this->m_G, nullptr);
249 m_activeLabelList.init(1, this->m_G->numberOfNodes() - 1);
250 m_maxLabel = 0;
251#endif
252#ifdef OGDF_GT_USE_GAP_RELABEL_HEURISTIC
253 m_labelListPosition.init(*this->m_G, nullptr);
254 m_labelList.init(this->m_G->numberOfNodes() + 1);
255#endif
256 m_cutNodes.clear();
257
258 // initialize residual graph for first preflow
259 for (edge e : this->m_G->edges) {
260 if (e->source() == *this->m_s && e->target() != *this->m_s) { // ignore loops
261 (*this->m_flow)[e] = getCap(e);
262 m_ex[e->target()] += getCap(e); // "+" needed for the case of multigraphs
263 }
264 }
265
266 if (*this->m_t == *this->m_s) {
267 return (TCap)0;
268 }
269
271 for (node v = this->m_G->firstNode(); v; v = v->succ()) {
272 curr[v] = v->firstAdj();
273 }
274
275 globalRelabel(); // initialize distance labels
276
277 int relCount = 0; // counts the relabel operations for the global relabeling heuristic
278#ifdef OGDF_GT_USE_MAX_ACTIVE_LABEL
279 while (m_maxLabel != 0) {
281 const node v = m_activeLabelList[m_maxLabel].front();
284#else
285 List<node> active;
286 for (adjEntry adj : (*this->m_s)->adjEntries) {
287 node w = adj->theEdge()->target();
288 if (w != *this->m_s) {
289 active.pushBack(w);
290 }
291 }
292 while (!active.empty()) {
293 const node v = active.front();
294#endif
295 adjEntry& adj = curr[v];
296 if (v == *this->m_s || v == *this->m_t || !isActive(v)) {
297 // source, sink or not active: remove activity status
298#ifdef OGDF_GT_USE_MAX_ACTIVE_LABEL
299 setInactive(v);
300#else
301 active.popFront();
302#endif
303 } else {
304 while (this->m_et->greater(m_ex[v], (TCap)0)) {
305 if (isAdmissible(adj)) {
306 // push and adjacent node becomes active
307#ifdef OGDF_GT_USE_MAX_ACTIVE_LABEL
308 const node w = adj->twinNode();
309 if (w != *this->m_s && w != *this->m_t && !isActive(w)) {
310 // w will become active after push
311 setActive(w);
312 }
313 push(adj);
314 if (v != *this->m_s && !isActive(v)) {
315 setInactive(v);
316 }
317#else
318 push(adj);
319 active.pushBack(adj->twinNode());
320#endif
321 } else {
322 if (adj != v->lastAdj()) {
323 adj = adj->succ();
324 } else { // end of adjacency list
325 adj = v->firstAdj();
326 relabel(v);
327 ++relCount;
328#ifdef OGDF_GT_USE_GAP_RELABEL_HEURISTIC
329 // only gapRelabel if we do not do a globalRelabel directly afterwards
330 if (relCount != this->m_G->numberOfNodes()
331# if (OGDF_GT_GRH_STEPS > 1)
332 && relCount % OGDF_GT_GRH_STEPS
333 == 0 // obey frequency of gap relabel heuristic
334# endif
335 ) {
336 gapRelabel();
337 }
338#endif
339 break;
340 }
341 }
342 }
343 if (relCount == this->m_G->numberOfNodes()) {
344 relCount = 0;
346 }
347 }
348 }
349
350 TCap result = 0;
351 for (adjEntry adj : (*this->m_t)->adjEntries) {
352 edge e = adj->theEdge();
353 if (e->target() == *this->m_t) {
354 result += (*this->m_flow)[e];
355 } else {
356 result -= (*this->m_flow)[e];
357 }
358 }
359 return result;
360 }
361
362 // second stage: push excess that has not reached the sink back towards source
364 List<node> active;
365#ifdef OGDF_GT_USE_PUSH_RELABEL_SECOND_STAGE
367 for (node v = this->m_G->firstNode(); v; v = v->succ()) {
368 curr[v] = v->firstAdj();
369 m_label[v] = 1;
370 if (this->m_et->greater(m_ex[v], (TCap)0) && v != *this->m_s && v != *this->m_t) {
371 active.pushBack(v);
372 }
373 }
374 if (active.empty()) {
375 return;
376 }
377
378 m_label[*this->m_s] = 0;
379 while (!active.empty()) {
380 node v = active.front();
381 if (v == *this->m_s || v == *this->m_t || !isActive(v)) {
382 active.popFront();
383 } else {
384 adjEntry& adj = curr[v];
385 if (isAdmissible(adj)) {
386 push(adj);
387 active.pushBack(adj->twinNode());
388 } else {
389 if (adj == v->lastAdj()) {
390 // no admissible outgoing edge found -> relabel node!
391 relabelStage2(v);
392 adj = v->firstAdj();
393# if 0
394 // node is still active but move it to the end of the queue
395 // (don't know if this is really necessary)
396 active.popFront();
397 active.pushBack(v);
398# endif
399 } else {
400 adj = adj->succ();
401 }
402 }
403 }
404 }
405#else // USE_PUSH_RELABEL_SECOND_STAGE
406 m_ex[*this->m_s] = m_ex[*this->m_t] = 0;
407 for (node v = this->m_G->firstNode(); v; v = v->succ()) {
408 if (this->m_et->greater(m_ex[v], (TCap)0)) {
409 active.pushBack(v);
410 }
411 }
412 while (!active.empty()) {
413 const node v = active.popFrontRet();
414 if (this->m_et->greater(m_ex[v], (TCap)0) && v != *this->m_s && v != *this->m_t) {
415 for (adjEntry adj = v->firstAdj(); adj; adj = adj->succ()) {
416 const edge e = adj->theEdge();
417 const node u = e->source();
418 if (u != v) { // e is incoming edge
419 if (this->m_et->greater(m_ex[v], (TCap)0) && isResidualEdge(adj)) {
420 push(adj);
421 if (u != *this->m_s) {
422 active.pushFront(u);
423 }
424 }
425 }
426 }
427 }
428 }
429#endif // USE_PUSH_RELABEL_SECOND_STAGE
430 }
431
437};
438
439}
Interface for Max Flow Algorithms.
Class for adjacency list elements.
Definition Graph_d.h:79
adjEntry succ() const
Returns the successor in the adjacency list.
Definition Graph_d.h:155
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition Graph_d.h:97
node twinNode() const
Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
Definition Graph_d.h:112
node theNode() const
Returns the node whose adjacency list contains this element.
Definition Graph_d.h:103
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
void init()
Reinitializes the array to an array with empty index set.
Definition Array.h:367
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
void init()
Reinitializes the array. Associates the array with no graph.
Definition EdgeArray.h:292
Class for the representation of edges.
Definition Graph_d.h:300
node target() const
Returns the target node of the edge.
Definition Graph_d.h:338
node source() const
Returns the source node of the edge.
Definition Graph_d.h:335
std::enable_if< std::is_integral< T >::value, bool >::type geq(const T &x, const T &y) const
Compare if x is GEQ to y for integral types.
std::enable_if< std::is_integral< T >::value, bool >::type less(const T &x, const T &y) const
Compare if x is LESS than y for integral types.
Definition EpsilonTest.h:57
std::enable_if< std::is_integral< T >::value, bool >::type greater(const T &x, const T &y) const
Compare if x is GREATER than y for integral types.
int numberOfNodes() const
Returns the number of nodes in the graph.
Definition Graph_d.h:622
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition Graph_d.h:589
node firstNode() const
Returns the first node in the list of all nodes.
Definition Graph_d.h:646
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition Graph_d.h:592
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
void popFront()
Removes the first element from the list.
Definition List.h:1569
void clear()
Removes all elements from the list.
Definition List.h:1610
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1531
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
Definition List.h:1518
E popFrontRet()
Removes the first element from the list and returns it.
Definition List.h:1575
const_reference front() const
Returns a const reference to the first element.
Definition List.h:289
bool empty() const
Returns true iff the list is empty.
Definition List.h:270
Computes a max flow via Preflow-Push (global relabeling and gap relabeling heuristic).
Array< List< node > > m_activeLabelList
bool isActive(const node v) const
void push(const adjEntry adj)
void setLabel(const node v, int label)
bool isAdmissible(const adjEntry adj) const
TCap computeValue(const EdgeArray< TCap > &cap, const node &s, const node &t)
Compute only the value of the flow.
NodeArray< ListIterator< node > > m_activeLabelListPosition
bool isResidualEdge(const adjEntry adj) const
TCap getCap(const edge e) const
void computeFlowAfterValue()
Compute the flow itself after the flow value is already computed. Only used in algorithms with 2 phas...
const node * m_t
Pointer to the sink node.
virtual void init(const Graph &graph, EdgeArray< TCap > *flow=nullptr)
Initialize the problem with a graph and optional flow array. If no flow array is given,...
EdgeArray< TCap > * m_flow
Pointer to (extern) flow array.
void useEpsilonTest(const double &eps)
Change the used EpsilonTest from StandardEpsilonTest to a user given EpsilonTest.
bool isFeasibleInstance() const
Return whether the instance is feasible, i.e. the capacities are non-negative.
const Graph * m_G
Pointer to the given graph.
const node * m_s
Pointer to the source node.
const EdgeArray< TCap > * m_cap
Pointer to the given capacity array.
MaxFlowModule()
Empty Constructor.
TCap computeFlow(EdgeArray< TCap > &cap, node &s, node &t, EdgeArray< TCap > &flow)
Only a shortcut for computeValue and computeFlowAfterValue.
EpsilonTest * m_et
Pointer to the used EpsilonTest.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
void init()
Reinitializes the array. Associates the array with no graph.
Definition NodeArray.h:266
Class for the representation of nodes.
Definition Graph_d.h:177
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition Graph_d.h:208
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition Graph_d.h:223
adjEntry lastAdj() const
Returns the last entry in the adjacency list.
Definition Graph_d.h:226
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.