Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

MinSteinerTreeKou.h
Go to the documentation of this file.
1 
34 #pragma once
35 
36 #include <ogdf/basic/List.h>
39 
40 #include <ogdf/graphalg/Dijkstra.h>
41 
42 namespace ogdf {
43 
54 template<typename T>
56 public:
58 
59  virtual ~MinSteinerTreeKou() { }
60 
61 protected:
70  virtual T computeSteinerTree(
71  const EdgeWeightedGraph<T> &G,
72  const List<node> &terminals,
73  const NodeArray<bool> &isTerminal,
74  EdgeWeightedGraphCopy<T> *&finalSteinerTree) override;
75 
83  void calculateCompleteGraph(const EdgeWeightedGraph<T> &wG, const List<node> &terminals, EdgeArray<List<edge>> &predecessor,
84  EdgeWeightedGraphCopy<T> &completeTerminalGraph);
85 
94  void reinsertShortestPaths(const EdgeWeightedGraphCopy<T> &completeTerminalGraph, const EdgeArray<List<edge>> &ssspPred,
95  const NodeArray<edge> &mstPred, EdgeWeightedGraphCopy<T> &finalSteinerTree, const EdgeWeightedGraph<T> &wG);
96 
103  void insertPath(const List<edge> &ssspPred, EdgeWeightedGraphCopy<T> &finalSteinerTree, const EdgeWeightedGraph<T> &wG);
104 };
105 
106 template<typename T>
108 {
109  EdgeWeightedGraphCopy<T> completeTerminalGraph;
110  completeTerminalGraph.createEmpty(G);
111 
112  for (node v : terminals) {
113  completeTerminalGraph.newNode(v);
114  }
115 
116  List<edge> steinerTreeEdges;
117  EdgeArray<List<edge>> ssspPred(completeTerminalGraph);
118 
119  calculateCompleteGraph(G, terminals, ssspPred, completeTerminalGraph);
120 
121  NodeArray<edge> mstPred(completeTerminalGraph);
122  computeMinST(completeTerminalGraph, completeTerminalGraph.edgeWeights(), mstPred);
123 
124  finalSteinerTree = new EdgeWeightedGraphCopy<T>();
125  finalSteinerTree->createEmpty(G);
126 
127  reinsertShortestPaths(completeTerminalGraph, ssspPred, mstPred, *finalSteinerTree, G);
128 
129  T mstWeight = makeMinimumSpanningTree(*finalSteinerTree, finalSteinerTree->edgeWeights());
130  mstWeight -= MinSteinerTreeModule<T>::pruneAllDanglingSteinerPaths(*finalSteinerTree, isTerminal);
131 
132  return mstWeight;
133 }
134 
135 template<typename T>
137 {
138  Dijkstra<T> sssp;
139  for (node u = completeTerminalGraph.firstNode(); u->succ(); u = u->succ()) {
140  NodeArray<T> d;
142  sssp.call(wG, wG.edgeWeights(), completeTerminalGraph.original(u), pi, d);
143  for (node v = u->succ(); v; v = v->succ()) {
144  edge e = completeTerminalGraph.newEdge(u, v, d[completeTerminalGraph.original(v)]);
145  predecessor[e].clear();
146  for (node t = completeTerminalGraph.original(v); pi[t]; t = pi[t]->opposite(t)) {
147  predecessor[e].pushBack(pi[t]);
148  }
149  }
150  }
151 }
152 
153 template<typename T>
155  const EdgeArray<List<edge>> &ssspPred,
156  const NodeArray<edge> &mstPred,
157  EdgeWeightedGraphCopy<T> &finalSteinerTree,
158  const EdgeWeightedGraph<T> &wG)
159 {
160  for(node u : completeTerminalGraph.nodes) {
161  if (mstPred[u]) {
162  insertPath(ssspPred[mstPred[u]], finalSteinerTree, wG);
163  }
164  }
165 }
166 
167 template<typename T>
169 {
170  for (edge e : ssspPred)
171  {
172  if (e != nullptr && finalSteinerTree.chain(e).size() == 0)
173  {
174  node edgeSource = e->source();
175  node edgeTarget = e->target();
176 
177  node stSource = finalSteinerTree.copy(edgeSource);
178  if (stSource == nullptr) {
179  stSource = finalSteinerTree.newNode(edgeSource);
180  }
181 
182  node stTarget = finalSteinerTree.copy(edgeTarget);
183  if (stTarget == nullptr) {
184  stTarget = finalSteinerTree.newNode(edgeTarget);
185  }
186 
187  if (e->source() == finalSteinerTree.original(stSource)) {
188  edge newE = finalSteinerTree.newEdge(stSource, stTarget, wG.weight(e));
189  finalSteinerTree.setEdge(e, newE);
190  }
191  }
192  }
193 }
194 
195 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::GraphCopy::original
const Graph & original() const
Returns a reference to the original graph.
Definition: GraphCopy.h:292
ogdf::EdgeWeightedGraph::weight
T weight(const edge e) const
Definition: EdgeWeightedGraph.h:68
ogdf::MinSteinerTreeKou::~MinSteinerTreeKou
virtual ~MinSteinerTreeKou()
Definition: MinSteinerTreeKou.h:59
ogdf::MinSteinerTreeKou::reinsertShortestPaths
void reinsertShortestPaths(const EdgeWeightedGraphCopy< T > &completeTerminalGraph, const EdgeArray< List< edge >> &ssspPred, const NodeArray< edge > &mstPred, EdgeWeightedGraphCopy< T > &finalSteinerTree, const EdgeWeightedGraph< T > &wG)
Swaps an edge in the complete terminal graph with the corresponding shortest path in the original gra...
Definition: MinSteinerTreeKou.h:154
ogdf::computeMinST
T computeMinST(const Graph &G, const EdgeArray< T > &weight, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree using Prim's algorithm.
Definition: extended_graph_alg.h:273
ogdf::EdgeWeightedGraphCopy::newEdge
edge newEdge(node u, node v, T weight)
Definition: EdgeWeightedGraphCopy.h:166
ogdf::NodeArray< bool >
ogdf::EdgeArray
Dynamic arrays indexed with edges.
Definition: EdgeArray.h:112
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::MinSteinerTreeModule
Serves as an interface for various methods to compute or approximate minimum Steiner trees on undirec...
Definition: MinSteinerTreeModule.h:58
MinSteinerTreeModule.h
Declaration of ogdf::MinSteinerTreeModule.
ogdf::Dijkstra
Dijkstra's single source shortest path algorithm.
Definition: Dijkstra.h:54
ogdf::Graph::nodes
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition: Graph_d.h:568
ogdf::EdgeWeightedGraph
Definition: EdgeWeightedGraph.h:39
ogdf::MinSteinerTreeModule::pruneAllDanglingSteinerPaths
static T pruneAllDanglingSteinerPaths(EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
Prunes nonterminal leaves and their paths to terminal or branching nodes.
Definition: MinSteinerTreeModule.h:500
ogdf::GraphCopy::chain
const List< edge > & chain(edge e) const
Returns the list of edges coresponding to edge e.
Definition: GraphCopy.h:348
ogdf::EdgeWeightedGraph::edgeWeights
const EdgeArray< T > & edgeWeights() const
Definition: EdgeWeightedGraph.h:73
ogdf::Dijkstra::call
void call(const Graph &G, const EdgeArray< T > &weight, const List< node > &sources, NodeArray< edge > &predecessor, NodeArray< T > &distance, bool directed=false, bool arcsReversed=false, node target=nullptr, T maxLength=std::numeric_limits< T >::max())
Calculates, based on the graph G with corresponding edge costs and source nodes, the shortest paths a...
Definition: Dijkstra.h:267
ogdf::Graph::firstNode
node firstNode() const
Returns the first node in the list of all nodes.
Definition: Graph_d.h:621
Dijkstra.h
Implementation of Dijkstra's single source shortest path algorithm.
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
ogdf::Math::pi
constexpr double pi
The constant .
Definition: Math.h:62
ogdf::GraphCopy::setEdge
void setEdge(edge eOrig, edge eCopy)
sets eOrig to be the corresponding original edge of eCopy and vice versa
ogdf::MinSteinerTreeKou::computeSteinerTree
virtual T computeSteinerTree(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
Builds a minimum Steiner tree given a weighted graph and a list of terminals.
Definition: MinSteinerTreeKou.h:107
ogdf::MinSteinerTreeKou::MinSteinerTreeKou
MinSteinerTreeKou()
Definition: MinSteinerTreeKou.h:57
ogdf::EdgeWeightedGraphCopy::edgeWeights
const EdgeArray< T > & edgeWeights() const
Definition: EdgeWeightedGraphCopy.h:57
ogdf::makeMinimumSpanningTree
T makeMinimumSpanningTree(Graph &G, const EdgeArray< T > &weight)
Reduce a graph to its minimum spanning tree (MST) using Kruskal's algorithm.
Definition: extended_graph_alg.h:399
ogdf::NodeElement::succ
node succ() const
Returns the successor in the list of all nodes.
Definition: Graph_d.h:218
ogdf::EdgeWeightedGraphCopy
Definition: EdgeWeightedGraphCopy.h:40
ogdf::EdgeWeightedGraphCopy::createEmpty
void createEmpty(const Graph &wG)
Definition: EdgeWeightedGraphCopy.h:159
ogdf::MinSteinerTreeKou::insertPath
void insertPath(const List< edge > &ssspPred, EdgeWeightedGraphCopy< T > &finalSteinerTree, const EdgeWeightedGraph< T > &wG)
Inserts a shortest path corresponding to an edge in the complete terminal graph.
Definition: MinSteinerTreeKou.h:168
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
List.h
Declaration of doubly linked lists and iterators.
ogdf::List::size
int size() const
Returns the number of elements in the list.
Definition: List.h:1313
ogdf::MinSteinerTreeKou
This class implements the Minimum Steiner Tree 2-approximation algorithm by Kou et al.
Definition: MinSteinerTreeKou.h:55
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::GraphCopy::newNode
node newNode(node vOrig)
Creates a new node in the graph copy with original node vOrig.
Definition: GraphCopy.h:418
ogdf::MinSteinerTreeKou::calculateCompleteGraph
void calculateCompleteGraph(const EdgeWeightedGraph< T > &wG, const List< node > &terminals, EdgeArray< List< edge >> &predecessor, EdgeWeightedGraphCopy< T > &completeTerminalGraph)
Builds a complete terminal graph.
Definition: MinSteinerTreeKou.h:136