Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
BlowupGraph.h
Go to the documentation of this file.
1
32#pragma once
33
35#include <ogdf/basic/Math.h>
38
39//#define OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
40
41namespace ogdf {
42namespace steiner_tree {
43namespace goemans {
44
49template<typename T>
51private:
54 const double m_eps;
55
58
65
68
69 int m_lcm;
70 int m_y;
74
76
78
79 /* witness set (for some component and specified K (core edge set))
80 *
81 * W(e) = { e } if e is a core edge
82 * W(e) =
83 * take the path P of loss edges from u to e in the component
84 * add every incident core edge of u
85 * that is: if we root the loss connected component at the terminal,
86 * W(e) = all core edges incident to the subtree below e
87 *
88 * Need fast lookups for:
89 * (1) |W(f)|
90 * (2) all loss edges f such that given core edge e is in W(f)
91 * (3) all loss edges f such that W(f) is a subset of a given basis -> for each e \in B: do (2)
92 *
93 * Data Structures:
94 * - witnessCard[e] = |W(e)|
95 * - witness[v_e] = { f | e \in W(f) }
96 * (Note that core edges are given as nodes.)
97 * Also note that we can save it all much sparser.
98 */
101
102protected:
104 void computeLCM() {
106
107 for (int i = 0; i < m_fullCompStore.size(); ++i) {
110 int num, denom;
112 OGDF_ASSERT(Math::gcd(num, denom) == 1);
113 denominators.push(denom);
114 }
115
116 m_lcm = 1;
117 for (int denom : denominators) {
119 }
120#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
121 std::cout << "Normalizing factor is " << m_lcm << std::endl;
122#endif
123 }
124
127 const node v = m_graph.newNode();
128 m_isTerminal[v] = true;
129 m_terminals.pushBack(v);
130 m_original[v] = t;
131#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
132 std::cout << "Add terminal " << v << " representing original terminal " << t << std::endl;
133#endif
134 return v;
135 }
136
138 const node vCopy = m_graph.newNode();
139 m_original[vCopy] = v;
140 return vCopy;
141 }
142
146 node v = m_fullCompStore.original(start->theNode());
149 queueT.pushBack(start);
150 queueC.pushBack(copy[v]);
151 while (!queueT.empty()) {
152 const adjEntry inAdj = queueT.popFrontRet();
153 const node wT = inAdj->twinNode();
154 const node vC = queueC.popFrontRet();
155
158 newEdge(vC, copy[wO], m_fullCompStore.graph().weight(inAdj->theEdge()), cap);
159 } else { // not a terminal
160 const node wC = initNode(wO);
161 newEdge(vC, wC, m_fullCompStore.graph().weight(inAdj->theEdge()), cap);
162 const adjEntry back = inAdj->twin();
163 for (adjEntry adj = back->cyclicSucc(); adj != back; adj = adj->cyclicSucc()) {
164 queueT.pushBack(adj);
165 queueC.pushBack(wC);
166 }
167 }
168 }
169 return copy[v];
170 }
171
173 void initSource(ArrayBuffer<std::pair<node, int>>& roots) {
174 OGDF_ASSERT(m_source == nullptr);
176#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
177 std::cout << "Add source node " << getSource() << " with edges to:" << std::endl;
178#endif
179 for (auto root : roots) {
180#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
181 std::cout << " * node " << root.first << " with cost 0 and capacity " << root.second
182 << std::endl;
183#endif
184 newEdge(getSource(), root.first, 0, root.second);
185 }
186 }
187
190 const List<node>& terminals) {
191 ArrayBuffer<std::pair<node, int>> roots; // roots (in the blowupGraph) and their capacities
192
193 NodeArray<node> copy(originalGraph, nullptr);
194 for (node t : terminals) { // generate all terminals
195 copy[t] = initTerminal(t);
196 }
197 for (int i = 0; i < m_fullCompStore.size(); ++i) {
198 int cap = int(getLCM() * m_fullCompStore.extra(i) + m_eps);
200 roots.push(std::make_pair(root, cap));
201 }
202
203 removeIsolatedTerminals(); // can exist by preprocessing
204
205#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
206 for (edge e : m_graph.edges) {
207 std::cout << "Edge from " << e << " of cost " << m_cost[e] << " and capacity "
208 << m_capacity[e] << std::endl;
209 }
210#endif
211
212 // compute core edges (and replace these edges by nodes)
213 // and witness sets
215
217 }
218
221 OGDF_ASSERT(m_pseudotarget == nullptr);
223
224#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
225 std::cout << "Add pseudo-target " << getPseudotarget()
226 << " with edges coming from:" << std::endl;
227#endif
228 for (node v : terminals()) {
229 OGDF_ASSERT(v);
230 int y_v = -getLCM();
231 // compute y_v, the number of components containing v in the blow up graph - N
232 // NOTE: for the non-blowup variant this is simply the sum of all x_C where C contains v ... - 1
233 for (adjEntry adj : v->adjEntries) {
234 if (adj->twinNode() != getSource()) {
235 y_v += getCapacity(adj->theEdge());
236 }
237 }
238 OGDF_ASSERT(y_v >= 0);
239
240 if (y_v > 0) {
241 newEdge(v, getPseudotarget(), 0, y_v);
242#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
243 std::cout << " * terminal " << v << " with zero cost and capacity " << y_v
244 << std::endl;
245#endif
246 m_y += y_v;
247 }
248 }
249 }
250
252 void initTarget() {
253 OGDF_ASSERT(m_target == nullptr);
255
257#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
258 std::cout << "Add edge from pseudo-target " << getPseudotarget() << " to target "
259 << getTarget() << " with zero cost and capacity " << m_y << std::endl;
260#endif
261 }
262
265#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
266 std::cout << " * updating for terminal " << v << std::endl;
267#endif
268 int delta = 0;
269 int capSource = 0;
270 int capTarget = -getLCM();
271#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
272 std::cout << " * target capacity initialized to " << capTarget
273 << ", source capacity and delta to 0" << std::endl;
274#endif
276 for (adjEntry adj = v->firstAdj(); adj; adj = adj2) {
277 adj2 = adj->succ();
278 if (adj->twinNode() == getSource()) {
279#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
280 std::cout << " * remove edge with capacity " << getCapacity(adj->theEdge())
281 << " from source " << getSource() << std::endl;
282#endif
283 OGDF_ASSERT(adj->theEdge()->source() == getSource());
284
285 // remove arcs from the source
286 m_graph.delEdge(adj->theEdge());
287 } else if (adj->twinNode() == getPseudotarget()) {
288#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
289 std::cout << " * remove edge to pseudotarget " << getPseudotarget()
290 << " with capacity " << getCapacity(adj->theEdge())
291 << " participating in delta" << std::endl;
292#endif
293 OGDF_ASSERT(adj->theEdge()->target() == getPseudotarget());
294
295 // remove arcs to the pseudotarget
296 delta -= getCapacity(adj->theEdge());
297 m_graph.delEdge(adj->theEdge());
298 } else {
299#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
300 std::cout << " * update target capacity for edge " << adj->theEdge()
301 << " by adding " << getCapacity(adj->theEdge()) << std::endl;
302#endif
303 // compute y_v for the contraction node
304 capTarget += getCapacity(adj->theEdge());
305 // compute s->v capacity
306 if (v != adj->theEdge()->target()) { // outgoing edge
307#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
308 std::cout << " and change source capacity by the same amount" << std::endl;
309#endif
310 capSource += getCapacity(adj->theEdge());
311 }
312 }
313 }
314#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
315 std::cout << " * new target capacity is " << capTarget << " and delta = " << delta
316 << std::endl;
317#endif
319 if (capTarget > 0) {
321#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
322 std::cout << " * new edge from pseudotarget to target with zero cost and capacity "
323 << capTarget << std::endl;
324#endif
325 }
326 if (capSource > 0) {
327#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
328 std::cout << " * new edge from source to " << v << " with zero cost and capacity "
329 << capSource << std::endl;
330#endif
331 newEdge(getSource(), v, 0, capSource);
332 }
333
334 return delta + capTarget;
335 }
336
337 void setCapacity(edge e, int capacity) { m_capacity[e] = capacity; }
338
341
344 void addCore(node e) { m_coreEdges.pushBack(e); }
345
348 ++m_witnessCard[f];
349 m_witness[e].push(f);
350 }
351
359 m_witness.init(m_graph);
360
361 // compute set of core edges
364
365 // add nodes for core edges and be able to map them
368 for (edge e : m_graph.edges) {
369 if (!isLossEdge[e]) {
370 splitMap[e] = m_graph.newNode();
371 coreEdges.push(e);
372 }
373 }
374
375 // traverse losses from all terminals to find witness sets
376 NodeArray<adjEntry> pred(m_graph, nullptr);
377 for (node t : terminals()) {
379 stack.push(t);
380 while (!stack.empty()) {
381 // for each node v "below" an edge e in the traversal:
382 // add all incident core edges vw to W(e)
383 const node v = stack.popRet();
384 for (adjEntry adj : v->adjEntries) {
385 const edge e = adj->theEdge();
386 const node w = adj->twinNode();
387 if (!pred[v] || w != pred[v]->theNode()) { // do not look at backward arcs in the tree
388 if (isLossEdge[e]) {
389 stack.push(w);
390 pred[w] = adj;
391 } else {
392 for (node x = v; pred[x]; x = pred[x]->theNode()) {
393 addWitness(splitMap[e], pred[x]->theEdge());
394 }
395 }
396 }
397 }
398 }
399 }
400
401 // finally replace core edges by nodes
402 for (edge e : coreEdges) {
403 const T w = getCost(e);
404 const node x = splitMap[e];
405 const int cap = getCapacity(e);
406 OGDF_ASSERT(x);
407 newEdge(e->source(), x, w, cap);
408 newEdge(x, e->target(), 0, cap);
409 // the cost of a core edge node is hence the weight of one incident edge;
410 // also keep capacity.
411 // Note that we cannot guarantee throughout the algorithm that the edge
412 // with the non-zero cost is the first one nor that it is the incoming one
413 // because both directions and adjacency orders can be changed.
414 m_graph.delEdge(e);
415 addCore(x);
416 }
417 }
418
420 void makeCWCopy(const HashArray<edge, edge>& edgeMap) {
421 for (HashConstIterator<edge, edge> pair = edgeMap.begin(); pair.valid(); ++pair) {
422 const edge eO = pair.key();
423 const edge eC = pair.info();
424 const node vO = eO->target();
425 const node vC = eC->target();
426 m_witnessCard[eC] = m_witnessCard[eO]; // copy witness cardinality
427 if (vC == vO) { // target is a terminal, so it cannot be a core edge
428 continue;
429 }
430 for (ListIterator<node> it = m_coreEdges.begin(); it.valid(); ++it) {
431 if (*it == vO) { // vO is a core edge
432 m_coreEdges.insertAfter(vC, it); // make vC a core edge
433
434 // copy witness sets
435 // XXX: do we need this or are witness sets computed after the loop again?!
436 for (edge e : m_witness[vO]) {
437 m_witness[vC].push(edgeMap[e]);
438 }
439 break;
440 }
441 }
442 }
443 }
444
446
447public:
451 const CoreEdgeModule<T>& ceModule, double eps = 1e-8)
453 , m_eps(eps)
454 , m_terminals()
457 , m_cost(m_graph)
459 , m_y(0)
464 computeLCM();
465
466#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
467 std::cout << "Full components to use in blowup graph:\n";
468 for (int k = 0; k < m_fullCompStore.size(); ++k) {
469 std::cout << " * " << m_fullCompStore.terminals(k) << " cost "
470 << m_fullCompStore.cost(k) << " support " << m_fullCompStore.extra(k)
471 << " (normalized to " << m_fullCompStore.extra(k) * m_lcm << ")" << std::endl;
472 }
473#endif
474
477 initTarget();
478 }
479
482
483 const Graph& getGraph() const { return m_graph; }
484
486 node getSource() const { return m_source; }
487
490
492 node getTarget() const { return m_target; }
493
495 int getCapacity(edge e) const { return m_capacity[e]; }
496
498 const EdgeArray<int>& capacities() const { return m_capacity; }
499
501 T getCost(edge e) const { return m_cost[e]; }
502
504 node getOriginal(node v) const { return m_original[v]; }
505
507 int getLCM() const { return m_lcm; }
508
510 int getY() const { return m_y; }
511
513 const List<node>& terminals() const { return m_terminals; }
514
516 bool isTerminal(node v) const { return m_isTerminal[v]; }
517
521
524 OGDF_ASSERT(v->degree() == 2);
525 return getCapacity(v->firstAdj()->theEdge());
526 }
527
529 T getCoreCost(node v) const {
530 OGDF_ASSERT(v->degree() == 2);
531 T val = getCost(v->firstAdj()->theEdge());
532 if (val == 0) {
533 val = getCost(v->lastAdj()->theEdge());
534 }
535 return val;
536 }
537
539 double computeCoreWeight(node v) const {
540 double weight = (double)getCoreCost(v);
541 for (edge e : witnessList(v)) {
543 weight += (double)getCost(e) / numberOfWitnesses(e);
544 }
545 return weight;
546 }
547
549
552#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
553 std::cout << "Updating capacities (y = " << m_y << ")" << std::endl;
554#endif
555 for (node t : terminals()) {
557#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
558 std::cout << " * new y = " << m_y << std::endl;
559#endif
560 }
561 // XXX: doing it for v and all terminals we have met during cleanup would be sufficient
562 OGDF_ASSERT(getTarget()->degree() == 1);
563 setCapacity(getTarget()->firstAdj()->theEdge(), m_y);
564 }
565
567 edge newEdge(node v, node w, T cost, int capacity) {
568 edge e = m_graph.newEdge(v, w);
569 m_cost[e] = cost;
570 m_capacity[e] = capacity;
571 return e;
572 }
573
576 for (edge e : edges) {
577 m_graph.delEdge(e);
578 }
579 }
580
582 void contract(node& v, node t) {
583 if (v->degree() == 0) {
584 std::swap(v, t);
585 }
586
588 m_terminals.removeFirst(t);
589 m_isTerminal[t] = false;
590
591 if (t->degree() > 0) {
593 // the contract method ensures that capacities, weights, and everything is kept
594 } else {
596 }
597 }
598
600 template<typename NODELIST>
601 void contract(NODELIST& nodes) {
602 auto it = nodes.begin();
603 node v = *it;
604 for (++it; it != nodes.end(); ++it) {
605 contract(v, *it);
606 }
607 }
608
615 ArrayBuffer<node> cleanup;
616 cleanup.push(v->firstAdj()->twinNode());
617 cleanup.push(v->lastAdj()->twinNode());
618 OGDF_ASSERT(v->degree() == 2);
619 OGDF_ASSERT(v->firstAdj()->twinNode() != v->lastAdj()->twinNode());
620 m_graph.delNode(v);
621
622 while (!cleanup.empty()) {
623 v = cleanup.popRet();
624 if (!isTerminal(v)) {
625 OGDF_ASSERT(v->degree() >= 1);
626 if (v->degree() == 1) { // v is a pendant node, delete
627#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
628 std::cout << " * remove pendant node " << v << " for cleanup" << std::endl;
629#endif
630 cleanup.push(v->firstAdj()->twinNode());
631 m_graph.delNode(v);
632 } else if (v->indeg() == 0) { // v has no incoming edge, fix
633#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
634 std::cout << " * " << v << " has no incoming edge -> fix directions"
635 << std::endl;
636#endif
637 const node w = v->firstAdj()->twinNode();
638 const edge e = v->firstAdj()->theEdge();
639#ifdef OGDF_STEINER_TREE_GOEMANS_BLOWUP_GRAPH_LOGGING
640 std::cout << " * make " << w << " parent of " << v << " (reverse edge "
641 << e << ")" << std::endl;
642#endif
644 OGDF_ASSERT(e->source() == w);
645 if (!isTerminal(w)) {
646 cleanup.push(w);
647 // when w is cleaned up, it must not go back to v
648 if (w->firstAdj()->theEdge() == e) {
649 // move first adjacency entries of w away (w->v is not first anymore)
651 }
652 }
653 }
654 }
655 }
656 }
657
660 for (ListIterator<node> it = m_terminals.begin(), itNext; it.valid(); it = itNext) {
661 itNext = it.succ();
662 if ((*it)->degree() == 0) {
663 m_graph.delNode(*it);
664 m_terminals.del(it);
665 }
666 }
667 }
668
671 edge rootEdge = nullptr;
673 for (auto it = v->adjEntries.begin(); it != v->adjEntries.end();) {
674 edge e = (*it)->theEdge();
675 if (e->source() != v) { // incoming edge
676 rootEdge = e;
677 if (isTerminal(e->source())) {
678 break;
679 }
680 v = e->source();
681 it = v->adjEntries.begin();
682 } else {
683 ++it;
684 }
685 }
686 OGDF_ASSERT(rootEdge != nullptr);
687 OGDF_ASSERT(isTerminal(rootEdge->source()));
688 return rootEdge;
689 }
690
692 void copyComponent(const edge origEdge, const int origCap, const int copyCap) {
693 if (copyCap == 0) {
694 return;
695 }
698 HashArray<edge, edge> edgeMap;
699 todo.pushBack(origEdge);
700 origin.pushBack(origEdge->source());
701 while (!todo.empty()) {
702 edge eO = todo.popFrontRet();
703 node vC = origin.popFrontRet();
704 node wO = eO->target();
705 node wC = wO;
706 if (!isTerminal(wO)) {
708 }
711 edgeMap[eO] = eC;
712 if (!isTerminal(wO)) {
713 for (adjEntry adj = eO->adjTarget()->cyclicSucc(); adj != eO->adjTarget();
714 adj = adj->cyclicSucc()) {
715 OGDF_ASSERT(adj->theEdge()->target() != eO->target()); // outgoing edges
716 origin.pushBack(wC);
717 todo.pushBack(adj->theEdge());
718 }
719 }
720 }
721 makeCWCopy(edgeMap);
722 }
723
726
728 const List<node>& core() const { return m_coreEdges; }
729
732 void delCore(node e) {
733 /* What happens when we remove a core edge?
734 * - loss edges are not affected
735 * - we have to remove a core edge e from W(f) for all f, which means:
736 * for all elements f of witness[v_e], decrease witnessCard[f], then remove witness[v_e]
737 */
738 for (edge f : m_witness[e]) {
739 --m_witnessCard[f];
740 }
741 // witness[e] is removed by removing the node from the graph
742 m_coreEdges.removeFirst(e);
743 }
744
746 int numberOfWitnesses(edge e) const { return m_witnessCard[e]; }
747
749 const ArrayBuffer<edge>& witnessList(node e) const { return m_witness[e]; }
750
752};
753
754}
755}
756}
Definition of ogdf::steiner_tree::goemans::CoreEdgeModule class template.
Definition of the FullComponentStore class template.
Declaration and implementation of HashArray class.
Mathematical Helpers.
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
adjEntry succ() const
Returns the successor in the adjacency list.
Definition Graph_d.h:155
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
E popRet()
Removes the newest element from the buffer and returns it.
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
void init()
Reinitializes the array. Associates the array with no graph.
Definition EdgeArray.h:292
Class for the representation of edges.
Definition Graph_d.h:300
node source() const
Returns the source node of the edge.
Definition Graph_d.h:335
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
node contract(edge e, bool keepSelfLoops=false)
Contracts edge e while preserving the order of adjacency entries.
edge newEdge(node v, node w)
Creates a new edge (v,w) and returns it.
virtual void delNode(node v)
Removes node v and all incident edges from the graph.
void reverseEdge(edge e)
Reverses the edge e, i.e., exchanges source and target node.
virtual void delEdge(edge e)
Removes edge e from the graph.
void moveAdjAfter(adjEntry adjMove, adjEntry adjAfter)
Moves adjacency entry adjMove after adjAfter.
Definition Graph_d.h:1133
node newNode()
Creates a new node and returns it.
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition Graph_d.h:592
Indexed arrays using hashing for element access.
Definition HashArray.h:93
HashConstIterator< I, E, H > begin() const
Returns an iterator to the first element in the list of all elements.
Definition HashArray.h:112
Iterators for hash tables.
Definition Hashing.h:429
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
bool valid() const
Returns true iff the iterator points to an element.
Definition List.h:137
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
int indeg() const
Returns the indegree of the node.
Definition Graph_d.h:214
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition Graph_d.h:220
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition Graph_d.h:208
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition Graph_d.h:223
adjEntry lastAdj() const
Returns the last entry in the adjacency list.
Definition Graph_d.h:226
bool isTerminal(int id, node t) const
checks if a given node t is a terminal in the full component with given id
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.
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.
A special-purpose blowup graph for gammoid computation: directed, with special source and target,...
Definition BlowupGraph.h:50
T getCost(edge e) const
Returns the cost of e.
void removeBasis(node v)
Removes a basis and cleans up.
List< node > m_terminals
The terminals in the blowup graph.
Definition BlowupGraph.h:56
const EdgeArray< int > & capacities() const
Returns a reference to the edge array containing all capacities.
void contract(node &v, node t)
Contracts node v and terminal t into v.
void setCapacity(edge e, int capacity)
void initBlowupGraphComponents(const EdgeWeightedGraph< T > &originalGraph, const List< node > &terminals)
Initializes all components in the blowup graph as well as core edges and witness sets.
int numberOfWitnesses(edge e) const
Return the number of witnesses of an edge.
void delEdges(ArrayBuffer< edge > edges)
Removes edges in edges.
void removeIsolatedTerminals()
Removes isolated terminals.
int getY() const
Returns the y-value of all terminals.
int getLCM() const
Returns the least common multiple of all denominators.
node getSource() const
Returns the source node.
void initSource(ArrayBuffer< std::pair< node, int > > &roots)
Connects source to component roots.
void initCoreWitness()
Finds a "random" set of core edges and "replace" found edges by nodes, also find the witness sets for...
void delCore(node e)
Remove a core edge.
edge newEdge(node v, node w, T cost, int capacity)
Adds and returns a new edge between v and w of specified cost and capacity.
void addWitness(node e, edge f)
Adds e to W(f)
node getTarget() const
Returns the target node.
List< node > m_coreEdges
the core edges as nodes
Definition BlowupGraph.h:77
void copyComponent(const edge origEdge, const int origCap, const int copyCap)
Copy a component in the blowup graph and set original capacity to origCap and capacity of copy to cop...
void addCore(node e)
Adds a core edge.
double computeCoreWeight(node v) const
Compute the weight of a core edge.
const FullComponentWithExtraStore< T, double > & m_fullCompStore
all enumerated full components, with solution
Definition BlowupGraph.h:53
int getCapacity(edge e) const
Returns the capacity of e.
edge findRootEdge(node v)
Finds the root node of a component given by v, an arbitrary inner nonterminal of the component.
NodeArray< ArrayBuffer< edge > > m_witness
const List< node > & terminals() const
Returns a reference to the list containing all terminals in the blowup graph.
node getPseudotarget() const
Returns the pseudotarget node.
T getCoreCost(node v) const
Get cost of a core edge.
const double m_eps
epsilon for double operations
Definition BlowupGraph.h:54
node initBlowupGraphComponent(const NodeArray< node > &copy, adjEntry start, int cap)
Does a bfs of the component tree to add directed components with the first terminal as root.
void updateSpecialCapacities()
Updates capacities from source to terminals and terminals to pseudotarget.
node initTerminal(node t)
Inserts a terminal.
void contract(NODELIST &nodes)
Contracts nodes.
void makeCWCopy(const HashArray< edge, edge > &edgeMap)
Copies witness sets and core edges for a given copy map.
node getOriginal(node v) const
Returns the original node of v.
void initPseudotarget()
Connects pseudotarget.
NodeArray< bool > m_isTerminal
Incidence vector for the blowup graph terminals.
Definition BlowupGraph.h:57
void computeLCM()
Computes the least common multiple of the values assigned to the full components.
bool isTerminal(node v) const
Returns true if and only if v is a terminal.
const CoreEdgeModule< T > & m_ceModule
Definition BlowupGraph.h:75
NodeArray< node > m_original
Mapping of blowup graph nodes to original nodes. If a node in a blowup graph represents more than one...
Definition BlowupGraph.h:64
int updateSourceAndTargetArcCapacities(const node v)
Updates arc capacities s->v and v->t.
T getCoreCapacity(node v) const
Get capacity of a core edge.
BlowupGraph(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const FullComponentWithExtraStore< T, double > &fullCompStore, const CoreEdgeModule< T > &ceModule, double eps=1e-8)
Initializes a blowup graph including core edges and witness sets.
const ArrayBuffer< edge > & witnessList(node e) const
Return list of loss edges f in W(e)
const List< node > & core() const
Return list of core edges (implemented by nodes)
Interface for core edge finder algorithms.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
T lcm(T a, T b)
Returns the least common multipler of two numbers.
Definition Math.h:193
T gcd(T a, T b)
Returns the greatest common divisor of two numbers.
Definition Math.h:171
void getFraction(double d, int &num, int &denom, const double epsilon=5e-10, const int count=10)
Converts a double to a fraction.
Definition Math.h:200
The namespace for all OGDF objects.