Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
FullComponentDecisions.h
Go to the documentation of this file.
1
32#pragma once
33
34namespace ogdf {
35namespace steiner_tree {
36
45 static inline double computeDensity(int n, int m) {
46 double density(2.0 * m);
47 density /= n;
48 density /= n - 1;
49 return density;
50 }
51
59 static bool shouldUseAllTerminalDijkstra(int n, int m, int t) {
60 double coverage(t);
61 coverage /= n;
62 if (coverage < 0.07) {
63 return true;
64 }
65
66 double density {computeDensity(n, m)};
67 if (density > 0.5) {
68 return false;
69 }
70 if (density > 0.1 && coverage > 0.3) {
71 return false;
72 }
73 return true;
74 }
75
82 static inline bool shouldUseAllNodeDijkstra(int n, int m) {
83 return computeDensity(n, m) <= 0.15;
84 }
85
94 static bool shouldUseDijkstra(int k, int n, int m, int t) {
95 if (k == 3) {
96 return shouldUseAllTerminalDijkstra(n, m, t);
97 }
98 return shouldUseAllNodeDijkstra(n, m);
99 }
100
108 static inline bool shouldUseErickson(int n, int m) { return computeDensity(n, m) < 0.0029; }
109};
110
111}
112}
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Contains rules of thumb to decide which (sub-)algorithms to use for the generation of full components...
static bool shouldUseAllNodeDijkstra(int n, int m)
Returns true iff the rule of thumb predicts to call Dijkstra on all nodes instead of the algorithm by...
static bool shouldUseErickson(int n, int m)
Returns true iff the rule of thumb predicts to use the algorithm by Erickson et al instead of the Dre...
static bool shouldUseAllTerminalDijkstra(int n, int m, int t)
Returns true iff the rule of thumb predicts to call Dijkstra on all terminals instead of the algorith...
static double computeDensity(int n, int m)
Computes the ratio of edges to potential edges in a simple graph.
static bool shouldUseDijkstra(int k, int n, int m, int t)
Returns true iff the rule of thumb predicts to use multiple Dijkstra calls instead of the algorithm b...