Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MinSteinerTreeZelikovsky.h
Go to the documentation of this file.
1
33#pragma once
34
35#include <ogdf/basic/List.h>
45
46namespace ogdf {
47
65template<typename T>
67public:
68 template<typename TYPE>
70 template<typename TYPE>
72
74 enum class WinCalculation {
75 absolute,
77 };
78
80 enum class TripleGeneration {
82 voronoi,
84 };
85
87 enum class TripleReduction {
88 on,
89 off
90 };
91
93 enum class SaveCalculation {
106 hybrid
107 };
108
110 enum class Pass {
113 one,
115 multi
116 };
117
128
130
131 virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
132 const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) override {
134 m_tripleLookUps = 0;
136 return MinSteinerTreeModule<T>::call(G, terminals, isTerminal, finalSteinerTree);
137 }
138
144 void forceAPSP(bool force = true) { m_ssspDistances = !force; }
145
148
151
154
157
160
163
166
169
171 void pass(Pass p) { m_pass = p; }
172
174 Pass pass() const { return m_pass; }
175
178
181
183 long numberOfTripleLookUps() const { return m_tripleLookUps; }
184
185protected:
194 virtual T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
195 const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) override;
196
201
205 inline void generateTriple(node u, node v, node w, node center, const T& minCost,
206 const Save<T>& save) {
207 const double gain = save.gain(u, v, w);
208 const double win = calcWin(gain, minCost);
209 if (tripleReduction() == TripleReduction::off || win > 0) {
211 OGDF_ASSERT(center);
212 Triple<T> triple(u, v, w, center, minCost, win);
213 m_triples.pushBack(triple);
214 }
215 }
216
222 inline void generateTriples(const Save<T>& save,
225 [this, &save](node u, node v, node w, node center, T minCost) {
226 generateTriple(u, v, w, center, minCost, save);
227 });
228 }
229
245
257
264
272 bool findBestTripleForCenter(node center, const Save<T>& save, Triple<T>& maxTriple) const {
273 bool updated = false; // return value
274
275 // find s0, nearest terminal to center
276 T best = std::numeric_limits<T>::max();
277 node s0 = nullptr;
278 for (node s : *m_terminals) {
279 T tmp = m_distance[s][center];
280 if (best > tmp) {
281 best = tmp;
282 s0 = s;
283 }
284 }
285 OGDF_ASSERT(s0);
286 OGDF_ASSERT(m_pred[s0][center]);
287
288 // find s1 maximizing save(s0, s1) - d(center, s1)
289 node s1 = nullptr;
290 T save1Val(0);
291 for (node s : *m_terminals) {
292 if (s != s0 && m_pred[s][center] != nullptr) {
293 OGDF_ASSERT(m_distance[s][center] != std::numeric_limits<T>::max());
294 T tmpVal = save.saveWeight(s, s0);
295 T tmp = tmpVal - m_distance[s][center];
296 if (!s1 || best < tmp) {
297 best = tmp;
298 s1 = s;
300 }
301 }
302 }
303 if (s1) {
304 OGDF_ASSERT(m_pred[s1][center]);
305 node s2 = nullptr;
306 T save2Val(0);
307 const edge save1 = save.saveEdge(s0, s1);
308 for (node s : *m_terminals) {
309 if (s != s0 && s != s1 && m_pred[s][center] != nullptr) {
310 OGDF_ASSERT(m_distance[s][center] != std::numeric_limits<T>::max());
311 const edge tmp = save.saveEdge(s0, s);
312 save2Val = save.saveWeight(tmp == save1 ? s1 : s0, s);
313 T tmpWin = save1Val + save2Val - m_distance[s0][center] - m_distance[s1][center]
314 - m_distance[s][center];
315 if (!s2 || best < tmpWin) {
316 best = tmpWin;
317 s2 = s;
318 }
319 }
320 }
321
322 if (s2 // it may happen that s2 does not exist
323 && best > maxTriple.win()) { // best win is better than previous best; also positive
324 OGDF_ASSERT(m_pred[s2][center]);
325 maxTriple.s0(s0);
326 maxTriple.s1(s1);
327 maxTriple.s2(s2);
328 maxTriple.z(center);
329 maxTriple.win(best);
330 //maxTriple.cost(save1Val + save2Val - win); not needed
331 updated = true;
332 }
333 }
334 return updated;
335 }
336
343
350
354 double calcWin(double gain, T cost) const {
355 switch (winCalculation()) {
357 return gain / cost - 1.0;
359 default:
360 return gain - cost;
361 }
362 }
363
365 // generate complete graph
366 for (node v : *m_terminals) {
367 steinerTree.newNode(v);
368 }
369 for (node u : steinerTree.nodes) {
370 const NodeArray<T>& dist = m_distance[steinerTree.original(u)];
371 for (node v = u->succ(); v; v = v->succ()) {
372 steinerTree.newEdge(u, v, dist[steinerTree.original(v)]);
373 }
374 }
375 // compute MST
377 }
378
379private:
386
393
397};
398
399template<typename T>
401 const List<node>& terminals, const NodeArray<bool>& isTerminal,
403 OGDF_ASSERT(tripleGeneration()
404 != TripleGeneration::ondemand // combinations that only work with ondemand:
405 || (winCalculation() == WinCalculation::absolute
406 && saveCalculation() != SaveCalculation::hybrid && pass() != Pass::one));
407
408 m_originalGraph = &G;
409 m_terminals = &terminals;
410 m_isTerminal = &isTerminal;
411
412 // build the complete terminal graph and a distance matrix
414 for (node v : *m_terminals) {
415 isNewTerminal[v] = true;
416 }
417
418 if (terminals.size() >= 3) {
419 computeDistanceMatrix();
420
421 // init terminal-spanning tree and its save-edge data structure
422 EdgeWeightedGraphCopy<T> steinerTree; // the terminal-spanning tree to be modified
423 steinerTree.createEmpty(G);
424 generateInitialTerminalSpanningTree(steinerTree);
425
426 Save<T>* save = nullptr;
427 switch (saveCalculation()) {
428 case SaveCalculation::staticEnum:
430 break;
431 case SaveCalculation::staticLCATree:
433 break;
434 case SaveCalculation::dynamicLCATree:
435 case SaveCalculation::hybrid:
437 break;
438 }
439 OGDF_ASSERT(save);
440
441 if (tripleGeneration() == TripleGeneration::ondemand) { // ondemand triple generation
442 tripleOnDemand(*save, isNewTerminal);
443 } else { // exhaustive or voronoi
444 // triple generation phase
445 if (saveCalculation() == SaveCalculation::hybrid) {
447 generateTriples(saveTriple);
448 } else {
449 generateTriples(*save);
450 }
451 // contraction phase
452 if (pass() == Pass::multi) {
453 multiPass(*save, isNewTerminal);
454 } else { // pass() == one
455 onePass(*save, isNewTerminal);
456 }
457 }
458 delete save;
459
460 // cleanup
461 m_triples.clear();
462 }
463
464 // obtain final Steiner Tree using (MST-based) Steiner tree approximation algorithm
466}
467
468template<typename T>
470 if (m_ssspDistances) {
471 MinSteinerTreeModule<T>::allTerminalShortestPaths(*m_originalGraph, *m_terminals,
472 *m_isTerminal, m_distance, m_pred);
473 } else {
474 MinSteinerTreeModule<T>::allPairShortestPaths(*m_originalGraph, *m_isTerminal, m_distance,
475 m_pred);
476 }
477}
478
479template<typename T>
483 MinSteinerTreeModule<T>::getNonterminals(nonterminals, *m_originalGraph, *m_isTerminal);
484 do {
485 maxTriple.win(0);
486 for (node center : nonterminals) {
487 if (findBestTripleForCenter(center, save, maxTriple)) {
488 ++m_triplesGenerated;
489 }
490 }
491
492 if (maxTriple.win() > 0) {
493 contractTriple(maxTriple, save, isNewTerminal);
494 }
495 } while (maxTriple.win() > 0);
496}
497
498template<typename T>
500 m_triples.quicksort(GenericComparer<Triple<T>, double>(
501 [](const Triple<T>& x) -> double { return -x.win(); }));
502
503 for (const Triple<T>& t : m_triples) {
504 ++m_tripleLookUps;
505 if (calcWin(double(save.gain(t.s0(), t.s1(), t.s2())), t.cost()) > 0) {
506 contractTriple(t, save, isNewTerminal);
507 }
508 }
509}
510
511template<typename T>
513 double win = 0;
515
516 do {
517 win = 0;
519 for (ListIterator<Triple<T>> it = m_triples.begin(); it.valid(); it = nextIt) {
520 nextIt = it.succ();
521 ++m_tripleLookUps;
522 Triple<T>& t = *it;
523 t.win(calcWin(double(save.gain(t.s0(), t.s1(), t.s2())), t.cost()));
524 if (t.win() > win) {
525 win = t.win();
526 maxTriple = it;
527 } else {
528 if (tripleReduction() == TripleReduction::on && t.win() <= 0) {
529 m_triples.del(it);
530 }
531 }
532 }
533
534 if (win > 0) {
535 contractTriple(*maxTriple, save, isNewTerminal);
536 m_triples.del(maxTriple);
537 }
538 } while (win > 0);
539}
540
541}
Extends the GraphCopy concept to weighted graphs.
Definition of ogdf::steiner_tree::Full3ComponentGeneratorEnumeration class template.
Definition of ogdf::steiner_tree::Full3ComponentGeneratorVoronoi class template.
Declaration of doubly linked lists and iterators.
Declaration of ogdf::MinSteinerTreeModule.
A weighted tree as auxiliary data structure for contraction based algorithms.
Implementation of the staticTree option for calculating save edges in Zelikovsky's 11/6-approximation...
Implementation of the staticLCATree option for calculating save edges in Zelikovsky's 11/6-approximat...
Definition of a Triple used in contraction-based approximation algorithm for the minimum Steiner tree...
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
Class for the representation of edges.
Definition Graph_d.h:300
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
int size() const
Returns the number of elements in the list.
Definition List.h:1472
Encapsulates a pointer to a list element.
Definition List.h:103
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.
static void allTerminalShortestPaths(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
Runs a given (or the default) single-source-shortest-paths function from all terminals.
static void allPairShortestPaths(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
The default all-pair-shortest-paths algorithm.
static void getNonterminals(ArrayBuffer< node > &nonterminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Generates a list (as ArrayBuffer<node>) of all nonterminals.
This class implements the 11/6-approximation algorithm by Zelikovsky for the minimum Steiner tree pro...
bool findBestTripleForCenter(node center, const Save< T > &save, Triple< T > &maxTriple) const
Find the best triple for a given nonterminal center.
WinCalculation winCalculation() const
Returns type of gain calculation currently in use.
double calcWin(double gain, T cost) const
Calculate the win.
SaveCalculation
Different methods for obtaining save edges.
@ staticLCATree
Builds a "weight tree" (save edges are inner nodes, terminals are leaves and searches save edges via ...
@ dynamicLCATree
Same as staticLCATree but each time a triple has been contracted the "weight tree" is updated dynamic...
@ staticEnum
Stores explicitly the save edge for every pair of terminals. Needs O(n^2) space but has fast query ti...
@ hybrid
Uses staticEnum for the triple generation phase (many queries) and dynamicLCATree during the contract...
SaveCalculation saveCalculation() const
Returns type of save calculation currently in use.
TripleReduction tripleReduction() const
Returns type of triple reduction currently in use.
SaveCalculation m_saveCalculation
Chosen option for save calculation.
void forceAPSP(bool force=true)
For the 3-restricted case, it is sufficient to compute an SSSP from every terminal instead of doing a...
long m_triplesContracted
Number of contracted triples.
void tripleOnDemand(Save< T > &save, NodeArray< bool > &isNewTerminal)
Contraction phase for algorithm generating triples on demand.
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.
List< Triple< T > > m_triples
The list of triples during the algorithm.
void tripleGeneration(TripleGeneration tg)
Sets type of triple generation.
void onePass(Save< T > &save, NodeArray< bool > &isNewTerminal)
Contraction phase for the one pass heuristic.
TripleGeneration
Choice of triple generation.
@ ondemand
generate triples "on the fly", only usable with WinCalculation::absolute
TripleGeneration tripleGeneration() const
Returns type of triple generation currently in use.
const NodeArray< bool > * m_isTerminal
Incidence vector for terminal nodes.
const EdgeWeightedGraph< T > * m_originalGraph
The original edge-weighted graph.
Pass pass() const
Returns type of pass currently in use.
void tripleReduction(TripleReduction tr)
Sets type of triple reduction.
void generateTriples(const Save< T > &save, const steiner_tree::Full3ComponentGeneratorModule< T > &fcg)
Generates triples using the given full 3-component generator.
long numberOfGeneratedTriples() const
Returns the number of generated triples.
MinSteinerTreeZelikovsky(WinCalculation wc=WinCalculation::absolute, TripleGeneration tg=TripleGeneration::voronoi, SaveCalculation sc=SaveCalculation::hybrid, TripleReduction tr=TripleReduction::on, Pass pass=Pass::multi)
TripleReduction
Switches immediate triple dropping.
@ on
removes triples as soon as their gain is known to be non positive
void generateInitialTerminalSpanningTree(EdgeWeightedGraphCopy< T > &steinerTree)
NodeArray< NodeArray< T > > m_distance
The distance matrix.
void computeDistanceMatrix()
Computes the distance matrix for the original graph.
TripleReduction m_tripleReduction
Chosen option for triple reduction.
void multiPass(Save< T > &save, NodeArray< bool > &isNewTerminal)
Contraction phase for the original version of the algorithm.
void saveCalculation(SaveCalculation sv)
Sets type of save calculation.
void generateTriples(const Save< T > &save)
Generates triples according to the chosen option.
long m_triplesGenerated
Number of generated triples.
NodeArray< NodeArray< edge > > m_pred
The predecessor matrix.
WinCalculation m_winCalculation
Chosen option for gain calculation.
bool m_ssspDistances
True iff we only compute SSSP from terminals instead of APSP for full component construction.
long m_tripleLookUps
Number of triple lookups.
TripleGeneration m_tripleGeneration
Chosen option for triple generation.
Pass
Enables a heuristic version (for TG exhaustive and voronoi only)
@ multi
normal, greedy version
@ one
heuristic: evaluate all triples, sort them descending by gain, traverse sorted triples once,...
long numberOfContractedTriples() const
Returns the number of contracted triples.
long numberOfTripleLookUps() const
Returns the number of triple lookups during execution time.
const List< node > * m_terminals
List of terminal nodes.
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 generateTriple(node u, node v, node w, node center, const T &minCost, const Save< T > &save)
Add a found triple to the triples list.
void pass(Pass p)
Sets type of pass.
void contractTriple(const Triple< T > &triple, Save< T > &save, NodeArray< bool > &isNewTerminal)
Contracts a triple and updates the save data structure.
void winCalculation(WinCalculation wc)
Sets type of gain calculation.
WinCalculation
Choice of objective function.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
node succ() const
Returns the successor in the list of all nodes.
Definition Graph_d.h:229
Interface for full 3-component generation including auxiliary functions.
Full 3-component generation using Voronoi regions.
Dynamically updatable weighted Tree for determining save edges via LCA computation.
Definition SaveDynamic.h:50
This class computes save edges recursively and stores for every node pair their save edge in a HashAr...
Definition SaveEnum.h:48
This class serves as an interface for different approaches concerning the calculation of save edges.
Definition Save.h:45
virtual T gain(node u, node v, node w) const =0
Returns the gain (sum of the save edges) of a node triple.
virtual void update(const Triple< T > &t)=0
Updates the weighted tree data structure given a contracted triple.
virtual edge saveEdge(node u, node v) const =0
Returns the save edge between two nodes.
virtual T saveWeight(node u, node v) const =0
Returns the weight of the save edge between two nodes.
This class behaves basically the same as SaveDynamic except that the update of the weighted graph is ...
Definition SaveStatic.h:48
This class represents a triple used by various contraction-based minimum Steiner tree approximations.
Definition Triple.h:44
double win() const
Definition Triple.h:60
Algorithms used by at least two functions of Steiner tree code or its internal helpers.
T makeMinimumSpanningTree(Graph &G, const EdgeArray< T > &weight)
Reduce a graph to its minimum spanning tree (MST) using Kruskal's algorithm.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
T obtainFinalSteinerTree(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const NodeArray< bool > &isOriginalTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
The namespace for all OGDF objects.
Compare elements based on a single comparable attribute.
Definition comparer.h:398