Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MinSteinerTreeDualAscent.h
Go to the documentation of this file.
1
33#pragma once
34
37
38// enable this to print log
39//#define OGDF_DUAL_ASCENT_LOGGING
40
41namespace ogdf {
42
52template<typename T>
54private:
55 const T MAX_VALUE = std::numeric_limits<T>::max();
56
60
64
67
69
70 // components for the Steiner graph
72
77 void init();
78
87 bool isTerminal(const node v, bool rootIsTerminal) const;
88
95 int findActiveComponent(node* terminal) const;
96
103 int findComponent(const node v) const;
104
111 List<edge>* computeCutSet(const node v) const;
112
122 bool isActiveComponent(const node v) const;
123
128 void updateComponents();
129
130protected:
146 T computeSteinerTree(const EdgeWeightedGraph<T>& G, const List<node>& terminals,
148};
149
150template<typename T>
152 // local auxilary lists
153 List<node> nodes;
154 m_pOrigGraph->allNodes(nodes);
155 List<edge> edges;
156 m_pOrigGraph->allEdges(edges);
157
158 // create directed graph
159 // and initialize slack variables
160 m_diGraph.createEmpty(*m_pOrigGraph);
161 m_diGraph.clear();
162 m_edgeSlacks.init(m_diGraph);
163 m_origMapping.init(m_diGraph);
164
165 // create resulting Steiner tree
166 m_steinerGraph.createEmpty(m_diGraph);
167 m_steinerGraph.clear();
168 m_componentMapping.init(m_steinerGraph);
169
170 // TODO: Better choices possible?
171 m_rootTerminal = m_pTerminals->chooseElement();
172
173 for (node v : nodes) {
174 node w = m_diGraph.newNode(v);
175 m_steinerGraph.newNode(w);
176 }
177
178 for (edge e : edges) {
179 node source = m_diGraph.copy(e->source());
180 node target = m_diGraph.copy(e->target());
181 edge copiedEdgeS = m_diGraph.newEdge(source, target);
182 edge copiedEdgeT = m_diGraph.newEdge(target, source);
183 m_edgeSlacks[copiedEdgeS] = m_edgeSlacks[copiedEdgeT] = m_pOrigGraph->weight(e);
184 m_origMapping[copiedEdgeS] = m_origMapping[copiedEdgeT] = e;
185 }
186 updateComponents();
187
188#ifdef OGDF_DUAL_ASCENT_LOGGING
189 std::cout << "directed graph has " << m_diGraph.numberOfNodes() << " nodes "
190 << "and " << m_diGraph.numberOfEdges() << " edges." << std::endl
191 << "root terminal is node " << m_rootTerminal << "." << std::endl;
192#endif
193}
194
195template<typename T>
197 OGDF_ASSERT(v->graphOf() == &m_steinerGraph);
198 OGDF_ASSERT(m_componentMapping[v] > -1);
199 return m_componentMapping[v];
200}
201
202template<typename T>
204 strongComponents(m_steinerGraph, m_componentMapping);
205}
206
207template<typename T>
209 OGDF_ASSERT(v->graphOf() == &m_steinerGraph);
210
211 node w = m_diGraph.original(m_steinerGraph.original(v));
212 return (m_rootTerminal != w || rootIsTerminal) && (*m_pIsTerminal)[w];
213}
214
215template<typename T>
217 int result = -1;
218
219#ifdef OGDF_DUAL_ASCENT_LOGGING
220 std::cout << " searching for active component.." << std::endl;
221#endif
222
224 for (auto it = m_pTerminals->begin(); it != m_pTerminals->end() && result == -1; it++) {
225 if (*it != m_rootTerminal) {
226 node v = m_steinerGraph.copy(m_diGraph.copy(*it));
227 int candidate = findComponent(v);
228 if (!checked[candidate]) {
229 checked[candidate] = true;
230 bool isRoot = isActiveComponent(v);
231
232 if (isRoot) {
233 result = candidate;
234 *terminal = *it;
235#ifdef OGDF_DUAL_ASCENT_LOGGING
236 std::cout << " active component found: component " << result << ", terminal "
237 << *terminal << std::endl;
238#endif
239 }
240 }
241 }
242 }
243
244#ifdef OGDF_DUAL_ASCENT_LOGGING
245 if (result == -1) {
246 std::cout << " could not find an active component" << std::endl;
247 }
248#endif
249
250 return result;
251}
252
253template<typename T>
255 OGDF_ASSERT(root->graphOf() == &m_steinerGraph);
256
257 // establish "weakly connected" component of v (non-standard definition, see paper for details)
258 NodeArray<bool> visited(m_steinerGraph, false);
260 visited[root] = true;
261
263 queue.pushBack(root);
264
265 // determine all nodes connected to root
266 // meaning all nodes from which a directed path to root exists
267 while (!queue.empty()) {
268 node v = queue.popFrontRet();
269 weakComp.pushBack(v);
270 for (adjEntry adj : v->adjEntries) {
271 edge e = adj->theEdge();
272 node w = e->source();
273 if (!visited[w]) {
274 visited[w] = true;
275 queue.pushBack(w);
276 }
277 }
278 }
279
280 // identify (incoming) cut edges
281 List<edge>* result = new List<edge>();
282
283 for (node v : weakComp) {
284 node w = m_steinerGraph.original(v);
285 for (adjEntry adj : w->adjEntries) {
286 edge e = adj->theEdge();
287 if (!visited[m_steinerGraph.copy(e->source())]) {
288 result->pushBack(e);
289 OGDF_ASSERT(m_steinerGraph.copy(e) == nullptr);
290 }
291 }
292 }
293 return result;
294}
295
296template<typename T>
298 OGDF_ASSERT(source->graphOf() == &m_steinerGraph);
299
300 int comp = findComponent(source);
301 bool danglingTerminalFound = false;
302 bool hasTerminal = false;
303
304#ifdef OGDF_DUAL_ASCENT_LOGGING
305 std::cout << " checking whether component of node " << source << " is active.. " << std::endl;
306 std::cout << " component has id " << comp << std::endl;
307#endif
308
310 NodeArray<bool> visited(m_steinerGraph, false);
311 queue.pushBack(source);
312 visited[source] = true;
313#ifdef OGDF_DUAL_ASCENT_LOGGING
314 while (!queue.empty()) {
315#else
316 while (!queue.empty() && !danglingTerminalFound) {
317#endif
318 node v = queue.popFrontRet();
319 hasTerminal |= isTerminal(v, false) && findComponent(v) == comp;
320 for (adjEntry adj : v->adjEntries) {
321 edge e = adj->theEdge();
322 node w = e->source();
323 if (!visited[w]) {
324 danglingTerminalFound |= isTerminal(w, true) && findComponent(w) != comp;
325 visited[w] = true;
326 queue.pushBack(w);
327 }
328 }
329 }
330
331#ifdef OGDF_DUAL_ASCENT_LOGGING
332 if (hasTerminal) {
333 std::cout << " component includes a terminal" << std::endl;
334 }
336 std::cout << " component has dangling terminal" << std::endl;
337 }
339 std::cout << " component is active!" << std::endl;
340 }
341#endif
343}
344
345template<typename T>
347 const List<node>& terminals, const NodeArray<bool>& isTerminal,
349#ifdef OGDF_DUAL_ASCENT_LOGGING
350 std::cout << "MinSteinerTreeDualAscent called." << std::endl;
351 std::cout << "terminals are: ";
352
353 for (node v : terminals) {
354 std::cout << v << " ";
355 }
356 std::cout << std::endl;
357#endif
358 m_pOrigGraph = &G;
359 m_pTerminals = &terminals;
360 m_pIsTerminal = &isTerminal;
361
362 init();
363
364 // create resulting Steiner tree
366 finalSteinerTree->createEmpty(*m_pOrigGraph);
367 T result = 0;
368
369 int comp = -1;
370 node terminal = nullptr;
371
372#ifdef OGDF_DUAL_ASCENT_LOGGING
373 std::cout << "main loop starting.." << std::endl;
374#endif
375 while ((comp = findActiveComponent(&terminal)) != -1) {
376 // if active comonents exists we
377 // have one of its terminals
378 OGDF_ASSERT(terminal != nullptr);
379
380 // find minimal cut edge
381 List<edge>* cutEdges = computeCutSet(m_steinerGraph.copy(m_diGraph.copy(terminal)));
382 edge minEdge = nullptr;
383 T minSlack = MAX_VALUE;
384#ifdef OGDF_DUAL_ASCENT_LOGGING
385 std::cout << " cut edges:";
386#endif
387 for (edge e : *cutEdges) {
388#ifdef OGDF_DUAL_ASCENT_LOGGING
389 std::cout << " " << e;
390#endif
391 if (m_edgeSlacks[e] < MAX_VALUE || minEdge == nullptr) {
392 minEdge = e;
393 minSlack = m_edgeSlacks[e];
394 }
395 }
396#ifdef OGDF_DUAL_ASCENT_LOGGING
397 std::cout << std::endl << " next edge: " << minEdge << std::endl;
398#endif
399 OGDF_ASSERT(minEdge != nullptr);
400
401 // update slack variables
402 for (edge e : *cutEdges) {
403 m_edgeSlacks[e] -= minSlack;
404 }
405 delete cutEdges;
406
407 // insert edge
408 m_steinerGraph.newEdge(minEdge);
409 updateComponents();
410
411 // insert edge into final Steiner tree
412 edge origEdge = m_origMapping[minEdge];
413 T cost = m_pOrigGraph->weight(origEdge);
414 if (finalSteinerTree->copy(origEdge->source()) == nullptr) {
415 finalSteinerTree->newNode(origEdge->source());
416 }
417 if (finalSteinerTree->copy(origEdge->target()) == nullptr) {
418 finalSteinerTree->newNode(origEdge->target());
419 }
420 if (finalSteinerTree->copy(origEdge) == nullptr) {
421 finalSteinerTree->newEdge(origEdge, cost);
422 result += cost;
423 }
424 }
425
426#ifdef OGDF_DUAL_ASCENT_LOGGING
427 std::cout << "removing expendable edges" << std::endl;
428#endif
429 result -= this->pruneAllDanglingSteinerPaths(*finalSteinerTree, *m_pIsTerminal);
430 result -= this->removeCyclesFrom(*finalSteinerTree, *m_pIsTerminal);
431
432#ifdef OGDF_DUAL_ASCENT_LOGGING
433 std::cout << "algorithm terminated." << std::endl;
434#endif
435 return result;
436}
437
438}
Extends the GraphCopy concept to weighted graphs.
Declaration of ogdf::MinSteinerTreeModule.
Class for adjacency list elements.
Definition Graph_d.h:79
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
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
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
Indexed arrays using hashing for element access.
Definition HashArray.h:93
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
void clear()
Removes all elements from the list.
Definition List.h:1610
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1531
Dual ascent heuristic for the minimum Steiner tree problem.
GraphCopy m_steinerGraph
the to-be constructed "almost" Steiner tree
GraphCopy m_diGraph
the directed graph
void init()
Intializes all relevant variables.
NodeArray< int > m_componentMapping
maps each node to its component
List< edge > * computeCutSet(const node v) const
Returns all incoming cut edges of the component of v.
bool isTerminal(const node v, bool rootIsTerminal) const
Returns whether this node is a terminal.
EdgeArray< T > m_edgeSlacks
slack variables for each directed edge representing the adjusted weight
T computeSteinerTree(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
Creates a minimum Steiner tree given a weighted graph and a list of terminals.
void updateComponents()
Re-establishes all strongly connected components for the Steiner graph.
const List< node > * m_pTerminals
list of terminals passed to the module
EdgeArray< edge > m_origMapping
maps each directed edge to its undirected original
const EdgeWeightedGraph< T > * m_pOrigGraph
original graph passed to the module
int findActiveComponent(node *terminal) const
Searches for the next active component.
EdgeArray< bool > m_edgeInclusions
stores the resulting Steiner tree
const NodeArray< bool > * m_pIsTerminal
terminal incidence vector passed to the module
int findComponent(const node v) const
Returns the component of node v.
bool isActiveComponent(const node v) const
Determines whether a strongly connected component is active (paper says "is root component").
Serves as an interface for various methods to compute or approximate minimum Steiner trees on undirec...
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
int strongComponents(const Graph &G, NodeArray< int > &component)
Computes the strongly connected components of the digraph G.
#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.