1/** \file
2 * \brief Implementation of the 2(1-1/l)-approximation algorithm for
3 * the minimum Steiner tree problem by Matsuyama and Takahashi
4 *
5 * \author Matthias Woste
6 *
7 * \par License:
8 * This file is part of the Open Graph Drawing Framework (OGDF).
9 *
10 * \par
11 * Copyright (C)<br>
12 * See README.md in the OGDF root directory for details.
13 *
14 * \par
15 * This program is free software; you can redistribute it and/or
16 * modify it under the terms of the GNU General Public License
17 * Version 2 or 3 as published by the Free Software Foundation;
18 * see the file LICENSE.txt included in the packaging of this file
19 * for details.
20 *
21 * \par
22 * This program is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 * GNU General Public License for more details.
26 *
27 * \par
28 * You should have received a copy of the GNU General Public
29 * License along with this program; if not, see
30 * http://www.gnu.org/copyleft/gpl.html
31 */
32
33#pragma once
34
35#include <ogdf/basic/List.h>
36#include <ogdf/graphalg/steiner_tree/EdgeWeightedGraphCopy.h>
37#include <ogdf/module/MinSteinerTreeModule.h>
38#include <ogdf/basic/extended_graph_alg.h>
39
40namespace ogdf {
41
42/**
43 * This class implements the minimum Steiner tree 2-approximation algorithm
44 * by Takahashi and Matsuyama with improvements proposed by Poggi de Aragao et al.
45 *
46 * @ingroup ga-steiner
47 *
48 * This implementation is based on:
49 *
50 * (H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs, Math. Japonica,
51 * volume 24, number 6, pages 573-577, 1980)
52 *
53 * (M. Poggi de Aragao, C. Riberiro, E. Uchoa, R. Werneck, Hybrid Local Search for the Steiner Problem in Graphs,
54 * MIC 2001, pages 429-433, 2001)
55 */
56template<typename T>
57class MinSteinerTreeTakahashi: public MinSteinerTreeModule<T> {
58public:
59 MinSteinerTreeTakahashi() { }
60
61 virtual ~MinSteinerTreeTakahashi() { }
62
63 /**
64 * An extended call method with specific start node.
65 *
66 * You should only call this method when there is more than one terminal.
67 *
68 * @see MinSteinerTreeModule::call
69 */
70 virtual T call(const EdgeWeightedGraph<T> &G,
71 const List<node> &terminals,
72 const NodeArray<bool> &isTerminal,
73 EdgeWeightedGraphCopy<T> *&finalSteinerTree,
74 const node startNode)
75 {
76 return call(G, terminals, isTerminal, isTerminal, finalSteinerTree, startNode);
77 }
78
79 /**
80 * An extended call method with intermediate and final (original) terminals.
81 *
82 * You should only call this method when there is more than one terminal.
83 *
84 * @see MinSteinerTreeModule::call
85 */
86 virtual T call(const EdgeWeightedGraph<T> &G,
87 const List<node> &terminals,
88 const NodeArray<bool> &isTerminal,
89 const NodeArray<bool> &isOriginalTerminal,
90 EdgeWeightedGraphCopy<T> *&finalSteinerTree)
91 {
92 return call(G, terminals, isTerminal, isOriginalTerminal, finalSteinerTree, terminals.front());
93 }
94
95 using MinSteinerTreeModule<T>::call;
96
97 /*!
98 * An extended call method with intermediate and final (original) terminal nodes
99 * and a specific start node.
100 *
101 * You should only call this method when there is more than one terminal.
102 *
103 * @see MinSteinerTreeModule::call
104 */
105 virtual T call(const EdgeWeightedGraph<T> &G,
106 const List<node> &terminals,
107 const NodeArray<bool> &isTerminal,
108 const NodeArray<bool> &isOriginalTerminal,
109 EdgeWeightedGraphCopy<T> *&finalSteinerTree,
110 const node startNode);
111
112protected:
113 virtual T computeSteinerTree(
114 const EdgeWeightedGraph<T> &G,
115 const List<node> &terminals,
116 const NodeArray<bool> &isTerminal,
117 EdgeWeightedGraphCopy<T> *&finalSteinerTree) override
118 {
119 return call(G, terminals, isTerminal, isTerminal, finalSteinerTree, terminals.front());
120 }
121
122 /*!
123 * Modified Dijkstra algorithm to solve the Minimum Steiner Tree problem
124 * @param wG the original graph
125 * @param intermediateTerminalSpanningTree intermediate terminal spanning tree
126 * @param s source node to start from
127 * @param numberOfTerminals number of terminal nodes
128 * @param isTerminal terminal incivende vector
129 * @return the weight of the intermediateTerminalSpanningTree
130 */
131 T terminalDijkstra(const EdgeWeightedGraph<T> &wG,
132 EdgeWeightedGraphCopy<T> &intermediateTerminalSpanningTree,
133 const node s,
134 int numberOfTerminals,
135 const NodeArray<bool> &isTerminal);
136};
137
138template<typename T>
139T MinSteinerTreeTakahashi<T>::call(const EdgeWeightedGraph<T> &G,
140 const List<node> &terminals,
141 const NodeArray<bool> &isTerminal,
142 const NodeArray<bool> &isOriginalTerminal,
143 EdgeWeightedGraphCopy<T> *&finalSteinerTree,
144 const node startNode)
145{
146 OGDF_ASSERT(isConnected(G));
147
148 EdgeWeightedGraphCopy<T> terminalSpanningTree;
149 terminalSpanningTree.createEmpty(G);
150 terminalDijkstra(G, terminalSpanningTree, startNode, terminals.size(), isTerminal);
151
152 finalSteinerTree = new EdgeWeightedGraphCopy<T>(G);
153 for(node u : G.nodes) {
154 if (!terminalSpanningTree.copy(u)) {
155 finalSteinerTree->delNode(finalSteinerTree->copy(u));
156 }
157 }
158
159 T mstWeight = makeMinimumSpanningTree(*finalSteinerTree, finalSteinerTree->edgeWeights());
160 mstWeight -= MinSteinerTreeModule<T>::pruneAllDanglingSteinerPaths(*finalSteinerTree, isOriginalTerminal);
161
162 return mstWeight;
163}
164
165template<typename T>
166T MinSteinerTreeTakahashi<T>::terminalDijkstra(const EdgeWeightedGraph<T> &wG,
167 EdgeWeightedGraphCopy<T> &intermediateTerminalSpanningTree, const node s, int numberOfTerminals,
168 const NodeArray<bool> &isTerminal)
169{
170 NodeArray<edge> predecessor(wG, nullptr);
171 NodeArray<T> distance(wG, std::numeric_limits<T>::max());
172 distance[s] = 0;
173 NodeArray<T> bestDistance(wG, std::numeric_limits<T>::max());
174 bestDistance[s] = 0;
175 NodeArray<bool> isInQueue(wG, true);
176
177 PrioritizedMapQueue<node, T> queue(wG); //priority queue
178 for (node v : wG.nodes) {
179 queue.push(v, distance[v]);
180 }
181
182 T mstWeight = 0;
183 int terminalsFound = 1;
184 while (!queue.empty() && terminalsFound < numberOfTerminals) {
185 node v = queue.topElement();
186 queue.pop();
187 isInQueue[v] = false;
188 bestDistance[v] = distance[v];
189 if (isTerminal[v]
190 && distance[v] > 0) {
191 ++terminalsFound;
192 // insert path from new node to old tree
193 node tmpT = intermediateTerminalSpanningTree.newNode(v);
194 while (distance[v] > 0) {
195 distance[v] = 0;
196 queue.push(v, distance[v]);
197 isInQueue[v] = true;
198 const edge e = predecessor[v];
199 OGDF_ASSERT(e);
200 const node w = e->opposite(v);
201 node tmpS = intermediateTerminalSpanningTree.copy(w);
202 if (!tmpS) {
203 tmpS = intermediateTerminalSpanningTree.newNode(w);
204 }
205 edge tmpE;
206 if (e->target() == v) {
207 tmpE = intermediateTerminalSpanningTree.newEdge(tmpS, tmpT, wG.weight(e));
208 } else {
209 tmpE = intermediateTerminalSpanningTree.newEdge(tmpT, tmpS, wG.weight(e));
210 }
211 mstWeight += wG.weight(e);
212 intermediateTerminalSpanningTree.setEdge(e, tmpE);
213 tmpT = tmpS;
214 v = w;
215 }
216 } else { // !isTerminal[v] || distance[v] == 0
217 for(adjEntry adj : v->adjEntries) {
218 const node w = adj->twinNode();
219 const edge e = adj->theEdge();
220 if (distance[w] > distance[v] + wG.weight(e)
221 && bestDistance[w] >= distance[w]) {
222 distance[w] = distance[v] + wG.weight(e);
223 if (!isInQueue[w]) {
224 queue.push(w, distance[w]);
225 isInQueue[w] = true;
226 } else {
227 queue.decrease(w, distance[w]);
228 }
229 predecessor[w] = e;
230 }
231 }
232 }
233 }
234 return mstWeight;
235}
236
237}
238