Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
FullComponentGeneratorDreyfusWagnerWithoutMatrix.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Hashing.h>
35#include <ogdf/basic/Math.h>
39
40namespace ogdf {
41namespace steiner_tree {
42
54template<typename T>
59
68
70
71 public:
79 // copy nodes and edges
80 for (node v : m_original.nodes) {
81 node vCopy = m_copy.newNode();
84 }
85 for (edge e : m_original.edges) {
86 edge eCopy =
87 m_copy.newEdge(copy(e->source()), copy(e->target()), m_original.weight(e));
89 }
90
91 // set terminals
92 for (node v : terminals) {
93 m_isTerminal[copy(v)] = true;
94 }
95
96 // initialize source node and its edges to every other node
97 m_source = m_copy.newNode();
98 for (node w : m_original.nodes) {
99 m_copy.newEdge(m_source, copy(w), std::numeric_limits<T>::max());
100 }
101 }
102
104 node copy(node v) const {
105 OGDF_ASSERT(v->graphOf() == &m_original);
106 return m_copyOfNode[v];
107 }
108
110 node original(node v) const {
111 OGDF_ASSERT(v->graphOf() == &m_copy);
112 return m_origOfNode[v];
113 }
114
116 edge original(edge e) const {
117 OGDF_ASSERT(e->graphOf() == &m_copy);
118 return m_origOfEdge[e];
119 }
120
122 node source() const { return m_source; }
123
125 const EdgeWeightedGraph<T>& graph() const { return m_copy; }
126
128 const NodeArray<bool>& terminalArray() const { return m_isTerminal; }
129
131 T weight(edge e) const {
132 OGDF_ASSERT(e->graphOf() == &m_copy);
133 return m_copy.weight(e);
134 }
135
137 void setWeight(edge e, T value) {
138 OGDF_ASSERT(e->graphOf() == &m_copy);
139 m_copy.setWeight(e, value);
140 }
141 };
142
145
147 struct DWMData {
151
153
154 explicit DWMData(T _cost = std::numeric_limits<T>::max()) : cost(_cost) { }
155
157 void invalidate() {
158 edges.clear();
159 subgraphs.clear();
160 }
161
163 bool valid() const { return cost == 0 || !(edges.empty() && subgraphs.empty()); }
164
166 void add(const DWMData* other) {
167 if (valid()) {
168 if (other->valid()) {
169 subgraphs.push(other);
170 } else {
171 invalidate();
172 }
173 }
174 cost += other->cost;
175 }
176
178 void clear() {
179 invalidate();
180 cost = 0; // make it valid again
181 }
182
184 void add(edge e, T c) {
185 if (valid()) {
186 edges.push(e);
187 }
188 cost += c;
189 }
190 };
191
193 struct DWMSplit {
194 T cost = std::numeric_limits<T>::max();
195 const DWMData* subgraph1 = nullptr;
196 const DWMData* subgraph2 = nullptr;
197
199 void set(const DWMData* s1, const DWMData* s2) {
200 subgraph1 = s1;
201 subgraph2 = s2;
202 cost = s1->cost + s2->cost;
203 }
204 };
205
207 class SortedNodeListHashFunc;
208
211
213 const DWMData* dataOf(const List<node>& key) const {
214 OGDF_ASSERT(key.size() > 1);
215 OGDF_ASSERT(m_map.member(key));
216 return &m_map.lookup(key)->info();
217 }
218
220 T costOf(const List<node>& key) const {
221 OGDF_ASSERT(key.size() > 1);
222 return dataOf(key)->cost;
223 }
224
226 bool safeIfSumSmaller(const T summand1, const T summand2, const T compareValue) const {
227#ifdef OGDF_FULL_COMPONENT_GENERATION_ALWAYS_SAFE
228 return summand1 + summand2 < compareValue;
229#else
230 return summand1 < std::numeric_limits<T>::max() && summand2 < std::numeric_limits<T>::max()
232#endif
233 }
234
246 static void sortedInserter(node w, List<node>& list, bool& inserted, node newNode) {
247 if (!inserted && w->index() > newNode->index()) {
248 list.pushBack(newNode);
249 inserted = true;
250 }
251 list.pushBack(w);
252 }
253
256 bool inserted = false;
257 m_terminalSubset.forEachMember([&](node w) { sortedInserter(w, newSubset, inserted, v); });
258 if (!inserted) {
259 newSubset.pushBack(v);
260 }
261 }
262
265 const SubsetEnumerator<node>& subset, node v) const {
266 bool insertedIntoSubset = false;
267 bool insertedIntoComplement = false;
268 // Interestingly std::bind is much slower than using lambdas (at least on g++ 6.3)
269 subset.forEachMemberAndNonmember(
272 if (!insertedIntoSubset) {
273 newSubset.pushBack(v);
274 }
276 newComplement.pushBack(v);
277 }
278 }
279
286 OGDF_ASSERT(v->graphOf() == &m_G);
287 OGDF_ASSERT(split[v].subgraph1 == nullptr);
288 OGDF_ASSERT(split[v].subgraph2 == nullptr);
289
290 DWMSplit& best = split[v];
291 for (subset.begin(1, subset.numberOfMembersAndNonmembers() / 2); subset.valid();
292 subset.next()) {
295
298 }
299 }
300 }
301
303 template<typename CONTAINER>
305 OGDF_ASSERT(m_terminalSubset.size() >= 2);
306
307 List<node> terminals;
308 m_terminalSubset.list(terminals);
309 SubsetEnumerator<node> subset(terminals); // done here because of linear running time
311
312 // update auxiliary graph
313 updateAuxGraph(split, subset, costOf(terminals));
314
315 // compute shortest-paths tree on graph
316 NodeArray<T> distance;
317 NodeArray<edge> pred;
319 m_auxG.terminalArray(), distance, pred);
320
321 // insert best subtrees
322 insertBestSubtrees(targets, split, pred, distance, terminals);
323 }
324
327 for (node t : m_terminals) {
328 NodeArray<T> distance;
329 NodeArray<edge> pred;
331
332 for (node v : m_G.nodes) {
333 // make key
334 List<node> key;
335 key.pushBack(t);
336 if (v->index() < t->index()) {
337 key.pushFront(v);
338 } else {
339 key.pushBack(v);
340 }
341
342 // insert if not already defined
343 if (!m_map.member(key)) {
344 T dist = distance[v];
345 ArrayBuffer<edge> edges;
346 for (node curr = v; pred[curr] != nullptr; curr = pred[curr]->opposite(curr)) {
347 edges.push(pred[curr]);
348 }
349 m_map.fastInsert(key, DWMData(dist, edges));
350 }
351 }
352 }
353 }
354
357 for (adjEntry adj : m_auxG.source()->adjEntries) {
358 node w = m_auxG.original(adj->twinNode());
359 T cost = oldCost;
360 if (!m_terminalSubset.hasMember(w)) {
361 computeSplit(split, w, subset);
362 cost = split[w].cost;
363 }
364 m_auxG.setWeight(adj->theEdge(), cost);
365 }
366 }
367
370 edge addNewPath(DWMData& result, node curr, const NodeArray<edge>& pred) const {
371 edge e = nullptr;
372 while (curr != m_auxG.source()) {
373 e = pred[curr];
374 OGDF_ASSERT(e != nullptr);
375 node prev = e->opposite(curr);
376 OGDF_ASSERT(prev != curr);
377 if (prev != m_auxG.source()) {
378 edge eO = m_auxG.original(e);
379 OGDF_ASSERT(eO != nullptr);
380 result.add(eO, m_auxG.weight(e));
381 }
382 curr = prev;
383 }
384 OGDF_ASSERT(e != nullptr);
385 OGDF_ASSERT(e->source() == curr);
387
388 return e;
389 }
390
393 OGDF_ASSERT(v->graphOf() == &m_auxG.graph());
394 OGDF_ASSERT(v != m_auxG.source());
395 DWMData best(distance[v]);
396 best.invalidate();
397 m_map.fastInsert(newSubset, best);
398 }
399
402 const NodeArray<edge>& pred, const List<node>& newSubset, const List<node>& terminals) {
403 OGDF_ASSERT(v->graphOf() == &m_auxG.graph());
404 OGDF_ASSERT(v != m_auxG.source());
405 DWMData best(0);
406
407 edge e = addNewPath(best, v, pred);
408 // add best solution so far
409 node tO = m_auxG.original(e->target());
410 if (m_terminalSubset.hasMember(tO)) {
411 best.add(dataOf(terminals));
412 } else {
413 best.add(split[tO].subgraph1);
414 best.add(split[tO].subgraph2);
415 }
416
417 m_map.fastInsert(newSubset, best);
418 }
419
421 template<typename CONTAINER>
423 const NodeArray<edge>& pred, const NodeArray<T>& distance, const List<node>& terminals) {
424 for (node v : targets) {
425 if (!m_terminalSubset.hasMember(v)) {
427 makeKey(newSubset, v);
428
429 if (!m_map.member(newSubset)) { // not already defined
430 node vCopy = m_auxG.copy(v);
431 if (pred[m_auxG.copy(v)] == nullptr) { // path over terminal
433 } else {
434 insertValidBestSubtree(vCopy, split, pred, newSubset, terminals);
435 }
436 }
437 }
438 }
439 }
440
443 T cost(0);
444
445 if (data.valid()) {
446 // add edges
447 for (edge e : data.edges) {
448 node uO = e->source();
449 node vO = e->target();
450 OGDF_ASSERT(uO != nullptr);
451 OGDF_ASSERT(vO != nullptr);
452 node uC = tree.copy(uO);
453 node vC = tree.copy(vO);
454 if (uC == nullptr) {
455 uC = tree.newNode(uO);
456 }
457 if (vC == nullptr) {
458 vC = tree.newNode(vO);
459 }
460 T dist = m_G.weight(e);
461 tree.newEdge(e, dist);
462 cost += dist;
463 }
464
465 // recurse
466 for (const DWMData* subgraph : data.subgraphs) {
467 cost += getSteinerTreeFor(*subgraph, tree);
468 }
469
471 }
472
473 return cost;
474 }
475
476public:
482 const List<node>& terminals, const NodeArray<bool>& isTerminal)
483 : m_G(G)
484 , m_terminals(terminals)
485 , m_isTerminal(isTerminal)
488 , m_map(1 << 22) { // we initially allocate 4MB*sizeof(DWMData) for hashing
489 }
490
491 void call(int restricted) {
495 for (m_terminalSubset.begin(2, restricted - 2); m_terminalSubset.valid();
496 m_terminalSubset.next()) {
498 }
499 // save time by only adding terminals instead of all nodes
500 for (m_terminalSubset.begin(restricted - 1); m_terminalSubset.valid();
501 m_terminalSubset.next()) {
503 }
504 }
505
509 tree.createEmpty(m_G);
510 T cost(getSteinerTreeFor(*dataOf(terminals), tree));
512 return cost;
513 }
514
517 if (tree.empty()) {
518 return false;
519 }
520 for (node v : tree.nodes) {
521 OGDF_ASSERT(v->degree() > 1 || m_isTerminal[tree.original(v)]);
522 if (m_isTerminal[tree.original(v)] // is a terminal
523 && v->degree() > 1) { // but not a leaf
524 return false;
525 }
526 }
527 return true;
528 }
529};
530
531template<typename T>
533 static const unsigned int c_prime = 0x7fffffff; // mersenne prime 2**31 - 1
534 // would be nicer: 0x1fffffffffffffff; // mersenne prime 2**61 - 1
535 const int m_random;
536
537public:
539 SortedNodeListHashFunc() : m_random(randomNumber(2, c_prime - 1)) { }
540
542 unsigned int hash(const List<node>& key) const {
543 unsigned int hash = 0;
544 for (node v : key) {
545 hash = (hash * m_random + v->index()) % c_prime;
546 }
547 return hash;
548 }
549};
550
551}
552}
Extends the GraphCopy concept to weighted graphs.
Declaration of classes used for hashing.
Declaration of ogdf::MinSteinerTreeModule.
A class that allows to enumerate k-subsets.
Mathematical Helpers.
Class for adjacency list elements.
Definition Graph_d.h:79
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
void clear()
Clears the buffer.
Definition ArrayBuffer.h:95
void push(E e)
Puts a new element in the buffer.
bool empty() const
Returns true if the buffer is empty, false otherwise.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
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
node source() const
Returns the source node of the edge.
Definition Graph_d.h:335
Hashing with chaining and table doubling.
Definition Hashing.h:261
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
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1531
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
Definition List.h:1518
static void singleSourceShortestPaths(const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
The default single-source-shortest-paths algorithm.
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 index() const
Returns the (unique) node index.
Definition Graph_d.h:211
Enumerator for k-subsets of a given type.
AuxiliaryGraph(const EdgeWeightedGraph< T > &orig, const List< node > &terminals)
Constructs a copy of the original graph with an added source node having edges to all other nodes.
A generator for restricted full components (for Steiner tree approximations) based on the Dreyfus-Wag...
static void sortedInserter(node w, List< node > &list, bool &inserted, node newNode)
Is being used as a callback to ogdf::SubsetEnumerator's forEach* methods to get the subset plus a cor...
T getSteinerTreeFor(const List< node > &terminals, EdgeWeightedGraphCopy< T > &tree) const
Constructs a Steiner tree for the given set of terminals if it is valid, otherwise an empty tree is r...
void insertValidBestSubtree(node v, const NodeArray< DWMSplit > &split, const NodeArray< edge > &pred, const List< node > &newSubset, const List< node > &terminals)
Inserts the valid best subtree (based on the SSSP computation) into the hash map.
const NodeArray< bool > & m_isTerminal
A reference to the terminal incidence vector.
bool isValidComponent(const EdgeWeightedGraphCopy< T > &tree) const
Checks if a given tree is a valid full component.
const DWMData * dataOf(const List< node > &key) const
Returns a pointer to the relevant data of the partial solution given by key.
void computePartialSolutions(const CONTAINER &targets)
Computes all partial solutions for given m_terminalSubset.
T costOf(const List< node > &key) const
Returns the cost of the partial solution given by key.
edge addNewPath(DWMData &result, node curr, const NodeArray< edge > &pred) const
Adds the shortest path from the source to curr into result.
T getSteinerTreeFor(const DWMData &data, EdgeWeightedGraphCopy< T > &tree) const
Adds edges to construct a Steiner tree from the given data (recursively) if the data is valid.
void makeKey(List< node > &newSubset, List< node > &newComplement, const SubsetEnumerator< node > &subset, node v) const
Makes a list from subset and its complement, each including an correctly inserted node v.
FullComponentGeneratorDreyfusWagnerWithoutMatrix(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal)
The constructor.
void insertBestSubtrees(const CONTAINER &targets, const NodeArray< DWMSplit > &split, const NodeArray< edge > &pred, const NodeArray< T > &distance, const List< node > &terminals)
Inserts the best subtrees into the hash map.
bool safeIfSumSmaller(const T summand1, const T summand2, const T compareValue) const
Checks overflow-safe if summand1 plus summand2 is less than compareValue.
void insertInvalidBestSubtree(node v, const NodeArray< T > &distance, const List< node > &newSubset)
Inserts the invalid best subtree (based on the SSSP computation) into the hash map.
void makeKey(List< node > &newSubset, node v) const
Makes a list from the current terminal subset including an correctly inserted node v.
void updateAuxGraph(NodeArray< DWMSplit > &split, SubsetEnumerator< node > &subset, T oldCost)
Updates the auxiliary graph.
void computeSplit(NodeArray< DWMSplit > &split, node v, SubsetEnumerator< node > &subset) const
Populates split that contains a partial solution for an included nonterminal v in m_G.
Hashing< List< node >, DWMData, SortedNodeListHashFunc > m_map
A hash array for keys of size > 2.
const List< node > & m_terminals
A reference to the index-sorted list of terminals.
bool isAcyclicUndirected(const Graph &G, List< edge > &backedges)
Returns true iff the undirected graph G is acyclic.
bool isTree(const Graph &G)
Returns true iff G is a tree, i.e. contains no undirected cycle and is connected.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
int randomNumber(int low, int high)
Returns random integer between low and high (including).
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
void updateMin(T &min, const T &newValue)
Stores the minimum of min and newValue in min.
Definition Math.h:98
The namespace for all OGDF objects.
@ tree
for every hyperedge e a minimal subcubic tree connecting all hypernodes incident with e together is a...
Subgraphs (given by other subgraphs and additional edges) and their cost for a partial solution.
void set(const DWMData *s1, const DWMData *s2)
Sets subgraph1 and subgraph2 and computes cost.