Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

common_algorithms.h
Go to the documentation of this file.
1 
33 #pragma once
34 
37 
38 //#define OGDF_COMMON_ALG_FIND_BEST_TAKAHASHI_ROOT
39 
40 
41 namespace ogdf {
42 namespace steiner_tree {
43 
52 template<typename T>
54  const EdgeWeightedGraphCopy<T> &inputTree,
55  NodeArray<node> &externalNodes,
56  NodeArray<edge> &treeEdge,
57  Graph &outputTree)
58 {
59  // sort edges by weight
60  Array<Prioritized<edge, T>> sortEdges(inputTree.numberOfEdges());
61  int i = 0;
62  for(edge e : inputTree.edges) {
63  sortEdges[i] = Prioritized<edge,T>(e, inputTree.weight(e));
64  ++i;
65  }
66  sortEdges.quicksort();
67 
68  // insert edges into forest (which in the end makes up a tree)
69  NodeArray<node *> root(outputTree);
70  List<node *> garbage;
71  node edgeNode = nullptr;
72  for (i = 0; i < inputTree.numberOfEdges(); ++i) {
73  edgeNode = outputTree.newNode();
74  edge e = sortEdges[i].item();
75  treeEdge[edgeNode] = e;
76 
77  node u = e->source();
78  node v = e->target();
79  if (externalNodes[u]) {
80  node *uRoot = root[externalNodes[u]];
81  OGDF_ASSERT(uRoot);
82  while (root[*uRoot] != uRoot) {
83  *uRoot = *root[*uRoot];
84  uRoot = root[*uRoot];
85  OGDF_ASSERT(uRoot);
86  }
87  outputTree.newEdge(edgeNode, *uRoot);
88  root[edgeNode] = uRoot;
89  if (externalNodes[v]) {
90  node *vRoot = root[externalNodes[v]];
91  OGDF_ASSERT(vRoot);
92  while (root[*vRoot] != vRoot) {
93  *vRoot = *root[*vRoot];
94  vRoot = root[*vRoot];
95  OGDF_ASSERT(vRoot);
96  }
97  outputTree.newEdge(edgeNode, *vRoot);
98  *vRoot = edgeNode;
99  } else {
100  externalNodes[v] = edgeNode;
101  }
102  } else {
103  externalNodes[u] = edgeNode;
104  if (externalNodes[v]) {
105  node *vRoot = root[externalNodes[v]];
106  OGDF_ASSERT(vRoot);
107  while (root[*vRoot] != vRoot) {
108  *vRoot = *root[*vRoot];
109  vRoot = root[*vRoot];
110  OGDF_ASSERT(vRoot);
111  }
112  outputTree.newEdge(edgeNode, *vRoot);
113  root[edgeNode] = vRoot;
114  } else {
115  root[edgeNode] = new node;
116  garbage.pushBack(root[edgeNode]);
117  externalNodes[v] = edgeNode;
118  }
119  }
120  *root[edgeNode] = edgeNode;
121  }
122  OGDF_ASSERT(edgeNode);
123 
124  // garbage collect
125  for(node *p : garbage) {
126  delete p;
127  }
128 
129  return edgeNode;
130 }
131 
132 
144 template <typename T>
145 void contractTripleInSteinerTree(const Triple<T> &t, EdgeWeightedGraphCopy<T> &st, edge save0, edge save1, edge save2, edge &ne0, edge &ne1)
146 {
147  if (save0 == save1) {
148  st.delEdge(save1);
149  st.delEdge(save2);
150  } else {
151  st.delEdge(save0);
152  st.delEdge(save1);
153  }
154  ne0 = st.newEdge(st.copy(t.s0()), st.copy(t.s1()), 0);
155  ne1 = st.newEdge(st.copy(t.s0()), st.copy(t.s2()), 0);
156 }
157 
158 template <typename T>
160 {
161  edge ne0, ne1;
162  contractTripleInSteinerTree(t, st, e0, e1, e2, ne0, ne1);
163 }
164 
165 
166 template<typename T>
167 T obtainFinalSteinerTree(const EdgeWeightedGraph<T> &G, const NodeArray<bool> &isTerminal, const NodeArray<bool> &isOriginalTerminal, EdgeWeightedGraphCopy<T> *&finalSteinerTree)
168 {
169  List<node> terminals;
170  MinSteinerTreeModule<T>::getTerminals(terminals, G, isTerminal);
171 
172  finalSteinerTree = nullptr;
174 #ifdef OGDF_COMMON_ALG_FIND_BEST_TAKAHASHI_ROOT
175  // find minimum Steiner tree of G among Takahashi approximations for each start node
176  T bestMstWeight = std::numeric_limits<T>::max();
177  for (node v : terminals) {
178  EdgeWeightedGraphCopy<T> *tmpSteinerTree;
179  T tmpMstWeight = mstt.call(G, terminals, isTerminal, isOriginalTerminal, tmpSteinerTree, v);
180  if (tmpMstWeight < bestMstWeight) {
181  bestMstWeight = tmpMstWeight;
182  delete finalSteinerTree;
183  finalSteinerTree = tmpSteinerTree;
184  } else {
185  delete tmpSteinerTree;
186  }
187  }
188  return bestMstWeight;
189 #else
190  return mstt.call(G, terminals, isTerminal, isOriginalTerminal, finalSteinerTree);
191 #endif
192 }
193 
194 }
195 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
MinSteinerTreeTakahashi.h
Implementation of the 2(1-1/l)-approximation algorithm for the minimum Steiner tree problem by Matsuy...
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::Graph::newEdge
edge newEdge(node v, node w)
Creates a new edge (v,w) and returns it.
ogdf::MinSteinerTreeTakahashi::call
virtual T call(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree, const node startNode)
An extended call method with specific start node.
Definition: MinSteinerTreeTakahashi.h:70
ogdf::steiner_tree::Triple::s2
node s2() const
Definition: Triple.h:64
ogdf::GraphCopy::delEdge
virtual void delEdge(edge e) override
Removes edge e and clears the list of edges corresponding to e's original edge.
ogdf::steiner_tree::obtainFinalSteinerTree
T obtainFinalSteinerTree(const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const NodeArray< bool > &isOriginalTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
Definition: common_algorithms.h:167
ogdf::steiner_tree::Triple::s1
node s1() const
Definition: Triple.h:60
ogdf::EdgeWeightedGraphCopy::newEdge
edge newEdge(node u, node v, T weight)
Definition: EdgeWeightedGraphCopy.h:166
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::GraphCopy::copy
node copy(node v) const
Returns the node in the graph copy corresponding to v.
Definition: GraphCopy.h:341
EdgeWeightedGraphCopy.h
Extends the GraphCopy concept to weighted graphs.
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::Graph::numberOfEdges
int numberOfEdges() const
Returns the number of edges in the graph.
Definition: Graph_d.h:604
ogdf::EdgeWeightedGraph
Definition: EdgeWeightedGraph.h:39
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::node
NodeElement * node
The type of nodes.
Definition: Graph_d.h:63
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
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::Graph::edges
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition: Graph_d.h:571
ogdf::Graph::newNode
node newNode()
Creates a new node and returns it.
ogdf::MinSteinerTreeTakahashi
This class implements the minimum Steiner tree 2-approximation algorithm by Takahashi and Matsuyama w...
Definition: MinSteinerTreeTakahashi.h:57
ogdf::EdgeWeightedGraphCopy::weight
T weight(const edge e) const
Definition: EdgeWeightedGraphCopy.h:51
ogdf::EdgeWeightedGraphCopy
Definition: EdgeWeightedGraphCopy.h:40
ogdf::Prioritized
Augments any data elements of type X with keys of type Priority. This class is also its own Comparer.
Definition: comparer.h:279
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::Array::quicksort
void quicksort()
Sorts array using Quicksort.
Definition: Array.h:617
ogdf::MinSteinerTreeModule::getTerminals
static void getTerminals(List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Generates a list (as List<node>) of all terminals.
Definition: MinSteinerTreeModule.h:306
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::List::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:1374