# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
SpannerElkinNeiman.h
Go to the documentation of this file.
1
33#pragma once
34
35#include <ogdf/basic/Queue.h>
39
40namespace ogdf {
41
94template<typename TWeight>
95class SpannerElkinNeiman : public SpannerModule<TWeight> {
97 const Graph* m_G;
98
100
101 double m_c;
102 double m_beta;
103 int m_k;
105
114 const double DEFAULT_EPSILON = 0.8;
115
116public:
118
119 SpannerElkinNeiman(double epsilon) : SpannerModule<TWeight>() { setEpsilon(epsilon); }
120
126 void setEpsilon(double epsilon) {
127 OGDF_ASSERT(epsilon > 0);
128 m_c = 3.0 / epsilon; // see corollary 8.
129 }
130
132 virtual bool preconditionsOk(const GraphAttributes& GA, double stretch,
133 std::string& error) override {
134 if (GA.directed()) {
135 error = "The graph must be undirected";
136 return false;
137 }
138 double integralPart;
139 if (std::modf(stretch, &integralPart) != 0.0) {
140 error = "The stretch is required to be an integer, not " + to_string(m_stretch);
141 return false;
142 }
143 int intStretch = static_cast<int>(stretch);
144 if (intStretch < 1) {
145 error = "The stretch must be >= 1.0";
146 return false;
147 }
148 if (intStretch % 2 == 0) {
149 error = "The stretch must be odd";
150 return false;
151 }
153 error = "The graph must be unweighted";
154 return false;
155 }
156 return true;
157 }
158
159private:
161 virtual void init(const GraphAttributes& GA, double stretch, GraphCopySimple& spanner,
162 EdgeArray<bool>& inSpanner) override {
164 m_intStretch = static_cast<int>(stretch);
165 m_k = (m_intStretch + 1) / 2;
166 m_G = &GA.constGraph();
167 m_beta = log(m_c * m_G->numberOfNodes()) / m_k; // log is logarithm naturale
168 }
169
170 struct BfsNode {
172 int depth;
174
175 BfsNode(node _n, double _depth, edge _p) : n(_n), depth(_depth), p(_p) { }
176 };
177
179 virtual typename SpannerModule<TWeight>::ReturnType execute() override {
181 // First, assign each node the random variable. This is done here, so the first
182 // feasibility check can be done fast (This is the one that mostly fails).
183 for (node u : m_G->nodes) {
185 // Feasibility check 1: See proof of Theorem 1 and "Standard Centralized Model" in 2.1.1
186 if (m_eps.geq(r[u], static_cast<double>(m_k))) {
188 }
189 }
190
191 // Paper: u broadcasts a message x within distance k
192 // Here: Fix a receiving node x and find all nodes u within distance k, that send messages to x
193 for (node x : m_G->nodes) {
194 // values[u]: x recieves the value from u (m_u(x))
195 NodeArray<double> values(*m_G, std::numeric_limits<double>::lowest());
196
197 // firstEdge[u]: The first edge from the path x->u (p_u(x))
198 // This is the last edge from the path u->x as described in the paper
199 NodeArray<edge> firstEdge(*m_G, nullptr);
200
202 NodeArray<bool> marked(*m_G, false); // Just visit a node once.
203
204 queue.emplace(x, 0, nullptr); // p==nullptr: we do not have a first edge
205 marked[x] = true; // Do not revisit x
206 while (!queue.empty()) {
207 BfsNode bfsNode = queue.pop();
208 int distance = bfsNode.depth + 1;
209
212 if (marked[u]) {
213 continue;
214 }
215
216 edge p = bfsNode.p;
217 if (p == nullptr) {
218 p = adj->theEdge(); // Set the first edge: Only happens in the first expansion step of the bfs
219 }
220
221 values[u] = r[u] - distance;
222 firstEdge[u] = p;
223
224 if (distance < m_k) { // distance is <= m_k when a dfs node is popped from the stack.
225 queue.emplace(u, distance, p);
226 marked[u] = true;
227 }
228 }
229 }
230
232
233 // find edges that must be added to the spanner:
234 // m(x) = max{m_u(x) | u in V}
235 double maxValue = std::numeric_limits<double>::lowest();
236 for (node u : m_G->nodes) {
237 Math::updateMax(maxValue, values[u]);
238 }
239 maxValue -= 1.0; // m(x)-1
240
242
243 // Add the edges (sets C(x) in the paper) to the spanner.
244 for (node u : m_G->nodes) {
245 if (values[u] != std::numeric_limits<double>::lowest()
246 && m_eps.geq(values[u], maxValue)) {
247 edge e = firstEdge[u];
248 if (!(*m_inSpanner)[e]) {
249 m_spanner->newEdge(e);
250 (*m_inSpanner)[e] = true;
251 }
252 }
253 }
254
256 }
257
258 // Feasibility check 2: See proof of Theorem 1 and "Standard Centralized Model" in 2.1.1
259 // Note: The paper states, that the spanner must have >= n-1 edges. This does not work, for
260 // all graphs, e.g. a forest as an input. The paper never states, that the graph must be connected
261 // nor that it can be disconnected. Using n-<amount components> does work and solves the issue above.
265 }
266
268 }
269
275};
276
283template<typename TWeight>
289
290}
A wrapper class for iterating calls to spanner algorithms.
Basic module for spanner algorithms.
Declaration and implementation of list-based queues (classes QueuePure<E> and Queue<E>).
Definition Graph_d.h:79
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
std::enable_if< std::is_integral< T >::value, bool >::type geq(const T &x, const T &y) const
Compare if x is GEQ to y for integral types.
Stores additional attributes of a graph (like layout information).
static const long edgeDoubleWeight
Corresponds to edge attribute doubleWeight(edge).
static const long edgeIntWeight
Corresponds to edge attribute intWeight(edge).
Copies of graphs with mapping between nodes and edges.
Definition GraphCopy.h:59
edge newEdge(edge eOrig)
Creates a new edge in the graph copy with original edge eOrig.
Definition GraphCopy.h:188
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
int numberOfNodes() const
Returns the number of nodes in the graph.
Definition Graph_d.h:622
int numberOfEdges() const
Returns the number of edges in the graph.
Definition Graph_d.h:625
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition Graph_d.h:589
ReturnType
The return type of a module.
Definition Module.h:50
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Implementation of list-based queues.
Definition Queue.h:50
Randomized multiplicative spanner calculation by propagating random messages through the graph.
int m_intStretch
m_stretch, but as an integer
double m_c
the parameter for the exponential distribution.
double m_beta
The parameter for the exponential distribution.
virtual SpannerModule< TWeight >::ReturnType execute() override
Executes the core algorithm.
virtual void init(const GraphAttributes &GA, double stretch, GraphCopySimple &spanner, EdgeArray< bool > &inSpanner) override
Initializes members and create an empty spanner.
int m_k
the parameter k derived from the stretch
virtual bool preconditionsOk(const GraphAttributes &GA, double stretch, std::string &error) override
void setEpsilon(double epsilon)
Sets the epsilon for this algorithm.
const Graph * m_G
The original graph.
const double DEFAULT_EPSILON
The default value for epsilon.
Use the ogdf::SpannerIteratedWrapper to execute the ogdf::SpannerElkinNeiman algorithm up to 200 time...
A implementation-independed wrapper class to execute a spanner algorithm multiple times.
Interface for spanner algorithms.
void assertTimeLeft()
Assert, that time is left.
virtual void init(const GraphAttributes &GA, double stretch, GraphCopySimple &spanner, EdgeArray< bool > &inSpanner)
Initializes members and create an empty spanner.
const GraphAttributes * m_GA
EdgeArray< bool > * m_inSpanner
GraphCopySimple * m_spanner
int connectedComponents(const Graph &G, NodeArray< int > &component, List< node > *isolated=nullptr)
Computes the connected components of G and optionally generates a list of isolated nodes.
#define OGDF_ASSERT(expr)
Definition basic.h:41
double randomDoubleExponential(double beta)
Returns a random double value from the exponential distribution.
int r[]