FullComponentDecisions.h

Go to the documentation of this file.

 
#pragma once
 
namespace ogdf {
namespace steiner_tree {
 
struct FullComponentDecisions {
    static inline double computeDensity(int n, int m) {
        double density(2.0 * m);
        density /= n;
        density /= n - 1;
        return density;
    }
 
    static bool shouldUseAllTerminalDijkstra(int n, int m, int t) {
        double coverage(t);
        coverage /= n;
        if (coverage < 0.07) {
            return true;
        }
 
        double density {computeDensity(n, m)};
        if (density > 0.5) {
            return false;
        }
        if (density > 0.1 && coverage > 0.3) {
            return false;
        }
        return true;
    }
 
    static inline bool shouldUseAllNodeDijkstra(int n, int m) {
        return computeDensity(n, m) <= 0.15;
    }
 
    static bool shouldUseDijkstra(int k, int n, int m, int t) {
        if (k == 3) {
            return shouldUseAllTerminalDijkstra(n, m, t);
        }
        return shouldUseAllNodeDijkstra(n, m);
    }
 
    static inline bool shouldUseErickson(int n, int m) { return computeDensity(n, m) < 0.0029; }
};
 
}
}