Graph Drawing

 v. 2023.09 (Elderberry)

No Matches
Go to the documentation of this file.
34#pragma once
42namespace ogdf {
48template<typename TCap>
53 // gr = dg.
54 for (edge e = gr.lastEdge(); e != nullptr; e = e->pred()) {
55 edge e_new_dg = gr.newEdge(e->target(), e->source());
57 }
58 }
68 TCap computeValue(const EdgeArray<TCap>& cap, const node& s, const node& t) override {
69 // clear old flow
70 (*this->m_flow).fill(0);
71 // store capacity, source and sink
72 this->m_cap = &cap;
73 this->m_s = &s;
74 this->m_t = &t;
77 OGDF_ASSERT(isSTPlanar(*this->m_G, s, t));
78 GraphCopy copyG(*this->m_G);
79 node copyS = copyG.copy(s);
80 node copyT = copyG.copy(t);
83 adjEntry adjAtSource = ce.findCommonFace(copyS, copyT, adjAtTarget, false);
84 face f_infty = ce.rightFace(adjAtSource);
85 ce.setExternalFace(f_infty);
87 // split the external face
92 for (edge e : (*this->m_G).edges) {
93 costs[dg.dualEdge(copyG.copy(e))] = cap[e];
94 }
96 costs[dg.dualEdge(ts_edge)] = std::numeric_limits<TCap>::max();
99 NodeArray<edge> preds(dg, nullptr);
101, costs, dg.dualNode(f_infty), preds, dists, true); // directed
103 for (edge e : (*this->m_G).edges) {
104 (*this->m_flow)[e] = dists[dg.dualNode(ce.leftFace(copyG.copy(e)->adjSource()))]
105 - dists[dg.dualNode(ce.rightFace(copyG.copy(e)->adjSource()))];
106 }
108 // compute flow value
109 TCap flowValue = 0;
110 for (adjEntry adj : s->adjEntries) {
111 edge e = adj->theEdge();
112 if (e->source() == s) {
113 flowValue += (*this->m_flow)[e];
114 } else {
115 flowValue -= (*this->m_flow)[e];
116 }
117 }
118 return flowValue;
119 }
123 void computeFlowAfterValue() override { /* nothing to do here */
124 }
126 void init(const Graph& graph, EdgeArray<TCap>* flow = nullptr) override {
127 OGDF_ASSERT(isConnected(graph));
128 OGDF_ASSERT(isPlanar(graph));
129 MaxFlowModule<TCap>::init(graph, flow);
130 }
132 // use methods from super class
Includes declaration of dual graph class.
Interface for Max Flow Algorithms.
Class for adjacency list elements.
Definition Graph_d.h:79
Combinatorial embeddings of planar graphs with modification functionality.
Dijkstra's single source shortest path algorithm.
Definition Dijkstra.h:53
A dual graph including its combinatorial embedding of an embedded graph.
Definition DualGraph.h:56
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
node source() const
Returns the source node of the edge.
Definition Graph_d.h:335
Faces in a combinatorial embedding.
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
const node * m_t
Pointer to the sink node.
virtual void init(const Graph &graph, EdgeArray< T > *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.
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 dual shortest paths.
void createBackArcs(Graph &gr, EdgeArray< TCap > &new_costs)
Create back arcs for all edges and set the backedges' new_costs to zero.
TCap computeValue(const EdgeArray< TCap > &cap, const node &s, const node &t) override
Compute only the value of the flow.
void computeFlowAfterValue() override
Implementation of computeFlowAfterValue from the super class. This does nothing, because the algorith...
void init(const Graph &graph, EdgeArray< TCap > *flow=nullptr) override
Initialize the problem with a graph and optional flow array. If no flow array is given,...
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
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
Declaration of extended graph algorithms.
Implementation of Dijkstra's single source shortest path algorithm.
bool isConnected(const Graph &G)
Returns true iff G is connected.
bool isSTPlanar(const Graph &graph, const node s, const node t)
Returns whether G is s-t-planar (i.e.
bool isPlanar(const Graph &G)
Returns true, if G is planar, false otherwise.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/ for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Declaration of simple graph algorithms.