Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

MaxFlowSTPlanarItaiShiloach.h
Go to the documentation of this file.
1 
35 #pragma once
36 
37 #include <limits>
41 
42 namespace ogdf {
43 
45 
48 template<typename TCap>
50 {
51 private:
52 
59  return m_prioritizedEdges->priority(e) - TCap(1);
60  }
61 
67  return m_prioritizedEdges->topPriority() - TCap(1);
68  }
69 
75  TCap shiftPriority(TCap priority) {
76  OGDF_ASSERT(priority < std::numeric_limits<TCap>::max());
77  return priority + TCap(1);
78  }
79 
83  enum class NodeType {
84  New,
85  Path,
86  Done
87  };
88 
94  enum class EdgePathType {
95  NoPath,
96  SourcePath,
97  TargetPath,
98  Unknown
99  };
100 
102 
105 
108 
111 
114 
117 
120 
121 public:
126  delete m_prioritizedEdges;
127  }
128 
138  TCap computeValue(const EdgeArray<TCap> &originalCapacities, const node &source, const node &target)
139  {
140  OGDF_ASSERT(source != target);
141  OGDF_ASSERT(isSTPlanar(*this->m_G, source, target));
142 
143  // initialize auxiliary structures
144 
145  m_partialFlow = (TCap) 0;
146 
147  this->m_s = &source;
148  this->m_t = &target;
149  this->m_cap = &originalCapacities;
150  this->m_flow->init(*this->m_G, (TCap) 0);
152 
153  // establish s-t-planarity
154  ConstCombinatorialEmbedding embedding(*this->m_G);
155 #ifdef OGDF_DEBUG
156  embedding.consistencyCheck();
157 #endif
158  adjEntry secondCommonAdj;
159  m_commonFaceAdj = embedding.findCommonFace(*this->m_s, *this->m_t, secondCommonAdj);
160  OGDF_ASSERT(m_commonFaceAdj != nullptr);
161 
162  m_pred.init(*this->m_G, nullptr);
163  m_status.init(*this->m_G, NodeType::New);
164  m_visited.init(*this->m_G, false);
165  m_edgeCounter.init(*this->m_G, 0);
166  m_status[*this->m_s] = NodeType::Path;
167  m_status[*this->m_t] = NodeType::Path;
168 
169  delete m_prioritizedEdges;
170  m_prioritizedEdges = new PrioritizedMapQueue<edge, TCap>(*this->m_G);
171 
172  // saturate all paths
173 
174  edge lastSaturated = nullptr;
175  while(findUppermostPath(lastSaturated)) {
176 
177  lastSaturated = m_prioritizedEdges->topElement();
179  m_prioritizedEdges->pop();
180 
181  (*this->m_flow)[lastSaturated] = (*this->m_cap)[lastSaturated];
182 
183  m_pred[lastSaturated->target()] = nullptr;
184  OGDF_ASSERT(m_status[lastSaturated->target()] == NodeType::Path);
185  OGDF_ASSERT(m_status[lastSaturated->source()] == NodeType::Path);
186  }
187 
188  return m_partialFlow;
189  }
190 
199  {
200  // the flow value is only computed if the edge is deleted
201  while (!m_prioritizedEdges->empty()) {
202  edge e = m_prioritizedEdges->topElement();
203  dropEdge(e);
204  }
205  }
206 
207  // use methods from super class
213 
214 private:
215 
221  bool findUppermostPath(const edge saturatedEdge)
222  {
223  node v;
224  adjEntry initialAdj;
225 
226  if (saturatedEdge == nullptr) {
227  v = *this->m_s;
228  initialAdj = m_commonFaceAdj;
229  } else {
230  OGDF_ASSERT(!saturatedEdge->isSelfLoop());
231  OGDF_ASSERT(saturatedEdge->target() != *this->m_s);
232  v = saturatedEdge->source();
233  initialAdj = saturatedEdge->adjSource()->cyclicSucc();
234  }
235 
236  OGDF_ASSERT(v != *this->m_t);
237 
238  for(adjEntry adj = initialAdj;
239  m_edgeCounter[v] < v->degree();
240  adj = adj->cyclicSucc())
241  {
242  m_edgeCounter[v]++;
243  edge e = adj->theEdge();
244 
245  bool visited = m_visited[e];
246  m_visited[e] = true;
247 
248  if(!visited
249  && e->target() != v
250  && m_status[e->target()] != NodeType::Done)
251  {
252  EdgePathType pathType = getPathType(e);
253  OGDF_ASSERT(pathType != EdgePathType::Unknown);
254 
255  if(pathType == EdgePathType::NoPath) {
256  // extend the path
257  appendEdge(e);
258  adj = e->adjTarget();
259  v = e->target();
260  } else if(pathType == EdgePathType::TargetPath) {
261  // merge path
262  node w = e->target();
263 
264  // remove tangling target path
265  edge f;
266  while(m_pred[w] != nullptr) {
267  f = m_pred[w];
268  w = f->source();
269  dropEdge(f);
270  }
271 
273  appendEdge(e);
274 
275  return true;
276  } else {
277  // remove source path cycle
279  node w = e->target();
280 
281  node formerSource;
282  while(e->source() != w) {
283  formerSource = e->source();
284  if(e->target() != w) {
285  dropEdge(e);
286  }
287  e = m_pred[formerSource]->adjSource()->theEdge();
288  }
289 
290  dropEdge(e);
291  adj = e->adjSource();
292  v = e->source();
293  }
294  }
295  }
296 
297  // v is a deadend
298  if(v == *this->m_s) {
299  return false;
300  } else {
301  edge e = m_pred[v];
302  dropEdge(e);
303  return findUppermostPath(e);
304  }
305  }
306 
312  void appendEdge(const edge e) {
313  node v = e->target();
314  OGDF_ASSERT(m_pred[v] == nullptr);
315 
316  // update path predecessor
317  m_pred[v] = e;
319 
320  // insert into priority queue while
321  // taking into account the partial flow
322  TCap value = m_partialFlow + (*this->m_cap)[e];
323  m_prioritizedEdges->push(e, shiftPriority(value));
324  }
325 
332  void dropEdge(const edge e) {
333  node v = e->target();
334  OGDF_ASSERT(m_pred[v] == e);
336 
337  // update path predecessor
338  m_pred[v] = nullptr;
339  m_status[v] = v == *this->m_t ? NodeType::Path : NodeType::Done;
340 
341  // remove edge from priority queue
342  TCap modCap = unshiftedPriority(e);
343  m_prioritizedEdges->decrease(e, std::numeric_limits<TCap>::min());
344 #ifdef OGDF_DEBUG
345  edge f = m_prioritizedEdges->topElement();
346 #endif
347  m_prioritizedEdges->pop();
348 
349  // determine the flow on this edge
350  (*this->m_flow)[e] = m_partialFlow - (modCap - (*this->m_cap)[e]);
351 
352  OGDF_ASSERT(e == f);
353  }
354 
361  EdgePathType getPathType(const edge e) const {
362  node v = e->source();
363  node w = e->target();
364 
366 
367  while(result == EdgePathType::Unknown) {
368  if(v == e->target() || w == *this->m_s) {
369  result = EdgePathType::SourcePath;
370  } else if(m_pred[v] == nullptr || m_pred[w] == nullptr) {
371  result = EdgePathType::TargetPath;
372  } else if(m_pred[w]->source() == *this->m_s) {
373  result = EdgePathType::SourcePath;
374  } else {
375  OGDF_ASSERT(w != m_pred[w]->source());
376  OGDF_ASSERT(v != m_pred[v]->source());
377 
378  w = m_pred[w]->source();
379  v = m_pred[v]->source();
380  }
381  }
382 
383  return result;
384  }
385 };
386 
387 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::EdgeArray::init
void init()
Reinitializes the array. Associates the array with no graph.
Definition: EdgeArray.h:283
ogdf::MaxFlowModule< TCap >::isFeasibleInstance
bool isFeasibleInstance() const
Return whether the instance is feasible, i.e. the capacities are non-negative.
Definition: MaxFlowModule.h:157
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
MaxFlowModule.h
Interface for Max Flow Algorithms.
PriorityQueue.h
Priority queue interface wrapping various heaps.
ogdf::ConstCombinatorialEmbedding::findCommonFace
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.
Definition: CombinatorialEmbedding.h:369
ogdf::MaxFlowSTPlanarItaiShiloach::m_prioritizedEdges
PrioritizedMapQueue< edge, TCap > * m_prioritizedEdges
A priority queue for storing all edges currently in a path.
Definition: MaxFlowSTPlanarItaiShiloach.h:116
ogdf::MaxFlowModule< TCap >::m_t
const node * m_t
Pointer to the sink node.
Definition: MaxFlowModule.h:48
ogdf::MaxFlowSTPlanarItaiShiloach::m_pred
NodeArray< edge > m_pred
The predecessor of each node in the currently uppermost path.
Definition: MaxFlowSTPlanarItaiShiloach.h:110
ogdf::MaxFlowSTPlanarItaiShiloach
Computes a max flow in s-t-planar network via uppermost paths.
Definition: MaxFlowSTPlanarItaiShiloach.h:49
ogdf::MaxFlowSTPlanarItaiShiloach::~MaxFlowSTPlanarItaiShiloach
~MaxFlowSTPlanarItaiShiloach()
Free allocated ressources.
Definition: MaxFlowSTPlanarItaiShiloach.h:125
ogdf::MaxFlowSTPlanarItaiShiloach::m_edgeCounter
NodeArray< int > m_edgeCounter
The number of edges visited from each node.
Definition: MaxFlowSTPlanarItaiShiloach.h:107
ogdf::MaxFlowSTPlanarItaiShiloach::EdgePathType::Unknown
@ Unknown
ogdf::MaxFlowSTPlanarItaiShiloach::m_status
NodeArray< NodeType > m_status
The status of each node.
Definition: MaxFlowSTPlanarItaiShiloach.h:113
ogdf::MaxFlowSTPlanarItaiShiloach::EdgePathType::TargetPath
@ TargetPath
ogdf::NodeArray< int >
ogdf::MaxFlowSTPlanarItaiShiloach::EdgePathType::SourcePath
@ SourcePath
ogdf::EdgeArray< bool >
ogdf::MaxFlowSTPlanarItaiShiloach::NodeType::New
@ New
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::MaxFlowSTPlanarItaiShiloach::unshiftedTopPriority
TCap unshiftedTopPriority()
see unshiftedPriority
Definition: MaxFlowSTPlanarItaiShiloach.h:66
ogdf::MaxFlowModule< TCap >::m_s
const node * m_s
Pointer to the source node.
Definition: MaxFlowModule.h:47
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::NodeElement::degree
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition: Graph_d.h:210
ogdf::MaxFlowModule< TCap >::m_G
const Graph * m_G
Pointer to the given graph.
Definition: MaxFlowModule.h:45
ogdf::MaxFlowSTPlanarItaiShiloach::dropEdge
void dropEdge(const edge e)
Removes a single edge from the current path.
Definition: MaxFlowSTPlanarItaiShiloach.h:332
ogdf::MaxFlowSTPlanarItaiShiloach::NodeType::Done
@ Done
ogdf::PrioritizedMapQueue
Prioritized queue interface wrapper for heaps.
Definition: PriorityQueue.h:498
ogdf::MaxFlowSTPlanarItaiShiloach::m_visited
EdgeArray< bool > m_visited
Whether each edge has was visited.
Definition: MaxFlowSTPlanarItaiShiloach.h:104
ogdf::MaxFlowSTPlanarItaiShiloach::unshiftedPriority
TCap unshiftedPriority(edge e)
To work with unsigned, we need a priority shifting of the elements in the priority queue.
Definition: MaxFlowSTPlanarItaiShiloach.h:58
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::EdgeElement::adjSource
adjEntry adjSource() const
Returns the corresponding adjacancy entry at source node.
Definition: Graph_d.h:333
ogdf::MaxFlowSTPlanarItaiShiloach::findUppermostPath
bool findUppermostPath(const edge saturatedEdge)
Establishes the next uppermost path.
Definition: MaxFlowSTPlanarItaiShiloach.h:221
ogdf::MaxFlowSTPlanarItaiShiloach::computeFlowAfterValue
void computeFlowAfterValue()
Computes the actual flow on each edge.
Definition: MaxFlowSTPlanarItaiShiloach.h:198
ogdf::MaxFlowSTPlanarItaiShiloach::getPathType
EdgePathType getPathType(const edge e) const
Performs an alternating backtracking from source and target to determine whether the new node is part...
Definition: MaxFlowSTPlanarItaiShiloach.h:361
ogdf::MaxFlowSTPlanarItaiShiloach::shiftPriority
TCap shiftPriority(TCap priority)
see unshiftedPriority
Definition: MaxFlowSTPlanarItaiShiloach.h:75
ogdf::AdjElement::cyclicSucc
adjEntry cyclicSucc() const
Returns the cyclic successor in the adjacency list.
Definition: Graph_d.h:279
ogdf::ConstCombinatorialEmbedding
Combinatorial embeddings of planar graphs.
Definition: CombinatorialEmbedding.h:198
ogdf::MaxFlowSTPlanarItaiShiloach::NodeType::Path
@ Path
ogdf::EdgeElement::adjTarget
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition: Graph_d.h:335
ogdf::MaxFlowSTPlanarItaiShiloach::m_partialFlow
TCap m_partialFlow
The flow reached thus far (monotonically increasing).
Definition: MaxFlowSTPlanarItaiShiloach.h:119
CombinatorialEmbedding.h
Declaration of CombinatorialEmbedding and face.
ogdf::MaxFlowSTPlanarItaiShiloach::NodeType
NodeType
Each node has a certain type depending on its participation in any path.
Definition: MaxFlowSTPlanarItaiShiloach.h:83
ogdf::MaxFlowModule
Definition: MaxFlowModule.h:40
ogdf::MaxFlowSTPlanarItaiShiloach::computeValue
TCap computeValue(const EdgeArray< TCap > &originalCapacities, const node &source, const node &target)
Computes the maximal flow from source to sink.
Definition: MaxFlowSTPlanarItaiShiloach.h:138
ogdf::MaxFlowSTPlanarItaiShiloach::EdgePathType
EdgePathType
Each edge may be part of the source or target path.
Definition: MaxFlowSTPlanarItaiShiloach.h:94
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::NodeArray::init
void init()
Reinitializes the array. Associates the array with no graph.
Definition: NodeArray.h:255
ogdf::MaxFlowModule< TCap >::m_cap
const EdgeArray< TCap > * m_cap
Pointer to the given capacity array.
Definition: MaxFlowModule.h:46
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::MaxFlowSTPlanarItaiShiloach::EdgePathType::NoPath
@ NoPath
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::MaxFlowSTPlanarItaiShiloach::m_commonFaceAdj
adjEntry m_commonFaceAdj
Definition: MaxFlowSTPlanarItaiShiloach.h:101
ogdf::isSTPlanar
bool isSTPlanar(const Graph &graph, const node s, const node t)
Returns whether G is s-t-planar (i.e.
Definition: extended_graph_alg.h:456
ogdf::MaxFlowSTPlanarItaiShiloach::appendEdge
void appendEdge(const edge e)
Appends an edge to the current path.
Definition: MaxFlowSTPlanarItaiShiloach.h:312
ogdf::MaxFlowModule< TCap >::m_flow
EdgeArray< TCap > * m_flow
Pointer to (extern) flow array.
Definition: MaxFlowModule.h:44