Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
SteinerTreeLowerBoundDualAscent.h
Go to the documentation of this file.
1
32#pragma once
33
35#include <ogdf/basic/Math.h>
38
39namespace ogdf {
40namespace steiner_tree {
41
43template<typename T>
45 struct TerminalData;
46
51
62
70
73 auto it = m_terminals.begin();
74 auto bestIt = it;
75 for (; it != m_terminals.end(); ++it) {
76 if ((*it).cut.size() < (*bestIt).cut.size()) {
77 bestIt = it;
78 }
79 }
80
81 return bestIt;
82 }
83
87 if (t == m_root) {
88 return false;
89 }
90 TerminalData& td = *it;
91 td.inCut[t] = true;
92 td.references.push({t, m_inTerminalCut[t].pushBack(it)});
93 for (adjEntry adj : t->adjEntries) {
94 node w = adj->twinNode();
95 if (!td.inCut[w]) {
96 // not in cut, so check (recursively) if we should add nodes
97 if (m_eps.equal(m_reducedCost[adj], T(0))) {
98 if (!addNode(it, w)) { // recurse
99 return false;
100 }
101 } else {
102 td.cutIterators[adj] = td.cut.pushBack(adj);
103 }
104 }
105 }
106
107 // delete arcs that are inside the cut
108 for (adjEntry adj : t->adjEntries) {
109 node w = adj->twinNode();
110 if (td.inCut[w]) {
111 auto& cutAdjIt = td.cutIterators[adj->twin()];
112 if (cutAdjIt != td.cut.end()) {
113 td.cut.del(cutAdjIt);
114 cutAdjIt = nullptr;
115 }
116 }
117 }
118
119 return true;
120 }
121
123 if (!(*it).inCut[w]) {
124 if (!addNode(it, w)) {
125 return false;
126 }
127 }
128 return true;
129 }
130
132 for (auto ref : (*it).references) {
133 m_inTerminalCut[ref.v].del(ref.it);
134 }
135
136 m_terminals.del(it);
137 }
138
145 void extendCut(adjEntry adj) {
147 node v = adj->theNode();
148 node w = adj->twinNode();
149 for (auto it = m_inTerminalCut[v].begin(); it.valid();) {
150 if (!addNodeChecked(*it, w)) {
151 auto nextIt = it;
152 ++nextIt;
154 it = nextIt;
155 } else {
156 ++it;
157 }
158 }
159 }
160
163 OGDF_ASSERT(!td.cut.empty());
164 T cost = std::numeric_limits<T>::max();
165 for (adjEntry adj : td.cut) {
166 Math::updateMin(cost, m_reducedCost[adj]);
167 }
168 OGDF_ASSERT(cost > 0);
169 return cost;
170 }
171
173 void update(TerminalData& td, T delta) {
174 // reduce costs
176 for (adjEntry adj : td.cut) {
177 m_reducedCost[adj] -= delta;
178 OGDF_ASSERT(m_eps.geq(m_reducedCost[adj], T(0)));
179 if (m_eps.leq(m_reducedCost[adj], T(0))) {
180 zeroed.push(adj);
181 }
182 }
183 m_lower += delta;
184
185 // extend
186 for (adjEntry adj : zeroed) {
187 extendCut(adj);
188 }
189 }
190
191public:
193 LowerBoundDualAscent(const EdgeWeightedGraph<T>& graph, const List<node>& terminals, node root,
194 double eps = 1e-6)
195 : m_eps(eps)
196 , m_lower(0)
197 , m_graph(graph)
198 , m_root(nullptr)
201 for (edge e : graph.edges) {
202 m_reducedCost[e->adjSource()] = m_reducedCost[e->adjTarget()] = graph.weight(e);
203 }
204
205 for (node t : terminals) {
206 if (t == root) {
207 m_root = root;
208 } else {
209 auto it = m_terminals.pushBack(TerminalData(m_graph, t));
210 if (!addNode(it, t)) {
212 }
213 }
214 }
215 OGDF_ASSERT(m_root != nullptr);
216 }
217
220 double eps = 1e-6)
221 : LowerBoundDualAscent(graph, terminals, terminals.front(), eps) { }
222
224 void compute() {
225 while (!m_terminals.empty()) {
226 auto it = chooseTerminal();
227 TerminalData& td = *it;
229 }
230 }
231
234 T reducedCost(adjEntry adj) const { return m_reducedCost[adj]; }
235
237 T get() const { return m_lower; }
238};
239}
240
251template<typename T>
254
255 T compute(const EdgeWeightedGraph<T>& graph, const List<node>& terminals, node root) {
256 steiner_tree::LowerBoundDualAscent<T> alg(graph, terminals, root);
257 alg.compute();
258 return alg.get();
259 }
260
261 void compute(const EdgeWeightedGraph<T>& graph, const List<node>& terminals, node root,
263 OGDF_ASSERT(isConnected(graph));
264
265 // compute first
266 steiner_tree::LowerBoundDualAscent<T> alg(graph, terminals, root);
267 alg.compute();
268
269 // generate the auxiliary network
271 NodeArray<node> copy(graph);
274
275 for (node v : graph.nodes) {
276 copy[v] = network.newNode();
277 }
278 for (edge e : graph.edges) {
279 edge uv = network.newEdge(copy[e->source()], copy[e->target()]);
280 edge vu = network.newEdge(copy[e->target()], copy[e->source()]);
281 weights[uv] = alg.reducedCost(e->adjTarget());
282 weights[vu] = alg.reducedCost(e->adjSource());
283 orig[uv] = orig[vu] = e;
284 }
285
286 // compute shortest path tree on network starting from root
287 Dijkstra<T> sssp;
288 NodeArray<edge> pred;
289 NodeArray<T> distance;
290 sssp.call(network, weights, copy[root], pred, distance, true);
291
292 // set all lower bounds to global lower bound
293 lbNodes.init(graph, alg.get());
294 lbEdges.init(graph, alg.get());
296
297 // add cost of path root -> v
298 for (node v : graph.nodes) {
299 lbNodes[v] += distance[copy[v]];
300 }
301 // add cost of path root -> e
302 for (edge a : network.edges) {
303 lbArcs[a] += distance[a->source()] + weights[a];
304 }
305
306 // to find the (reduced) distance from v / e to any (non-root) terminal,
307 // hence compute (directed) Voronoi regions
308 network.reverseAllEdges();
309
311 for (node t : terminals) {
312 if (t != root) {
314 }
315 }
316 sssp.call(network, weights, nonRootTerminals, pred, distance, true);
317
318 // add cost of path v -> any terminal
319 for (node v : graph.nodes) {
320 lbNodes[v] += distance[copy[v]];
321 }
322 // add cost of path e -> any terminal
323 for (edge a : network.edges) {
324 lbArcs[a] += distance[a->source()]; // the former target is now the source
325
326 // both lower bounds must be larger than the upper bound, so take the minimum
328 }
329 }
330
331public:
333 void setRepetitions(int num) { m_repetitions = num; }
334
336 T call(const EdgeWeightedGraph<T>& graph, const List<node>& terminals) {
337 T lb(0);
338 int i = 0;
339 for (node root : terminals) {
340 Math::updateMax(lb, compute(graph, terminals, root));
341 if (++i >= m_repetitions) {
342 break;
343 }
344 }
345 return lb;
346 }
347
352 void call(const EdgeWeightedGraph<T>& graph, const List<node>& terminals, NodeArray<T>& lbNodes,
354 if (m_repetitions <= 1) {
355 // catch this special case to avoid copying
356 compute(graph, terminals, terminals.front(), lbNodes, lbEdges);
357 } else {
358 lbNodes.init(graph, 0);
359 lbEdges.init(graph, 0);
360 int i = 0;
361 for (node root : terminals) {
362 NodeArray<T> nodes;
363 EdgeArray<T> edges;
364 compute(graph, terminals, root, nodes, edges);
365 for (node v : graph.nodes) {
366 Math::updateMax(lbNodes[v], nodes[v]);
367 }
368 for (edge e : graph.edges) {
369 Math::updateMax(lbEdges[e], edges[e]);
370 }
371 if (++i >= m_repetitions) {
372 break;
373 }
374 }
375 }
376 }
377};
378}
Declaration of class EdgeWeightedGraph.
Compare floating point numbers with epsilons and integral numbers with normal compare operators.
Mathematical Helpers.
Class for adjacency list elements.
Definition Graph_d.h:79
node twinNode() const
Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
Definition Graph_d.h:112
node theNode() const
Returns the node whose adjacency list contains this element.
Definition Graph_d.h:103
Dynamic arrays indexed with adjacency entries.
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
Dijkstra's single source shortest path algorithm.
Definition Dijkstra.h:53
void call(const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false, node target=nullptr, T maxLength=std::numeric_limits< T >::max())
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths a...
Definition Dijkstra.h:246
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
T weight(const edge e) const
std::enable_if< std::is_integral< T >::value, bool >::type leq(const T &x, const T &y) const
Compare if x is LEQ than y for integral types.
Definition EpsilonTest.h:83
std::enable_if< std::is_integral< T >::value, bool >::type geq(const T &x, const T &y) const
Compare if x is GEQ to y for integral types.
std::enable_if< std::is_integral< T >::value, bool >::type equal(const T &x, const T &y) const
Compare if x is EQUAL to y for integral types.
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition Graph_d.h:589
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition Graph_d.h:592
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1531
Encapsulates a pointer to a list element.
Definition List.h:103
const_reference front() const
Returns a const reference to the first element.
Definition List.h:289
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Implementation of a dual-ascent-based lower bound heuristic for Steiner tree problems.
T call(const EdgeWeightedGraph< T > &graph, const List< node > &terminals)
Calls the algorithm and returns the lower bound.
void setRepetitions(int num)
Sets the number of repeated calls to the lower bound algorithm (runs with different roots)
void compute(const EdgeWeightedGraph< T > &graph, const List< node > &terminals, node root, NodeArray< T > &lbNodes, EdgeArray< T > &lbEdges)
void call(const EdgeWeightedGraph< T > &graph, const List< node > &terminals, NodeArray< T > &lbNodes, EdgeArray< T > &lbEdges)
Compute the lower bounds under the assumption nodes or edges are included in the solution.
T compute(const EdgeWeightedGraph< T > &graph, const List< node > &terminals, node root)
Computes lower bounds for minimum Steiner tree instances.
bool addNode(ListIterator< TerminalData > &it, node t)
Adds a node to the cut and add neighbors recursively.
T findCheapestCutArcCost(const TerminalData &td) const
Finds the cheapest arc in cut and returns its cost.
T reducedCost(adjEntry adj) const
Returns the reduced cost of the arc given by adj.
void removeTerminalData(ListIterator< TerminalData > it)
bool addNodeChecked(ListIterator< TerminalData > &it, node w)
ListIterator< TerminalData > chooseTerminal()
Finds the terminal with the smallest cut arc set (of the last iteration)
LowerBoundDualAscent(const EdgeWeightedGraph< T > &graph, const List< node > &terminals, double eps=1e-6)
Initializes the algorithm (and takes the first terminal as root)
LowerBoundDualAscent(const EdgeWeightedGraph< T > &graph, const List< node > &terminals, node root, double eps=1e-6)
Initializes the algorithm.
NodeArray< List< ListIterator< TerminalData > > > m_inTerminalCut
Mapping of nodes to the cuts they are in.
void extendCut(adjEntry adj)
Assumes that the reduced cost of arc adj is zeroed and hence updates (in relevant cuts) the set of ar...
void update(TerminalData &td, T delta)
Updates reduced costs and cut data.
Implementation of Dijkstra's single source shortest path algorithm.
bool isConnected(const Graph &G)
Returns true iff G is connected.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
void updateMin(T &min, const T &newValue)
Stores the minimum of min and newValue in min.
Definition Math.h:98
void updateMax(T &max, const T &newValue)
Stores the maximum of max and newValue in max.
Definition Math.h:90
The namespace for all OGDF objects.