Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

SaveDynamic.h
Go to the documentation of this file.
1 
33 #pragma once
34 
35 #include <ogdf/tree/LCA.h>
39 
40 namespace ogdf {
41 namespace steiner_tree {
42 
48 //#define OGDF_SAVEDYNAMIC_CHANGE_TST
49 template<typename T>
50 class SaveDynamic: public Save<T> {
51 public:
58  explicit SaveDynamic(EdgeWeightedGraphCopy<T> &steinerTree)
59  : Save<T>()
60  , m_tree()
61  , m_treeEdge(m_tree, nullptr)
62  , m_steinerTree(&steinerTree)
63  , m_cTerminals(*m_steinerTree, nullptr)
64  {
66  m_lca = new LCA(m_tree, m_root);
67  }
68 
69  virtual ~SaveDynamic()
70  {
71  delete m_lca;
72  }
73 
82  virtual T gain(node u, node v, node w) const
83  {
84  node save1 = lca(m_steinerTree->copy(u), m_steinerTree->copy(v));
85  node save2 = lca(m_steinerTree->copy(u), m_steinerTree->copy(w));
86  if (save1 == save2) {
87  save2 = lca(m_steinerTree->copy(v), m_steinerTree->copy(w));
88  }
89  return weight(save1) + weight(save2);
90  }
91 
99  virtual T saveWeight(node u, node v) const
100  {
101  return weight(saveEdge(u, v));
102  }
103 
111  virtual edge saveEdge(node u, node v) const
112  {
113  OGDF_ASSERT(m_steinerTree->copy(u));
114  OGDF_ASSERT(m_steinerTree->copy(v));
115  node anc = lca(m_steinerTree->copy(u), m_steinerTree->copy(v));
116  OGDF_ASSERT(anc);
117  return m_treeEdge[anc];
118  }
119 
128  virtual void update(const Triple<T> &t)
129  {
130 #ifdef OGDF_SAVEDYNAMIC_CHANGE_TST
131  edge se0 = saveEdge(t.s0(), t.s1());
132  edge se1 = saveEdge(t.s0(), t.s2());
133  edge se2 = saveEdge(t.s1(), t.s2());
134 #endif
135  // initialize the three terminal nodes
136  node s0 = m_steinerTree->copy(t.s0());
137  node s1 = m_steinerTree->copy(t.s1());
138  node s2 = m_steinerTree->copy(t.s2());
139 
140  // determine the save edges
141  node save1 = lca(s0, s1);
142  node save2 = lca(s0, s2);
143  if (save1 == save2) {
144  save2 = lca(s1, s2);
145  }
146 
147  node v0 = m_cTerminals[s0];
148  node v1 = m_cTerminals[s1];
149  node v2 = m_cTerminals[s2];
150 
151  int v0level = m_lca->level(v0);
152  int v1level = m_lca->level(v1);
153  int v2level = m_lca->level(v2);
154 
155  delete m_lca;
156 
157  node v = m_tree.newNode();
158  node currentNode = m_tree.newNode();
159 #ifdef OGDF_SAVEDYNAMIC_CHANGE_TST
160  const node newNode0 = v, newNode1 = currentNode;
161 #endif
162  OGDF_ASSERT(!m_treeEdge[currentNode]);
163  m_tree.newEdge(currentNode, v);
164  m_cTerminals[s0] = v;
165  m_cTerminals[s1] = v;
166  m_cTerminals[s2] = currentNode;
167 
168  while (v0) {
169  // bubble pointers such that level(v0) >= level(v1) >= level(v2)
170  if (v1level < v2level) {
171  std::swap(v1, v2);
172  std::swap(v1level, v2level);
173  }
174  if (v0level < v1level) {
175  std::swap(v0, v1);
176  std::swap(v0level, v1level);
177  }
178  if (v1level < v2level) {
179  std::swap(v1, v2);
180  std::swap(v1level, v2level);
181  }
182  // bubble pointers such that weight(v0) <= weight(v1), weight(v2)
183  if (weight(v1) > weight(v2)) {
184  std::swap(v1, v2);
185  std::swap(v1level, v2level);
186  }
187  if (weight(v0) > weight(v1)) {
188  std::swap(v0, v1);
189  std::swap(v0level, v1level);
190  }
191  // now v0 is the node with the least weight... if equal, with the highest level.
192 
193  if (v0 != save1
194  && v0 != save2) {
195  for(adjEntry adj : currentNode->adjEntries) {
196  edge e = adj->theEdge();
197  if (e->target() == currentNode) {
198  m_tree.delEdge(e);
199  break;
200  }
201  }
202  m_tree.newEdge(v0, currentNode);
203  currentNode = v0;
204  } // else: nothing to do since m_tree is binary and save1/save2 are LCAs
205 
206  // set v0 to its parent or to nullptr if there is no parent
207  v = v0;
208  v0 = nullptr;
209  edge e = nullptr;
210  for(adjEntry adj : v->adjEntries) {
211  e = adj->theEdge();
212  if (e->target() == v) {
213  v0 = e->source();
214  --v0level;
215  break;
216  }
217  }
218  OGDF_ASSERT(e != nullptr);
219  if (v1 == e->target()) {
220  v1 = e->source();
221  --v1level;
222  }
223  if (v2 == e->target()) {
224  v2 = e->source();
225  --v2level;
226  }
227  }
228  m_root = currentNode;
229  m_tree.delNode(save1);
230  m_tree.delNode(save2);
231 
232  m_lca = new LCA(m_tree, m_root);
233 
234 #ifdef OGDF_SAVEDYNAMIC_CHANGE_TST
235  edge newEdge0, newEdge1;
236  contractTripleInSteinerTree(t, *m_steinerTree, se0, se1, se2, newEdge0, newEdge1);
237  m_treeEdge[newNode0] = newEdge0;
238  m_treeEdge[newNode1] = newEdge1;
239 #endif
240  }
241 
242 protected:
243 
251  node lca(node u, node v) const
252  {
253  OGDF_ASSERT(u);
254  OGDF_ASSERT(v);
255  return m_lca->call(m_cTerminals[u], m_cTerminals[v]);
256  }
257 
259  T weight(edge e) const
260  {
261  return e ? m_steinerTree->weight(e) : 0;
262  }
263 
265  T weight(node v) const
266  {
267  return weight(m_treeEdge[v]);
268  }
269 
270 private:
274 #ifndef OGDF_SAVEDYNAMIC_CHANGE_TST
275  const
276 #endif
280 };
281 
282 }
283 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::LCA::level
int level(node v) const
Returns the level of a node. The level of the root is 0.
Definition: LCA.h:74
ogdf::steiner_tree::SaveDynamic::m_lca
LCA * m_lca
Data structure for calculating the LCAs.
Definition: SaveDynamic.h:279
ogdf::steiner_tree::contractTripleInSteinerTree
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...
Definition: common_algorithms.h:145
ogdf::steiner_tree::Triple
This class represents a triple used by various contraction-based minimum Steiner tree approximations.
Definition: Triple.h:44
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::steiner_tree::SaveDynamic::weight
T weight(node v) const
Returns the associated weight of a node v in m_tree, or 0 if it is not associated.
Definition: SaveDynamic.h:265
ogdf::Graph::newEdge
edge newEdge(node v, node w)
Creates a new edge (v,w) and returns it.
ogdf::Graph::delNode
virtual void delNode(node v)
Removes node v and all incident edges from the graph.
ogdf::steiner_tree::SaveDynamic::update
virtual void update(const Triple< T > &t)
Updates the weighted tree data structure given a contracted triple.
Definition: SaveDynamic.h:128
ogdf::steiner_tree::Triple::s2
node s2() const
Definition: Triple.h:64
ogdf::steiner_tree::Triple::s1
node s1() const
Definition: Triple.h:60
ogdf::steiner_tree::SaveDynamic::gain
virtual T gain(node u, node v, node w) const
Returns the gain (sum of save edge costs) of the given triple, calculated by an LCA query.
Definition: SaveDynamic.h:82
ogdf::LCA::call
node call(node u, node v) const
Returns the LCA of two nodes u and v.
ogdf::steiner_tree::SaveDynamic::SaveDynamic
SaveDynamic(EdgeWeightedGraphCopy< T > &steinerTree)
Builds a weighted binary tree based on the given terminal spanning tree.
Definition: SaveDynamic.h:58
ogdf::steiner_tree::SaveDynamic::m_tree
Graph m_tree
The weighted binary tree to represent the edge weight hierarchy.
Definition: SaveDynamic.h:271
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
Triple.h
Definition of a Triple used in contraction-based approximation algorithm for the minimum Steiner tree...
ogdf::steiner_tree::Save
This class serves as an interface for different approaches concerning the calculation of save edges.
Definition: Save.h:45
ogdf::Graph::delEdge
virtual void delEdge(edge e)
Removes edge e from the graph.
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
LCA.h
The Sparse Table Algorithm for the Least Common Ancestor problem as proposed by Bender and Farach-Col...
ogdf::steiner_tree::buildHeaviestEdgeInComponentTree
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...
Definition: common_algorithms.h:53
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
ogdf::steiner_tree::SaveDynamic::m_steinerTree
const EdgeWeightedGraphCopy< T > * m_steinerTree
The underlying terminal spanning tree this weighted tree instance represents.
Definition: SaveDynamic.h:277
common_algorithms.h
Algorithms used by at least two functions of Steiner tree code or its internal helpers.
ogdf::NodeElement::adjEntries
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition: Graph_d.h:200
ogdf::steiner_tree::SaveDynamic::lca
node lca(node u, node v) const
Returns the node in m_tree that is the LCA of two nodes.
Definition: SaveDynamic.h:251
ogdf::steiner_tree::SaveDynamic::saveWeight
virtual T saveWeight(node u, node v) const
Determines the weight of the save edge between two nodes by a LCA query.
Definition: SaveDynamic.h:99
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::LCA
Implements the <O(n log n), O(1)>-time "sparse table" algorithm by Bender and Farach-Colton to comput...
Definition: LCA.h:52
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::steiner_tree::Triple::s0
node s0() const
Definition: Triple.h:56
ogdf::steiner_tree::SaveDynamic
Dynamically updatable weighted Tree for determining save edges via LCA computation.
Definition: SaveDynamic.h:50
ogdf::Graph::newNode
node newNode()
Creates a new node and returns it.
ogdf::EdgeWeightedGraphCopy
Definition: EdgeWeightedGraphCopy.h:40
ogdf::steiner_tree::SaveDynamic::weight
T weight(edge e) const
Returns the weight of an edge in the terminal tree or 0.
Definition: SaveDynamic.h:259
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::steiner_tree::SaveDynamic::~SaveDynamic
virtual ~SaveDynamic()
Definition: SaveDynamic.h:69
ogdf::steiner_tree::SaveDynamic::saveEdge
virtual edge saveEdge(node u, node v) const
Determines the save edge between two nodes by a LCA query.
Definition: SaveDynamic.h:111
ogdf::steiner_tree::SaveDynamic::m_treeEdge
NodeArray< edge > m_treeEdge
Maps each inner node of m_tree to an edge in m_steinerTree.
Definition: SaveDynamic.h:272
Save.h
Interface for various LCA methods.
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::steiner_tree::SaveDynamic::m_root
node m_root
The root node of the weighted binary tree.
Definition: SaveDynamic.h:273
ogdf::steiner_tree::SaveDynamic::m_cTerminals
NodeArray< node > m_cTerminals
Connects terminal nodes in the terminal spanning tree to their leafs in the weighted tree.
Definition: SaveDynamic.h:278
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169