Graph Drawing

 v. 2023.09 (Elderberry)

No Matches
Go to the documentation of this file.
33#pragma once
38#include <ogdf/tree/LCA.h>
40namespace ogdf {
41namespace steiner_tree {
47template<typename T>
48class SaveStatic : public Save<T> {
60 virtual ~SaveStatic() { delete m_lca; }
68 virtual T saveWeight(node u, node v) const { return m_steinerTree->weight(saveEdge(u, v)); }
76 virtual edge saveEdge(node u, node v) const {
77 OGDF_ASSERT(m_steinerTree->copy(u));
78 OGDF_ASSERT(m_steinerTree->copy(v));
79 node anc = lca(m_steinerTree->copy(u), m_steinerTree->copy(v));
81 return m_treeEdge[anc];
82 }
91 virtual T gain(node u, node v, node w) const {
92 node save0 = lca(m_steinerTree->copy(u), m_steinerTree->copy(v));
93 node save1 = lca(m_steinerTree->copy(u), m_steinerTree->copy(w));
94 if (save0 == save1) {
95 save1 = lca(m_steinerTree->copy(v), m_steinerTree->copy(w));
96 }
97 return (save0 ? m_steinerTree->weight(m_treeEdge[save0]) : 0)
98 + (save1 ? m_steinerTree->weight(m_treeEdge[save1]) : 0);
99 }
104 void rebuild() {
105 m_tree.clear();
106 m_cTerminals.fill(nullptr);
108 delete m_lca;
109 m_lca = new LCA(m_tree, m_root);
110 }
120 virtual void update(const Triple<T>& t) {
121 const edge save0 = saveEdge(t.s0(), t.s1());
122 const edge save1 = saveEdge(t.s0(), t.s2());
123 const edge save2 = saveEdge(t.s1(), t.s2());
126 rebuild();
127 }
135 node lca(node u, node v) const { return m_lca->call(m_cTerminals[u], m_cTerminals[v]); }
The Sparse Table Algorithm for the Least Common Ancestor problem as proposed by Bender and Farach-Col...
Interface for various LCA methods.
Definition of a Triple used in contraction-based approximation algorithm for the minimum Steiner tree...
Class for the representation of edges.
Definition Graph_d.h:300
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
virtual void clear()
Removes all nodes and all edges from the graph.
Implements the <O(n log n), O(1)>-time "sparse table" algorithm by Bender and Farach-Colton to comput...
Definition LCA.h:52
node call(node u, node v) const
Returns the LCA of two nodes u and v.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
This class serves as an interface for different approaches concerning the calculation of save edges.
Definition Save.h:45
This class behaves basically the same as SaveDynamic except that the update of the weighted graph is ...
Definition SaveStatic.h:48
EdgeWeightedGraphCopy< T > * m_steinerTree
A pointer to the tree we represent the save for.
Definition SaveStatic.h:141
node m_root
The root of m_tree.
Definition SaveStatic.h:142
SaveStatic(EdgeWeightedGraphCopy< T > &steinerTree)
Definition SaveStatic.h:50
void rebuild()
Rebuild the data structure (necessary if the tree has changed)
Definition SaveStatic.h:104
LCA * m_lca
The LCA data structure for m_tree.
Definition SaveStatic.h:143
NodeArray< edge > m_treeEdge
Maps each inner node of m_tree to an edge in m_steinerTree.
Definition SaveStatic.h:140
virtual void update(const Triple< T > &t)
Updates the weighted tree data structure given a contracted triple.
Definition SaveStatic.h:120
NodeArray< node > m_cTerminals
Definition SaveStatic.h:144
node lca(node u, node v) const
Returns the node corresponding to the LCA between two given nodes.
Definition SaveStatic.h:135
virtual T gain(node u, node v, node w) const
Returns the gain (sum of the save edges) of a node triple by an LCA query.
Definition SaveStatic.h:91
Graph m_tree
The weighted binary tree to represent the edge weight hierarchy.
Definition SaveStatic.h:139
virtual T saveWeight(node u, node v) const
Determines the weight of the save edge between two nodes by a LCA query.
Definition SaveStatic.h:68
virtual edge saveEdge(node u, node v) const
Determines the save edge between two nodes by a LCA query.
Definition SaveStatic.h:76
This class represents a triple used by various contraction-based minimum Steiner tree approximations.
Definition Triple.h:44
Algorithms used by at least two functions of Steiner tree code or its internal helpers.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/ for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
node buildHeaviestEdgeInComponentTree(const EdgeWeightedGraphCopy< T > &inputTree, NodeArray< node > &externalNodes, NodeArray< edge > &treeEdge, Graph &outputTree)
Given an edge-weighted tree, builds an auxiliary arborescence where each arc of the input tree is a n...
void contractTripleInSteinerTree(const Triple< T > &t, EdgeWeightedGraphCopy< T > &st, edge save0, edge save1, edge save2, edge &ne0, edge &ne1)
Updates the Steiner tree by deleting save edges, removing all direct connections between the terminal...
The namespace for all OGDF objects.