Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MinSteinerTreePrimalDual.h
Go to the documentation of this file.
1
34#pragma once
35
39
40#include <limits>
41
42//#define OGDF_MINSTEINERTREE_PRIMAL_DUAL_LOGGING
43
44namespace ogdf {
45
56template<typename T>
58private:
62 const T MAX_VALUE = std::numeric_limits<T>::max();
63
70
77 void mergeComponents(const node v, const node w);
78
84 void makeActive(int component);
85
91 bool isActive(int component) const;
92
98 int getComponent(const node v) const;
99
106 double getNextEdge(edge* nextEdge);
107
114 void updatePriorities(double eps);
115
119 void init();
120
121protected:
137 virtual T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
138 const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) override;
139
140public:
141 virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
142 const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) override {
143 m_lowerBound = 0;
144 return MinSteinerTreeModule<T>::call(G, terminals, isTerminal, finalSteinerTree);
145 }
146
152 double getLastLowerBound() const;
153};
154
155template<typename T>
157 m_activeComponentIterators.clear();
158 m_activeComponents.clear();
159 m_componentMapping.init(*m_pGraph);
160 m_priorities.init(*m_pGraph, 0);
161}
162
163template<typename T>
165 return m_pComponents->find(m_componentMapping[v]);
166}
167
168template<typename T>
169bool MinSteinerTreePrimalDual<T>::isActive(int component) const {
170 return m_activeComponentIterators[component].valid();
171}
172
173template<typename T>
175 m_activeComponentIterators[comp] = m_activeComponents.pushBack(comp);
176}
177
178template<typename T>
180 int compV = getComponent(v);
181 int compW = getComponent(w);
182
183 // remove former components
184 if (isActive(compV)) {
185 m_activeComponents.del(m_activeComponentIterators[compV]);
186 }
187 if (isActive(compW)) {
188 m_activeComponents.del(m_activeComponentIterators[compW]);
189 }
190
191 // craete new component
192 int compNew = m_pComponents->link(compV, compW);
193 if (!m_activeComponents.empty()) {
194 makeActive(compNew);
195 }
196}
197
198template<typename T>
200 List<node> nodes;
201 m_pGraph->allNodes(nodes);
202 for (node v : nodes) {
203 if (isActive(getComponent(v))) {
204 m_priorities(v) += eps;
205 }
206 }
207}
208
209template<typename T>
211 double result = MAX_VALUE;
212 *nextEdge = nullptr;
213
214 List<edge> edges;
215 m_pGraph->allEdges(edges);
216 for (edge e : edges) {
217 node v = e->source();
218 node w = e->target();
219 int compV = getComponent(v);
220 int compW = getComponent(w);
221 if (compV != compW) { // spanning different components ?
222 double value = m_pGraph->weight(e) - m_priorities(v) - m_priorities(w);
223 int divisor = isActive(compV) + isActive(compW);
224 if (divisor == 0) {
225 value = MAX_VALUE;
226 } else {
227 value /= divisor;
228 }
229 if (*nextEdge == nullptr || value < result) {
230 *nextEdge = e;
231 result = value;
232 }
233 }
234 }
235 return result;
236}
237
238template<typename T>
240 const List<node>& terminals, const NodeArray<bool>& isTerminal,
242 m_pGraph = &G;
243 m_pTerminals = &terminals;
244 m_pIsTerminal = &isTerminal;
246 m_pComponents = &components;
247
249 finalSteinerTree->createEmpty(*m_pGraph);
250
251 init();
252
253 // initialize components
254 List<node> nodes;
255 m_pGraph->allNodes(nodes);
256 for (node v : nodes) {
257 int comp = m_pComponents->makeSet();
258 m_componentMapping[v] = comp;
259 if (isTerminal(v)) {
260 makeActive(comp);
261 }
262 }
263
264#ifdef OGDF_MINSTEINERTREE_PRIMAL_DUAL_LOGGING
265 std::cout << "Goemans primal-dual starting..." << std::endl;
266 std::cout << "terminals:";
267 for (node v : *m_pTerminals) {
268 std::cout << " " << v;
269 }
270 std::cout << std::endl;
271
272 std::cout << "loop starting... " << std::endl;
273#endif
274
275 T result = 0;
276 while (!m_activeComponents.empty()) {
277#ifdef OGDF_MINSTEINERTREE_PRIMAL_DUAL_LOGGING
278 std::cout << "active component exists" << std::endl;
279#endif
280 // idendify next edge
281 edge minEdge = nullptr;
282 double minValue = getNextEdge(&minEdge);
283 OGDF_ASSERT(minEdge != nullptr);
284
285#ifdef OGDF_MINSTEINERTREE_PRIMAL_DUAL_LOGGING
286 std::cout << "minEdge found: " << minEdge << ", weight is " << m_pGraph->weight(minEdge)
287 << ", adjusted weight is " << minValue << std::endl;
288#endif
289 node v = minEdge->source();
290 node w = minEdge->target();
291
292 // include nodes in Steiner tree
293 if (finalSteinerTree->copy(v) == nullptr) {
294 finalSteinerTree->newNode(v);
295 }
296 if (finalSteinerTree->copy(w) == nullptr) {
297 finalSteinerTree->newNode(w);
298 }
299
300 // include edge in Steiner tree
301 T weight = m_pGraph->weight(minEdge);
302 result += weight;
303 finalSteinerTree->newEdge(minEdge, weight);
304
305 m_lowerBound += m_activeComponents.size() * minValue;
306
307 mergeComponents(v, w);
308
309 updatePriorities(minValue);
310 }
311 result -= this->pruneAllDanglingSteinerPaths(*finalSteinerTree, *m_pIsTerminal);
312
313#ifdef OGDF_MINSTEINERTREE_PRIMAL_DUAL_LOGGING
314 std::cout << "calculation finished!" << std::endl;
315#endif
316 return result;
317}
318
319template<typename T>
321 return m_lowerBound;
322}
323
324}
Implementation of disjoint sets data structures (union-find functionality).
Extends the GraphCopy concept to weighted graphs.
Declaration of ogdf::MinSteinerTreeModule.
A Union/Find data structure for maintaining disjoint sets.
Class for the representation of edges.
Definition Graph_d.h:300
Indexed arrays using hashing for element access.
Definition HashArray.h:93
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Serves as an interface for various methods to compute or approximate minimum Steiner trees on undirec...
virtual T call(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly.
Primal-Dual approximation algorithm for Steiner tree problems.
const NodeArray< bool > * m_pIsTerminal
virtual T call(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly.
void mergeComponents(const node v, const node w)
Merges two disjoint components.
int getComponent(const node v) const
Finds the biggest set including node v.
void updatePriorities(double eps)
Must be called after merging any two components.
double getLastLowerBound() const
Returns the lower bound calculated while solving the last problem.
HashArray< int, ListIterator< int > > m_activeComponentIterators
double getNextEdge(edge *nextEdge)
Idendifies the next edge with a tight-to-be packing constraint.
void init()
Initializes all required datastructes.
bool isActive(int component) const
Returns whether the given component is active.
const EdgeWeightedGraph< T > * m_pGraph
void makeActive(int component)
Marks the specified component as active.
virtual T computeSteinerTree(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
Builds a minimum Steiner tree given a weighted graph and a list of terminals.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
#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.