"""Bases of Theorem 14.1 (thm:connectivity), Theorem 11.4 (thm:bdd), and the previous
bounds quoted for them in tab:apps and tab:apps-affected.

Each line checks base**exponent < stated value, where the stated value is the rounded-up base
printed in the manuscript. c3 = (3/(4 pi)) arccos(5/6); F4 is the Arb upper bound of constants.py;
gamma5 = arccos(4/5)/pi is the constant of thm:cut-sweep-p; omega <= 9/4 as in thm:connectivity(d).
Bases per edge (m) use the width 7m/48; bases per dn use m <= dn/2, i.e. the exponent 7/96.
Double precision suffices: every margin printed is above 1e-6.
Run from the repository root:  python3 experiments/algorithmic-consequences/connectivity_bases.py
"""
import math

C3 = 3 / (4 * math.pi) * math.acos(5 / 6)
F4 = 0.24577197475           # Arb upper bound (constants.py)
G5 = math.acos(4 / 5) / math.pi
OMEGA = 9 / 4
H = 2 + math.sqrt(2)         # Cygan-Kratsch-Nederlof, Theorems 4.3 and 4.6
T = 2 + 2 ** (OMEGA / 2)     # Bodlaender-Cygan-Kratsch-Nederlof, Theorem 3.18
T3 = 1 + 2 ** (OMEGA / 2)    # the same with the degree-3 trick of their Corollary 3.19

CHECKS = [
    # (label, base, exponent, stated value[, tolerance])
    ("gamma5 < 0.20484", G5, 1, 0.20484),
    ("5 gamma5 / 2 < 0.5121", 5 * G5 / 2, 1, 0.5121),
    # thm:connectivity (a)
    ("FVS/CVC Delta<=4 (cutwidth): 2^(m/6) <= 2^(n/3)", 2, 1 / 3, 1.2600),
    ("FVS/CVC Delta<=5 (cutwidth): 2^(gamma5 m) <= 2^(5 gamma5 n/2)", 2, 5 * G5 / 2, 1.4262),
    ("Steiner Delta<=3: 3^(c3 n)", 3, C3, 1.1661),
    ("Steiner Delta<=4: 3^(F4 n)", 3, F4, 1.3100),
    ("FVS Delta<=6: 3^(7n/16)", 3, 7 / 16, 1.6172),
    ("FVS det. Delta<=4: 5^(F4 n)", 5, F4, 1.4853),
    # (b)
    ("4^tw problems Delta<=3: 4^(c3 n)", 4, C3, 1.2139),
    ("4^tw problems Delta<=4: 4^(F4 n)", 4, F4, 1.4060),
    ("4^tw problems Delta<=5: 4^(11n/32)", 4, 11 / 32, 1.6105),
    ("Min Leaf (Max Internal Spanning Tree) Delta<=6: 4^(7n/16)", 4, 7 / 16, 1.8341),
    ("CDS Delta<=3: 3^(c3 n)", 3, C3, 1.1661),
    # (c)
    ("Hamiltonian Cycle Delta<=3: (1+sqrt2)^(c3 n)", 1 + math.sqrt(2), C3, 1.1312),
    ("Hamiltonian Cycle Delta<=4 (cutwidth): (1+sqrt2)^(n/3)", 1 + math.sqrt(2), 1 / 3, 1.3416),
    ("Hamiltonian Cycle, Longest Path Delta<=5: (2+sqrt2)^(11n/32)", H, 11 / 32, 1.5252),
    ("Longest Path Delta<=3: (2+sqrt2)^(c3 n)", H, C3, 1.1874),
    ("Longest Path Delta<=4: (2+sqrt2)^(F4 n)", H, F4, 1.3523),
    # (d), omega <= 9/4
    ("TSP Delta<=3: (1+2^(w/2))^(c3 n)", T3, C3, 1.1757),
    ("TSP Delta<=4: (2+2^(w/2))^(F4 n)", T, F4, 1.4214),
    ("TSP Delta<=5: (2+2^(w/2))^(11n/32)", T, 11 / 32, 1.6352),
    ("TSP Delta<=6: (2+2^(w/2))^(7n/16)", T, 7 / 16, 1.8699),
    # (e)
    ("directed Delta<=3: 6^(c3 n)", 6, C3, 1.2848),
    ("directed Delta<=4: 6^(F4 n)", 6, F4, 1.5533),
    # (f)
    ("Co-Path Packing DP: 5^(5k/8)", 5, 5 / 8, 2.7344),
    ("k-Co-Path Set DP: 4^(5k/16) = 2^(5k/8)", 4, 5 / 16, 1.5423),
    # (g)
    ("Hamiltonian Cycle per edge: (2+sqrt2)^(7m/48)", H, 7 / 48, 1.1962),
    ("TSP per edge: (2+2^(w/2))^(7m/48)", T, 7 / 48, 1.2320),
    ("Hamiltonian Cycle per dn: (2+sqrt2)^(7dn/96)", H, 7 / 96, 1.0937),
    ("TSP per dn: (2+2^(w/2))^(7dn/96)", T, 7 / 96, 1.1100),
    # thm:bdd
    ("Min Weight DS Delta<=3: 3^(c3 n)", 3, C3, 1.1661),
    ("MWIS Delta<=3: 2^(c3 n)", 2, C3, 1.1018),
    ("MWIS Delta<=4: 2^(F4 n)", 2, F4, 1.1858),
    ("Max k-Vertex Cover Delta<=3: 2^(c3 n)", 2, C3, 1.1018),
    ("IDS Delta<=3: 3^(c3 n)", 3, C3, 1.1661),
    ("IDS Delta<=4: 3^(F4 n)", 3, F4, 1.3100),
    ("Upper Domination Delta<=3: 6^(c3 n)", 6, C3, 1.2848),
    ("EDS Delta<=3: 3^(c3 n)", 3, C3, 1.1661),
    ("OCT Delta<=4: 2^(n/3)", 2, 1 / 3, 1.2600),
    ("OCT Delta<=5: 2^(5 gamma5 n/2)", 2, 5 * G5 / 2, 1.4262),
    ("proof of thm:bdd: 3^c3 < 1.16604", 3, C3, 1.16604, 1e-5),
    ("proof of thm:bdd: 2^c3 < 1.10177", 2, C3, 1.10177, 1e-5),
    ("proof of thm:bdd: 6^c3 < 1.28471", 6, C3, 1.28471, 1e-5),
    ("proof of thm:bdd: 2^F4 < 1.18573", 2, F4, 1.18573, 1e-5),
    ("proof of thm:bdd: 3^F4 < 1.30998", 3, F4, 1.30998, 1e-5),
    ("proof of thm:bdd: 2^(1/3) < 1.25993", 2, 1 / 3, 1.25993, 1e-5),
    ("proof of thm:bdd: 2^(5 gamma5/2) < 1.42611", 2, 5 * G5 / 2, 1.42611, 1e-5),
    # previous bounds, derived from the widths n/6, n/3, 13n/30 or quoted
    ("prev. Hamiltonian Cycle Delta<=3: (1+sqrt2)^(n/6)", 1 + math.sqrt(2), 1 / 6, 1.1583),
    ("prev. Hamiltonian Cycle Delta<=4: (2+sqrt2)^(n/3)", H, 1 / 3, 1.5058),
    ("prev. TSP Delta<=3: (1+2^(w/2))^(n/6)", T3, 1 / 6, 1.2128),
    ("prev. TSP Delta<=4: (2+2^(w/2))^(n/3)", T, 1 / 3, 1.6110),
    ("prev. TSP Delta<=5: (2+2^(w/2))^(13n/30)", T, 13 / 30, 1.8588),
    ("prev. TSP Delta<=6 (Bjorklund-Husfeldt-Kaski-Koivisto): 114^(n/7)", 114, 1 / 7, 1.9672),
    ("prev. DS / EDS Delta<=3 (Fomin-Hoie): 3^(n/6)", 3, 1 / 6, 1.2010),
    ("prev. Max k-Vertex Cover Delta<=3 (Della Croce-Paschos): 2^(n/6)", 2, 1 / 6, 1.123, 1e-3),
    ("prev. OCT Delta<=4: 3^(n/3)", 3, 1 / 3, 1.4423),
    ("prev. OCT Delta<=5: 3^(13n/30)", 3, 13 / 30, 1.6098),
    ("prev. Longest Path Delta<=4 (BKKZ): 2^(2n/3)", 2, 2 / 3, 1.5875),
    ("prev. k-Path, Hamiltonian Cycle Delta=5 (BKKZ, who print 1.6245): 2^(7n/10)", 2, 7 / 10, 1.6246),
    ("prev. Upper Domination (Bazgan et al., who print 1.348): 6^(n/6)", 6, 1 / 6, 1.3481),
]

fails = []
print("c3 = %.10f, F4 <= %.11f, gamma5 = %.10f, omega <= %.4f" % (C3, F4, G5, OMEGA))
for label, b, e, stated, *tol in CHECKS:
    v = b ** e
    ok = v < stated and stated - v < (tol[0] if tol else 1e-4) + 1e-12
    print("%-62s %.7f < %-7s  margin %.2e  %s" % (label, v, stated, stated - v, "ok" if ok else "FAIL"))
    if not ok:
        fails.append(label)
# comparisons used in the text
cmp = [("Co-Path Packing: DP base below the branching factor 2.8192", 5 ** (5 / 8) < 2.8192),
       ("CDS Delta<=5: 4^(11/32) below Binkele-Raible-Fernau 1.8139", 4 ** (11 / 32) < 1.8139)]
for label, ok in cmp:
    print("%-62s %s" % (label, "ok" if ok else "FAIL"))
    if not ok:
        fails.append(label)
print("ALL CHECKS PASSED" if not fails else "FAILED: %s" % fails)