Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MaxFlowModule.h
Go to the documentation of this file.
1
32#pragma once
33
35#include <ogdf/basic/Graph.h>
36
37namespace ogdf {
38
39template<typename T>
41protected:
44 const Graph* m_G;
46 const node* m_s;
47 const node* m_t;
48
49private:
50 bool usingExternFlow = false;
51 bool doingAReInit = false;
52
53 void destroy() {
54 if (!usingExternFlow) {
55 delete m_flow;
56 }
57 delete m_et;
58 }
59
60public:
64
66
71 explicit MaxFlowModule(const Graph& graph, EdgeArray<T>* flow = nullptr)
72 : m_s(nullptr), m_t(nullptr) {
73 init(graph, flow);
74 }
75
77 virtual ~MaxFlowModule() { destroy(); }
78
82
87 virtual void init(const Graph& graph, EdgeArray<T>* flow = nullptr) {
88 // if re-init after an init with internal flow:
89 if (doingAReInit) {
90 destroy();
91 }
92 m_G = &graph;
93 if (flow) {
94 m_flow = flow;
95 usingExternFlow = true;
96 } else {
97 usingExternFlow = false; // in case of a re-init
98 m_flow = new EdgeArray<T>(*m_G, 0);
99 }
100 m_et = new EpsilonTest();
101 doingAReInit = true;
102 }
103
106
109 void useEpsilonTest(const double& eps) {
110 delete m_et;
111 m_et = new EpsilonTest(eps);
112 }
113
127 virtual T computeValue(const EdgeArray<T>& cap, const node& s, const node& t) = 0;
128
132 virtual void computeFlowAfterValue() = 0;
133
137
142 flow = *m_flow;
143 }
144
147 bool isFeasibleInstance() const {
148 for (edge e : m_G->edges) {
149 if ((*m_cap)[e] < 0) {
150 return false;
151 }
152 }
153 return true;
154 }
155
157
165 T val = computeValue(cap, s, t);
167 return val;
168 }
169};
170
171}
Compare floating point numbers with epsilons and integral numbers with normal compare operators.
Includes declaration of graph class.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition Graph_d.h:592
const node * m_t
Pointer to the sink node.
virtual ~MaxFlowModule()
Destructor that deletes m_flow if it is an internal flow array.
bool usingExternFlow
Is an extern flow array given in the constructor?
virtual void computeFlowAfterValue()=0
Compute the flow itself after the flow value is already computed. Only used in algorithms with 2 phas...
MaxFlowModule(const Graph &graph, EdgeArray< T > *flow=nullptr)
Constructor that calls init.
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< T > * 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.
virtual T computeValue(const EdgeArray< T > &cap, const node &s, const node &t)=0
Compute only the value of the flow.
bool doingAReInit
Is the next "init" call a re-init?
const node * m_s
Pointer to the source node.
const EdgeArray< T > * m_cap
Pointer to the given capacity array.
MaxFlowModule()
Empty Constructor.
T computeFlow(EdgeArray< T > &cap, node &s, node &t, EdgeArray< T > &flow)
Only a shortcut for computeValue and computeFlowAfterValue.
void computeFlowAfterValue(EdgeArray< T > &flow)
Compute the flow itself after the flow value is already computed. Only used in algorithms with 2 phas...
EpsilonTest * m_et
Pointer to the used EpsilonTest.
Class for the representation of nodes.
Definition Graph_d.h:177
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.