Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MinSteinerTreeMehlhorn.h
Go to the documentation of this file.
1
33#pragma once
34
35#include <ogdf/basic/List.h>
39
40namespace ogdf {
41
52template<typename T>
54public:
56
58
68 static void calculateCompleteGraph(const EdgeWeightedGraph<T>& wG, const List<node>& terminals,
69 const Voronoi<T>& voronoi, EdgeArray<edge>& bridges,
71
72protected:
81 virtual T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
82 const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) override;
83
95 const Voronoi<T>& voronoi, const NodeArray<edge>& mstPred, const EdgeArray<edge>& bridges,
97
106 const EdgeWeightedGraph<T>& wG);
107
117
121 class MehlhornTripleBucketMaxFunc : public BucketFunc<MehlhornTriple> {
122 public:
124
126 int source_index = MT.u->index();
127 int target_index = MT.v->index();
130 return target_index;
131 } else {
132 return source_index;
133 }
134 }
135 };
136
140 class MehlhornTripleBucketMinFunc : public BucketFunc<MehlhornTriple> {
141 public:
143
145 int source_index = MT.u->index();
146 int target_index = MT.v->index();
149 return source_index;
150 } else {
151 return target_index;
152 }
153 }
154 };
155};
156
157template<typename T>
159 const List<node>& terminals, const NodeArray<bool>& isTerminal,
162 EdgeArray<edge> bridges;
163 Voronoi<T> voronoi(G, G.edgeWeights(), terminals);
164
165 calculateCompleteGraph(G, terminals, voronoi, bridges, completeTerminalGraph);
166
169
171 finalSteinerTree->createEmpty(G);
172
173 reinsertShortestPaths(completeTerminalGraph, voronoi, mstPred, bridges, *finalSteinerTree, G);
174
177
178 return mstWeight;
179}
180
181template<typename T>
183 const List<node>& terminals, const Voronoi<T>& voronoi, EdgeArray<edge>& bridges,
185 completeTerminalGraph.createEmpty(wG);
186
187 for (node v : terminals) {
188 completeTerminalGraph.newNode(v);
189 }
190 if (completeTerminalGraph.numberOfNodes() <= 1) {
192 return;
193 }
194
195 // extract complete graph edges
197 for (edge e : wG.edges) {
199 triple.u = voronoi.seed(e->source());
200 triple.v = voronoi.seed(e->target());
201 if (triple.u != triple.v) {
202 triple.value =
203 voronoi.distance(e->source()) + voronoi.distance(e->target()) + wG.weight(e);
204 triple.bridge = e;
205 triples.pushBack(triple);
206 }
207 }
208
211
212 triples.bucketSort(0, wG.maxNodeIndex(), mtbMax);
213 triples.bucketSort(0, wG.maxNodeIndex(), mtbMin);
214
215 int currentSource = triples.front().u->index();
216 int currentTarget = triples.front().v->index();
218
220
221 for (ListConstIterator<MehlhornTriple> mtIt = triples.begin().succ(); mtIt.valid(); ++mtIt) {
222 if (((*mtIt).u->index() == currentSource && (*mtIt).v->index() == currentTarget)
223 || ((*mtIt).u->index() == currentTarget && (*mtIt).v->index() == currentSource)) {
224 if ((*mtIt).value < (*minTriple).value) {
225 minTriple = mtIt;
226 }
227 } else {
228 // add new direct edge
229 edge tmp = completeTerminalGraph.newEdge(completeTerminalGraph.copy((*minTriple).u),
230 completeTerminalGraph.copy((*minTriple).v), (*minTriple).value);
231 bridges[tmp] = (*minTriple).bridge;
232
233 currentSource = (*mtIt).u->index();
234 currentTarget = (*mtIt).v->index();
235 minTriple = mtIt;
236 }
237 }
238 // insert last triple
239 if (minTriple.valid()) {
240 edge tmp = completeTerminalGraph.newEdge(completeTerminalGraph.copy((*minTriple).u),
241 completeTerminalGraph.copy((*minTriple).v), (*minTriple).value);
242 bridges[tmp] = (*minTriple).bridge;
243 }
244}
245
246template<typename T>
248 const Voronoi<T>& voronoi, const NodeArray<edge>& mstPred, const EdgeArray<edge>& bridges,
250 for (node u : completeTerminalGraph.nodes) {
251 if (mstPred[u] != nullptr) {
252 edge bridge = bridges[mstPred[u]];
253 node v = bridge->source();
254 node w = bridge->target();
255 insertPath(v, voronoi, finalSteinerTree, wG);
256 insertPath(w, voronoi, finalSteinerTree, wG);
257 edge e = finalSteinerTree.newEdge(finalSteinerTree.copy(v), finalSteinerTree.copy(w),
258 wG.weight(bridge));
259 finalSteinerTree.setEdge(bridge, e);
260 }
261 }
262}
263
264template<typename T>
269 if (!currentTarget) {
270 currentTarget = finalSteinerTree.newNode(u);
271 }
272 edge e = voronoi.predecessorEdge(u);
273 edge newE;
274 while (e && finalSteinerTree.chain(e).empty()) { // e is not in ST yet
277 == nullptr) {
280 }
281 if (finalSteinerTree.original(currentSource) == e->source()) {
282 newE = finalSteinerTree.newEdge(currentSource, currentTarget, wG.weight(e));
283 } else {
284 newE = finalSteinerTree.newEdge(currentTarget, currentSource, wG.weight(e));
285 }
286 finalSteinerTree.setEdge(e, newE);
288 e = voronoi.predecessorEdge(finalSteinerTree.original(currentTarget));
289 }
290}
291
292namespace steiner_tree {
293
294template<typename T>
305}
306}
Extends the GraphCopy concept to weighted graphs.
Declaration of doubly linked lists and iterators.
Declaration of ogdf::MinSteinerTreeModule.
Definition of ogdf::Voronoi class template.
Abstract base class for bucket functions.
Definition basic.h:241
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
node opposite(node v) const
Returns the adjacent node different from v.
Definition Graph_d.h:350
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 EdgeArray< T > & edgeWeights() const
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Encapsulates a pointer to a list element.
Definition List.h:103
Helper class to sort MehlhornTriples lexicographically.
Helper class to sort MehlhornTriples lexicographically.
This class implements the Minimum Steiner Tree 2-approximation algorithm by Mehlhorn.
void insertPath(node u, const Voronoi< T > &voronoi, EdgeWeightedGraphCopy< T > &finalSteinerTree, const EdgeWeightedGraph< T > &wG)
Inserts a shortest path corresponding to an edge in the complete terminal graph.
void reinsertShortestPaths(EdgeWeightedGraphCopy< T > &completeTerminalGraph, const Voronoi< T > &voronoi, const NodeArray< edge > &mstPred, const EdgeArray< edge > &bridges, EdgeWeightedGraphCopy< T > &finalSteinerTree, const EdgeWeightedGraph< T > &wG)
Swaps an edge in the complete terminal graph with the corresponding shortest path in the original gra...
static void calculateCompleteGraph(const EdgeWeightedGraph< T > &wG, const List< node > &terminals, const Voronoi< T > &voronoi, EdgeArray< edge > &bridges, EdgeWeightedGraphCopy< T > &completeTerminalGraph)
Builds a complete terminal graph.
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.
Serves as an interface for various methods to compute or approximate minimum Steiner trees on undirec...
static T pruneAllDanglingSteinerPaths(EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
Prunes nonterminal leaves and their paths to terminal or branching nodes.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Computes Voronoi regions in an edge-weighted graph.
Definition Voronoi.h:46
T distance(node v) const
Returns the distance between v and its Voronoi seed.
Definition Voronoi.h:84
node seed(node v) const
Returns the Voronoi seed of node v.
Definition Voronoi.h:87
edge predecessorEdge(node v) const
Returns the edge incident to v and its predecessor. Note that the predecessor of a terminal is nullpt...
Definition Voronoi.h:75
T makeMinimumSpanningTree(Graph &G, const EdgeArray< T > &weight)
Reduce a graph to its minimum spanning tree (MST) using Kruskal's algorithm.
T computeMinST(const Graph &G, const EdgeArray< T > &weight, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree using Prim's algorithm.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
T constructTerminalSpanningTreeUsingVoronoiRegions(EdgeWeightedGraphCopy< T > &terminalSpanningTree, const EdgeWeightedGraph< T > &graph, const List< node > &terminals)
The namespace for all OGDF objects.
Represents a triple as specified in the algorithms description (see paper)