Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MaxFlowSTPlanarItaiShiloach.h
Go to the documentation of this file.
1
35#pragma once
36
40
41#include <limits>
42
43namespace ogdf {
44
46
49template<typename TCap>
51private:
57 TCap unshiftedPriority(edge e) { return m_prioritizedEdges->priority(e) - TCap(1); }
58
63 TCap unshiftedTopPriority() { return m_prioritizedEdges->topPriority() - TCap(1); }
64
71 OGDF_ASSERT(priority < std::numeric_limits<TCap>::max());
72 return priority + TCap(1);
73 }
74
78 enum class NodeType { New, Path, Done };
79
86
88
91
94
97
100
103
106
107public:
112
123 const node& target) {
124 OGDF_ASSERT(source != target);
125 OGDF_ASSERT(isSTPlanar(*this->m_G, source, target));
126
127 // initialize auxiliary structures
128
129 m_partialFlow = (TCap)0;
130
131 this->m_s = &source;
132 this->m_t = &target;
133 this->m_cap = &originalCapacities;
134 this->m_flow->init(*this->m_G, (TCap)0);
136
137 // establish s-t-planarity
138 ConstCombinatorialEmbedding embedding(*this->m_G);
139#ifdef OGDF_DEBUG
140 embedding.consistencyCheck();
141#endif
143 m_commonFaceAdj = embedding.findCommonFace(*this->m_s, *this->m_t, secondCommonAdj);
144 OGDF_ASSERT(m_commonFaceAdj != nullptr);
145
146 m_pred.init(*this->m_G, nullptr);
147 m_status.init(*this->m_G, NodeType::New);
148 m_visited.init(*this->m_G, false);
149 m_edgeCounter.init(*this->m_G, 0);
150 m_status[*this->m_s] = NodeType::Path;
151 m_status[*this->m_t] = NodeType::Path;
152
153 delete m_prioritizedEdges;
154 m_prioritizedEdges = new PrioritizedMapQueue<edge, TCap>(*this->m_G);
155
156 // saturate all paths
157
158 edge lastSaturated = nullptr;
160 lastSaturated = m_prioritizedEdges->topElement();
162 m_prioritizedEdges->pop();
163
164 (*this->m_flow)[lastSaturated] = (*this->m_cap)[lastSaturated];
165
166 m_pred[lastSaturated->target()] = nullptr;
169 }
170
171 return m_partialFlow;
172 }
173
182 // the flow value is only computed if the edge is deleted
183 while (!m_prioritizedEdges->empty()) {
184 edge e = m_prioritizedEdges->topElement();
185 dropEdge(e);
186 }
187 }
188
189 // use methods from super class
195
196private:
203 node v;
205
206 if (saturatedEdge == nullptr) {
207 v = *this->m_s;
208 initialAdj = m_commonFaceAdj;
209 } else {
210 OGDF_ASSERT(!saturatedEdge->isSelfLoop());
211 OGDF_ASSERT(saturatedEdge->target() != *this->m_s);
212 v = saturatedEdge->source();
213 initialAdj = saturatedEdge->adjSource()->cyclicSucc();
214 }
215
216 OGDF_ASSERT(v != *this->m_t);
217
218 for (adjEntry adj = initialAdj; m_edgeCounter[v] < v->degree(); adj = adj->cyclicSucc()) {
219 m_edgeCounter[v]++;
220 edge e = adj->theEdge();
221
222 bool visited = m_visited[e];
223 m_visited[e] = true;
224
225 if (!visited && e->target() != v && m_status[e->target()] != NodeType::Done) {
228
230 // extend the path
231 appendEdge(e);
232 adj = e->adjTarget();
233 v = e->target();
234 } else if (pathType == EdgePathType::TargetPath) {
235 // merge path
236 node w = e->target();
237
238 // remove tangling target path
239 edge f;
240 while (m_pred[w] != nullptr) {
241 f = m_pred[w];
242 w = f->source();
243 dropEdge(f);
244 }
245
247 appendEdge(e);
248
249 return true;
250 } else {
251 // remove source path cycle
253 node w = e->target();
254
256 while (e->source() != w) {
257 formerSource = e->source();
258 if (e->target() != w) {
259 dropEdge(e);
260 }
262 }
263
264 dropEdge(e);
265 adj = e->adjSource();
266 v = e->source();
267 }
268 }
269 }
270
271 // v is a deadend
272 if (v == *this->m_s) {
273 return false;
274 } else {
275 edge e = m_pred[v];
276 dropEdge(e);
277 return findUppermostPath(e);
278 }
279 }
280
286 void appendEdge(const edge e) {
287 node v = e->target();
288 OGDF_ASSERT(m_pred[v] == nullptr);
289
290 // update path predecessor
291 m_pred[v] = e;
293
294 // insert into priority queue while
295 // taking into account the partial flow
296 TCap value = m_partialFlow + (*this->m_cap)[e];
297 m_prioritizedEdges->push(e, shiftPriority(value));
298 }
299
306 void dropEdge(const edge e) {
307 node v = e->target();
308 OGDF_ASSERT(m_pred[v] == e);
310
311 // update path predecessor
312 m_pred[v] = nullptr;
313 m_status[v] = v == *this->m_t ? NodeType::Path : NodeType::Done;
314
315 // remove edge from priority queue
317 m_prioritizedEdges->decrease(e, std::numeric_limits<TCap>::min());
318#ifdef OGDF_DEBUG
319 edge f = m_prioritizedEdges->topElement();
320#endif
321 m_prioritizedEdges->pop();
322
323 // determine the flow on this edge
324 (*this->m_flow)[e] = m_partialFlow - (modCap - (*this->m_cap)[e]);
325
326 OGDF_ASSERT(e == f);
327 }
328
336 node v = e->source();
337 node w = e->target();
338
339 EdgePathType result =
341
342 while (result == EdgePathType::Unknown) {
343 if (v == e->target() || w == *this->m_s) {
345 } else if (m_pred[v] == nullptr || m_pred[w] == nullptr) {
347 } else if (m_pred[w]->source() == *this->m_s) {
349 } else {
350 OGDF_ASSERT(w != m_pred[w]->source());
351 OGDF_ASSERT(v != m_pred[v]->source());
352
353 w = m_pred[w]->source();
354 v = m_pred[v]->source();
355 }
356 }
357
358 return result;
359 }
360};
361
362}
Declaration of CombinatorialEmbedding and face.
Interface for Max Flow Algorithms.
Priority queue interface wrapping various heaps.
Class for adjacency list elements.
Definition Graph_d.h:79
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition Graph_d.h:97
Combinatorial embeddings of planar graphs.
adjEntry findCommonFace(const node v, const node w, bool left=true) const
Identifies a common face of two nodes and returns the respective adjacency entry.
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
adjEntry adjSource() const
Returns the corresponding adjacancy entry at source node.
Definition Graph_d.h:344
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition Graph_d.h:347
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
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.
Computes a max flow in s-t-planar network via uppermost paths.
void dropEdge(const edge e)
Removes a single edge from the current path.
TCap unshiftedPriority(edge e)
To work with unsigned, we need a priority shifting of the elements in the priority queue.
NodeType
Each node has a certain type depending on its participation in any path.
TCap computeValue(const EdgeArray< TCap > &originalCapacities, const node &source, const node &target)
Computes the maximal flow from source to sink.
EdgeArray< bool > m_visited
Whether each edge has was visited.
~MaxFlowSTPlanarItaiShiloach()
Free allocated ressources.
TCap m_partialFlow
The flow reached thus far (monotonically increasing).
void computeFlowAfterValue()
Computes the actual flow on each edge.
EdgePathType getPathType(const edge e) const
Performs an alternating backtracking from source and target to determine whether the new node is part...
NodeArray< edge > m_pred
The predecessor of each node in the currently uppermost path.
TCap unshiftedTopPriority()
see unshiftedPriority
PrioritizedMapQueue< edge, TCap > * m_prioritizedEdges
A priority queue for storing all edges currently in a path.
EdgePathType
Each edge may be part of the source or target path.
NodeArray< int > m_edgeCounter
The number of edges visited from each node.
NodeArray< NodeType > m_status
The status of each node.
bool findUppermostPath(const edge saturatedEdge)
Establishes the next uppermost path.
void appendEdge(const edge e)
Appends an edge to the current path.
TCap shiftPriority(TCap priority)
see unshiftedPriority
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
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition Graph_d.h:220
Prioritized queue interface wrapper for heaps.
bool isSTPlanar(const Graph &graph, const node s, const node t)
Returns whether G is s-t-planar (i.e.
#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.