Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
FullComponentStore.h
Go to the documentation of this file.
1
32#pragma once
33
36
37namespace ogdf {
38namespace steiner_tree {
39
40#define OGDF_FULLCOMPONENTSTORE_REMOVE_IN_GRAPH_REPRESENTATION_ALSO // unnecessary but may save memory
41
43template<typename T, typename ExtraDataType = void>
45protected:
52
53 template<class Y, class Enable = void> // Metadata without extra data
61
62 template<class Y> // Metadata with extra data
63 struct Metadata<Y, typename std::enable_if<!std::is_void<Y>::value>::type> {
66 T cost;
68
70 };
71
73
76 const EdgeWeightedGraphCopy<T>& comp) const {
77 while (m_nodeCopy[uO] == nullptr && !m_isTerminal[uO]) {
78 OGDF_ASSERT(comp.copy(uO)->degree() == 2);
79 adj = adj->twin()->cyclicSucc();
80 OGDF_ASSERT(comp.original(adj->theNode()) == uO);
81 edge e2 = adj->theEdge();
82 marked[e2] = true;
83 weight += comp.weight(e2);
84 uO = comp.original(adj->twinNode());
85 }
86 }
87
91 EdgeArray<bool> marked(comp, false);
92 for (node v : nonterminals) {
93 for (adjEntry adj : comp.copy(m_nodeOrig[v])->adjEntries) {
94 edge e = adj->theEdge();
95 if (!marked[e]) {
96 marked[e] = true;
97 node vO = comp.original(adj->theNode());
98 OGDF_ASSERT(m_nodeCopy[vO] != nullptr);
99 node uO = comp.original(adj->twinNode());
100 T weight(comp.weight(e));
101
102 traverseOverDegree2Nonterminals(uO, weight, marked, adj, comp);
103
104 edge eC = m_graph.newEdge(m_nodeCopy[uO], m_nodeCopy[vO], weight);
105 data.cost += weight;
106 if (m_isTerminal[uO]) {
107 data.start = eC->adjSource();
108 }
109 }
110 }
111 }
112#ifdef OGDF_DEBUG
113 for (edge e : comp.edges) {
114 OGDF_ASSERT(marked[e] == true);
115 }
116#endif
117 }
118
121 for (edge e : comp.edges) {
122 node uO = comp.original(e->source());
123 node vO = comp.original(e->target());
124 T weight = comp.weight(e);
125 edge eC = m_graph.newEdge(m_nodeCopy[uO], m_nodeCopy[vO], weight);
126 data.cost += weight;
127 if (m_isTerminal[uO]) {
128 data.start = eC->adjSource();
129 } else if (m_isTerminal[vO]) {
130 data.start = eC->adjTarget();
131 }
132 }
133 }
134
135public:
138 : m_originalGraph(G)
141 , m_nodeCopy(G, nullptr)
143 for (node v : m_terminals) {
144 node u = m_graph.newNode();
145 m_nodeCopy[v] = u;
146 m_nodeOrig[u] = v;
147 }
148 }
149
152 OGDF_ASSERT(!comp.empty());
154
155 // we temporarily use m_nodeCopy for nonterminals (with degree > 2) also
156 ArrayBuffer<node> nonterminals(comp.numberOfNodes() / 2);
157
158 // add all nonterminals with degree > 2 of comp to m_graph
159 // and find terminals
161 bool existNoncritical = false;
162 for (node v : comp.nodes) {
163 node vO = comp.original(v);
164 if (m_nodeCopy[vO] == nullptr) {
165 OGDF_ASSERT(v->degree() >= 2);
166 if (v->degree() > 2) {
167 node vC = m_graph.newNode();
168 m_nodeCopy[vO] = vC;
169 m_nodeOrig[vC] = vO;
170 nonterminals.push(vC);
171 } else {
172 existNoncritical = true;
173 }
174 } else {
175 data.terminals.grow(1, vO);
176 }
177 }
178 data.terminals.quicksort(GenericComparer<node, int>([](node v) { return v->index(); }));
179
180 // add all edges of comp to m_graph
181 // and find start adjEntry
182 if (existNoncritical) {
183 if (nonterminals.empty()) {
184 OGDF_ASSERT(data.terminals.size() == 2);
185 OGDF_ASSERT(data.cost == 0);
186 for (edge e : comp.edges) {
187 data.cost += comp.weight(e);
188 }
189 edge eC = m_graph.newEdge(m_nodeCopy[data.terminals[0]],
190 m_nodeCopy[data.terminals[1]], data.cost);
191 data.start = eC->adjSource();
192 } else {
194 }
195 } else {
196 copyEdges(data, comp);
197 }
198 OGDF_ASSERT(data.start != nullptr);
199
200 // cleanup m_nodeCopy (only terminals should be set)
201 for (node vC : nonterminals) {
202 m_nodeCopy[m_nodeOrig[vC]] = nullptr;
203 }
204
205 m_components.push(data);
206 }
207
209 void remove(int id) {
210#ifdef OGDF_FULLCOMPONENTSTORE_REMOVE_IN_GRAPH_REPRESENTATION_ALSO
211 auto& comp = m_components[id];
212 if (comp.terminals.size() == 2) {
213 m_graph.delEdge(comp.start->theEdge());
214 } else {
215 ArrayBuffer<node> stack(2 * comp.terminals.size() - 3);
216 stack.push(comp.start->twinNode());
217 m_graph.delEdge(comp.start->theEdge());
218 while (!stack.empty()) {
219 const node v = stack.popRet();
220 if (!isTerminal(v)) {
221 for (adjEntry adj : v->adjEntries) {
222 stack.push(adj->twinNode());
223 }
224 m_graph.delNode(v);
225 }
226 }
227 }
228#endif
229 if (m_components.size() == id + 1) {
230 m_components.pop();
231 } else {
232 m_components[id] = m_components.popRet();
233 }
234 }
235
237 int size() const { return m_components.size(); }
238
240 bool isEmpty() const { return m_components.empty(); }
241
243 const Array<node>& terminals(int id) const {
244 OGDF_ASSERT(id >= 0);
245 OGDF_ASSERT(id < m_components.size());
246 return m_components[id].terminals;
247 }
248
250 bool isTerminal(int id, node t) const {
251 OGDF_ASSERT(id >= 0);
252 OGDF_ASSERT(id < m_components.size());
253 return m_components[id].terminals.linearSearch(t) != -1;
254 }
255
256 bool isTerminal(node v) const { return m_isTerminal[m_nodeOrig[v]]; }
257
259 T cost(int i) const {
260 OGDF_ASSERT(i >= 0);
261 OGDF_ASSERT(i < m_components.size());
262 return m_components[i].cost;
263 }
264
265 adjEntry start(int i) const {
266 OGDF_ASSERT(i >= 0);
267 OGDF_ASSERT(i < m_components.size());
268 return m_components[i].start;
269 }
270
271 const EdgeWeightedGraph<T>& graph() const { return m_graph; }
272
273 node original(node v) const {
274 OGDF_ASSERT(m_nodeOrig[v] != nullptr);
275 return m_nodeOrig[v];
276 }
277
278 template<typename Fun>
279 void foreachAdjEntry(int i, Fun f) const {
280 adjEntry start = m_components[i].start;
281 int size = m_components[i].terminals.size();
282 if (size == 2) {
283 f(start->twin());
284 return;
285 }
286 // size >= 3: do DFS over nonterminals (terminals are only leaves)
288 stack.push(start);
289 while (!stack.empty()) {
290 const adjEntry back = stack.popRet()->twin();
291 f(back);
292 if (!this->isTerminal(back->theNode())) {
293 for (adjEntry adj = back->cyclicSucc(); adj != back; adj = adj->cyclicSucc()) {
294 stack.push(adj);
295 }
296 }
297 }
298 }
299
300 // \brief Do f(v) for each (original) node v of degree at least 3 in component with given id
301 template<typename Fun>
302 void foreachNode(int id, Fun f) const {
303 f(original(start(id)->theNode()));
304 foreachAdjEntry(id, [&](adjEntry back) { f(original(back->theNode())); });
305 }
306
307 // \brief Do f(e) for each (original) edge e in component with given id
308 template<typename Fun>
309 void foreachEdge(int id, const NodeArray<NodeArray<edge>>& pred, Fun f) const {
310 foreachAdjEntry(id, [&](adjEntry back) {
311 const node u = original(back->twinNode());
312 for (node v = original(back->theNode()); pred[u][v]; v = pred[u][v]->opposite(v)) {
313 f(pred[u][v]);
314 }
315 });
316 }
317
318 // \brief Do f(v) for each node v (also of degree 2) in component with given id
319 template<typename Fun>
320 void foreachNode(int id, const NodeArray<NodeArray<edge>>& pred, Fun f) const {
321 if (m_components[id].terminals.size() == 3) {
322 // use a variant that works when only pred[t] has been filled for all terminals t
323 adjEntry start = m_components[id].start;
324 const node c = start->twinNode();
325 f(original(c));
326 for (adjEntry adj : c->adjEntries) {
327 const node u = original(adj->twinNode());
328 node v = original(c);
329 while (v != u) {
330 v = pred[u][v]->opposite(v);
331 f(v);
332 }
333 }
334 return;
335 }
336 f(original(start(id)->theNode()));
337 foreachAdjEntry(id, [&](adjEntry back) {
338 const node u = original(back->twinNode());
339 for (node v = original(back->theNode()); pred[u][v]; v = pred[u][v]->opposite(v)) {
340 f(v);
341 }
342 });
343 }
344};
345
349template<typename T, typename ExtraDataType>
350class FullComponentWithExtraStore : public FullComponentStore<T, ExtraDataType> {
351public:
352 using FullComponentStore<T, ExtraDataType>::FullComponentStore;
353
356 OGDF_ASSERT(i >= 0);
358 return this->m_components[i].extra;
359 }
360
362 const ExtraDataType& extra(int i) const {
363 OGDF_ASSERT(i >= 0);
365 return this->m_components[i].extra;
366 }
367};
368
369template<typename T>
376
380template<typename T>
381class FullComponentWithLossStore : public FullComponentWithExtraStore<T, LossMetadata<T>> {
382protected:
386
394 if (!m_lossTerminal[u] && pred[u]) {
395 m_lossTerminal[u] = findLossTerminal(pred[u]->opposite(u), pred);
396 }
397
398 return m_lossTerminal[u];
399 }
400
401public:
402 using FullComponentWithExtraStore<T, LossMetadata<T>>::FullComponentWithExtraStore;
403
406 m_lossTerminal.init(this->m_graph, nullptr);
407
408 // add zero-cost edges between all terminals (to be removed later),
409 // and set m_lossTerminal mapping for terminals
411 const node s = this->m_terminals.front();
412 const node sC = this->m_nodeCopy[s];
413 m_lossTerminal[sC] = s;
414 for (ListConstIterator<node> it = this->m_terminals.begin().succ(); it.valid(); ++it) {
415 const node v = *it;
416 const node vC = this->m_nodeCopy[v];
417 m_lossTerminal[vC] = v;
418 zeroEdges.pushBack(this->m_graph.newEdge(sC, vC, 0));
419 }
420
421 // compute minimum spanning tree
422 NodeArray<edge> pred(this->m_graph);
423 EdgeArray<bool> isLossEdge(this->m_graph, false);
424 computeMinST(sC, this->m_graph, this->m_graph.edgeWeights(), pred, isLossEdge);
425
426 // remove zero-cost edges again
427 for (edge e : zeroEdges) {
428 this->m_graph.delEdge(e);
429 }
430
431 // find loss bridges and compute loss value
432 for (int id = 0; id < this->size(); ++id) {
433 this->foreachAdjEntry(id, [&](adjEntry adj) {
434 edge e = adj->theEdge();
435 if (!isLossEdge[e]) {
436 this->extra(id).bridges.pushBack(e);
437 findLossTerminal(e->source(), pred);
438 findLossTerminal(e->target(), pred);
439 } else {
440 this->extra(id).loss += this->m_graph.weight(e);
441 }
442 });
443 }
444 }
445
447 T loss(int id) const { return this->extra(id).loss; }
448
450 const List<edge>& lossBridges(int id) const { return this->extra(id).bridges; }
451
460 return m_lossTerminal[v];
461 }
462};
463
464}
465}
Extends the GraphCopy concept to weighted graphs.
Declaration and implementation of NodeArray class.
Class for adjacency list elements.
Definition Graph_d.h:79
adjEntry twin() const
Returns the corresponding adjacency element associated with the same edge.
Definition Graph_d.h:109
adjEntry cyclicSucc() const
Returns the cyclic successor in the adjacency list.
Definition Graph_d.h:291
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition Graph_d.h:97
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
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
void grow(INDEX add, const E &x)
Enlarges the array by add elements and sets new elements to x.
Definition Array.h:825
void quicksort()
Sorts array using Quicksort.
Definition Array.h:634
INDEX size() const
Returns the size (number of elements) of the array.
Definition Array.h:297
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
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Encapsulates a pointer to a list element.
Definition List.h:103
ListIteratorBase< E, isConst, isReverse > succ() const
Returns successor iterator.
Definition List.h:158
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
A data structure to store full components.
void remove(int id)
Removes a component by its id.
void foreachNode(int id, const NodeArray< NodeArray< edge > > &pred, Fun f) const
const NodeArray< bool > & m_isTerminal
Incidence vector for terminal nodes.
EdgeWeightedGraph< T > m_graph
Our graph representation for the full component store.
NodeArray< node > m_nodeCopy
Mapping of original terminals to m_graph nodes.
void copyEdgesWithSimplifiedPaths(Metadata< ExtraDataType > &data, const EdgeWeightedGraphCopy< T > &comp, const ArrayBuffer< node > &nonterminals)
Copy edges from comp into our representation, traversing variant to ignore degree-2 nodes.
void traverseOverDegree2Nonterminals(node &uO, T &weight, EdgeArray< bool > &marked, adjEntry adj, const EdgeWeightedGraphCopy< T > &comp) const
Traverse over degree-2 nonterminals.
bool isEmpty() const
Checks if the store does not contain any full components.
const EdgeWeightedGraph< T > & m_originalGraph
The original Steiner instance.
const List< node > & m_terminals
The terminal list of the original Steiner instance.
ArrayBuffer< Metadata< ExtraDataType > > m_components
List of full components (based on metadata)
bool isTerminal(int id, node t) const
checks if a given node t is a terminal in the full component with given id
void copyEdges(Metadata< ExtraDataType > &data, const EdgeWeightedGraphCopy< T > &comp)
Copy edges from comp into our representation.
void foreachEdge(int id, const NodeArray< NodeArray< edge > > &pred, Fun f) const
NodeArray< node > m_nodeOrig
Mapping of m_graph nodes to original nodes.
FullComponentStore(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal)
T cost(int i) const
Returns the sum of edge costs of this full component.
const EdgeWeightedGraph< T > & graph() const
const Array< node > & terminals(int id) const
Returns the list of terminals in the full component with given id.
void insert(const EdgeWeightedGraphCopy< T > &comp)
Inserts a component. Note that comp is copied and degree-2 nodes are removed.
int size() const
Returns the number of full components in the store.
A data structure to store full components with extra data for each component.
ExtraDataType & extra(int i)
Returns a reference to the extra data of this full component.
const ExtraDataType & extra(int i) const
Returns a const reference to the extra data of this full component.
A data structure to store full components with additional "loss" functionality.
void computeAllLosses()
Compute the loss, both edge set and value, of all full components.
node lossTerminal(node v) const
Returns the terminal (in the original graph) that belongs to a given node v (in the store) according ...
const List< edge > & lossBridges(int id) const
Returns a list of non-loss edges (that are bridges between the Loss components) of full component wit...
NodeArray< node > m_lossTerminal
Indicates which Steiner node is connected to which terminal through the loss edges,...
node findLossTerminal(const node u, const NodeArray< edge > &pred)
Starting from a Steiner node find the nearest terminal along a shortest path.
T loss(int id) const
Returns the loss value of full component with given id.
T computeMinST(const Graph &G, const EdgeArray< T > &weight, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree using Prim's algorithm.
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
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Definition GML.h:110
Compare elements based on a single comparable attribute.
Definition comparer.h:398
adjEntry start
Adjacency entry on a terminal where a non-terminal BFS yields the component.
adjEntry start
Adjacency entry on a terminal where a non-terminal BFS yields the component.
Array< node > terminals
Terminals, sorted by node index.
List< edge > bridges
List of non-loss edges.