Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MinSteinerTreeTakahashi.h
Go to the documentation of this file.
1
33#pragma once
34
35#include <ogdf/basic/List.h>
39
40namespace ogdf {
41
56template<typename T>
58public:
60
62
70 virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
72 const node startNode) {
73 return call(G, terminals, isTerminal, isTerminal, finalSteinerTree, startNode);
74 }
75
83 virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
84 const NodeArray<bool>& isTerminal, const NodeArray<bool>& isOriginalTerminal,
86 return call(G, terminals, isTerminal, isOriginalTerminal, finalSteinerTree,
87 terminals.front());
88 }
89
91
100 virtual T call(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
101 const NodeArray<bool>& isTerminal, const NodeArray<bool>& isOriginalTerminal,
103
104protected:
105 virtual T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
106 const NodeArray<bool>& isTerminal, EdgeWeightedGraphCopy<T>*& finalSteinerTree) override {
107 return call(G, terminals, isTerminal, isTerminal, finalSteinerTree, terminals.front());
108 }
109
121 int numberOfTerminals, const NodeArray<bool>& isTerminal);
122};
123
124template<typename T>
126 const NodeArray<bool>& isTerminal, const NodeArray<bool>& isOriginalTerminal,
129
131 terminalSpanningTree.createEmpty(G);
132 terminalDijkstra(G, terminalSpanningTree, startNode, terminals.size(), isTerminal);
133
135 for (node u : G.nodes) {
136 if (!terminalSpanningTree.copy(u)) {
137 finalSteinerTree->delNode(finalSteinerTree->copy(u));
138 }
139 }
140
144
145 return mstWeight;
146}
147
148template<typename T>
151 int numberOfTerminals, const NodeArray<bool>& isTerminal) {
152 NodeArray<edge> predecessor(wG, nullptr);
153 NodeArray<T> distance(wG, std::numeric_limits<T>::max());
154 distance[s] = 0;
155 NodeArray<T> bestDistance(wG, std::numeric_limits<T>::max());
156 bestDistance[s] = 0;
158
159 PrioritizedMapQueue<node, T> queue(wG); //priority queue
160 for (node v : wG.nodes) {
161 queue.push(v, distance[v]);
162 }
163
164 T mstWeight = 0;
165 int terminalsFound = 1;
166 while (!queue.empty() && terminalsFound < numberOfTerminals) {
167 node v = queue.topElement();
168 queue.pop();
169 isInQueue[v] = false;
170 bestDistance[v] = distance[v];
171 if (isTerminal[v] && distance[v] > 0) {
173 // insert path from new node to old tree
175 while (distance[v] > 0) {
176 distance[v] = 0;
177 queue.push(v, distance[v]);
178 isInQueue[v] = true;
179 const edge e = predecessor[v];
180 OGDF_ASSERT(e);
181 const node w = e->opposite(v);
183 if (!tmpS) {
185 }
186 edge tmpE;
187 if (e->target() == v) {
188 tmpE = intermediateTerminalSpanningTree.newEdge(tmpS, tmpT, wG.weight(e));
189 } else {
190 tmpE = intermediateTerminalSpanningTree.newEdge(tmpT, tmpS, wG.weight(e));
191 }
192 mstWeight += wG.weight(e);
194 tmpT = tmpS;
195 v = w;
196 }
197 } else { // !isTerminal[v] || distance[v] == 0
198 for (adjEntry adj : v->adjEntries) {
199 const node w = adj->twinNode();
200 const edge e = adj->theEdge();
201 if (distance[w] > distance[v] + wG.weight(e) && bestDistance[w] >= distance[w]) {
202 distance[w] = distance[v] + wG.weight(e);
203 if (!isInQueue[w]) {
204 queue.push(w, distance[w]);
205 isInQueue[w] = true;
206 } else {
207 queue.decrease(w, distance[w]);
208 }
209 predecessor[w] = e;
210 }
211 }
212 }
213 }
214 return mstWeight;
215}
216
217}
Extends the GraphCopy concept to weighted graphs.
Declaration of doubly linked lists and iterators.
Declaration of ogdf::MinSteinerTreeModule.
Class for adjacency list elements.
Definition Graph_d.h:79
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
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
const_reference front() const
Returns a const reference to the first element.
Definition List.h:289
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.
This class implements the minimum Steiner tree 2-approximation algorithm by Takahashi and Matsuyama w...
virtual T call(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const NodeArray< bool > &isOriginalTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
An extended call method with intermediate and final (original) terminals.
T terminalDijkstra(const EdgeWeightedGraph< T > &wG, EdgeWeightedGraphCopy< T > &intermediateTerminalSpanningTree, const node s, int numberOfTerminals, const NodeArray< bool > &isTerminal)
Modified Dijkstra algorithm to solve the Minimum Steiner Tree problem.
virtual T call(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree, const node startNode)
An extended call method with specific start node.
virtual T computeSteinerTree(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
Computes the actual Steiner tree.
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
Prioritized queue interface wrapper for heaps.
Declaration of extended graph algorithms.
bool isConnected(const Graph &G)
Returns true iff G is connected.
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()
The namespace for all OGDF objects.