"""The Laplacian matrix of a weighted graph of twelve weather stations
around Krems an der Donau: the quadratic form, the zero eigenvalue, the
normalized variants, and Laplacian regularization.

Purpose
-------
Numerical companion to the glossary entry 'LapMat'.  Twelve GeoSphere
weather stations within 45 km of Krems are the nodes of a weighted
graph: two stations are connected by an edge if they are at most 35 km
apart, and the edge weight exp(-d^2 / (2 * 20^2)) decays with the
distance d in km.  The mean temperature of 2024 at a station is a number
attached to its node.  The demo builds the Laplacian matrix L = D - A
from the degree matrix D and the adjacency matrix A and checks the
entry's claims: the quadratic form x^T L x equals the sum over the edges
of the weighted squared differences; L is positive semi-definite with
the eigenvalue 0 and the constant eigenvector; the multiplicity of the
eigenvalue 0 equals the number of connected components, which the demo
varies by shrinking the radius; the normalized Laplacian matrices have
eigenvalues in [0, 2]; the Fiedler vector splits the stations by its
signs; and Laplacian regularization predicts the mean temperature of a
station without a record as the weighted average of its neighbors.

Deterministic (the only random draws are test vectors from a fixed
seed) and self-contained: numpy + matplotlib only; the GeoSphere
download falls back to the committed CSV.

Blocks
------
[B-data]        Download the daily mean temperature of 2024 at the twelve
                stations (GeoSphere, klima-v2-1d, parameter tl_mittel) or
                read the committed copy; the mean temperature of the year
                per station; station positions in km east and north of
                Krems.
[B-graph]       Edges between stations at most 35 km apart with Gaussian
                weights; adjacency matrix A, degree matrix D, Laplacian
                matrix L = D - A: diagonal entries are the degrees, the
                off-diagonal entries the negated edge weights, every row
                sums to zero.
[B-quadform]    x^T L x equals the sum over the edges of
                A_ij (x_i - x_j)^2, for the temperature vector and for
                50 test vectors with entries drawn from a fixed seed; it
                is zero for a constant vector.
[B-eigenvalues] Eigenvalues of L are nonnegative, the smallest is 0 with
                the constant eigenvector; the graph is connected and the
                second-smallest eigenvalue is positive.  Shrinking the
                radius to 25 km and 20 km disconnects the graph into 2
                and 6 components, and the eigenvalue 0 then has
                multiplicity 2 and 6.
[B-normalized]  The normalized Laplacian matrices L_sym and L_rw: same
                eigenvalues, all in [0, 2], eigenvalue 0 with eigenvector
                D^(1/2) 1 and 1, respectively.
[B-fiedler]     The signs of the Fiedler vector split the three stations
                more than 20 km east of Krems from the other nine.
[B-regularize]  Laplacian regularization: leaving one station out, the
                minimizer of the quadratic form with the other eleven
                values fixed is the weighted average of its neighbors;
                error of this prediction against the recorded mean, the
                mean of the other stations as the baseline.
[B-plot]        CSVs for the figure (nodes, edges, eigenvalues) and the
                matplotlib preview.

Outputs
-------
LapMat_weather.csv  : date and the daily mean temperature of the twelve
                      stations (committed copy of the download).
LapMat_nodes.csv    : station name, position in km east and north of
                      Krems, altitude, mean temperature, Fiedler-vector
                      entry and its sign, label anchor for the figure.
LapMat_edges.csv    : one row per edge: start point, displacement, edge
                      weight (for a pgfplots quiver).
LapMat_eigenvalues.csv : index i and the i-th smallest eigenvalue of L
                      for the radii 35 km, 25 km, and 20 km.
LapMat.png          : matplotlib preview (checking only).
"""

# /// script
# requires-python = ">=3.10"
# dependencies = ["matplotlib==3.10.7", "numpy==2.3.4"]
# ///

import json
import math
import urllib.request
from pathlib import Path

import numpy as np
import matplotlib

matplotlib.use("Agg")
import matplotlib.pyplot as plt

OUT_DIR = Path(__file__).parent

report = []


def check(name, ok):
    report.append((name, bool(ok)))
    print(f"  [{'ok' if ok else 'FAIL'}] {name}")


# ---- [B-data] mean temperature of 2024 at twelve stations around Krems
print("[B-data] daily mean temperature of 2024 at twelve stations")
# GeoSphere station id, name, latitude, longitude, altitude in m (from the
# klima-v2-1d station metadata); the short name labels the figure, and the
# last field is the TikZ anchor of that label (south: label above the node,
# north: below, east: to the left)
STATIONS = [
    (3805, "Krems", 48.41861, 15.62222, 202.0, "Krems", "north"),
    (3811, "Langenlois", 48.4725, 15.69722, 207.0, "Langenlois", "east"),
    (2116, "Gars am Kamp", 48.59194, 15.7, 273.0, "Gars", "east"),
    (3702, "Jauerling Gipfel", 48.33447, 15.33911, 955.0, "Jauerling",
     "south"),
    (5609, "St. Pölten Landhaus", 48.19972, 15.63111, 273.6, "St. Pölten",
     "south"),
    (2117, "Horn Wasserwerk", 48.674999, 15.643888, 308.0, "Horn", "north"),
    (5413, "Melk", 48.20972, 15.33139, 307.0, "Melk", "south"),
    (1906, "Allentsteig", 48.69083, 15.36694, 598.8, "Allentsteig",
     "north"),
    (1920, "Stift Zwettl", 48.61778, 15.20361, 502.4, "Zwettl", "south"),
    (4081, "Langenlebarn", 48.32389, 16.11806, 175.3, "Langenlebarn",
     "south"),
    (2207, "Schöngrabern", 48.60333, 16.06167, 253.0, "Schöngrabern",
     "north"),
    (905, "Retz", 48.76111, 15.94167, 320.0, "Retz", "north"),
]
IDS = [s[0] for s in STATIONS]
NAMES = [s[5] for s in STATIONS]
n = len(STATIONS)
URL = ("https://dataset.api.hub.geosphere.at/v1/station/historical/"
       "klima-v2-1d?parameters=tl_mittel&station_ids="
       + ",".join(str(i) for i in IDS) + "&start=2024-01-01&end=2024-12-31")
CSV = OUT_DIR / "LapMat_weather.csv"
try:
    with urllib.request.urlopen(URL, timeout=120) as resp:
        payload = json.load(resp)
    dates = [stamp[:10] for stamp in payload["timestamps"]]
    by_id = {int(f["properties"]["station"]):
             f["properties"]["parameters"]["tl_mittel"]["data"]
             for f in payload["features"]}
    columns = [by_id[i] for i in IDS]
    with open(CSV, "w") as fh:
        fh.write("date," + ",".join(f"s{i}" for i in IDS) + "\n")
        for r, day in enumerate(dates):
            fh.write(day + "," + ",".join(f"{col[r]}" for col in columns)
                     + "\n")
    print(f"    downloaded {len(dates)} days for {len(columns)} stations")
except OSError as err:
    print(f"    download failed ({err}); reading the committed CSV")
    rows = CSV.read_text().strip().splitlines()[1:]
    dates = [r.split(",")[0] for r in rows]
    table = np.array([[float(v) for v in r.split(",")[1:]] for r in rows])
    columns = [table[:, j].tolist() for j in range(n)]

T = np.array(columns, dtype=float)             # stations x days
check("[B-data] 366 days for 2024", T.shape == (n, 366))
check("[B-data] no station is missing a day", not np.isnan(T).any())
x = T.mean(axis=1)                             # mean temperature per station
check("[B-data] mean temperature of 2024: "
      + ", ".join(f"{nm} {v:.1f}" for nm, v in zip(NAMES, x)),
      np.all((x > 8) & (x < 15)))
# positions in km east and north of Krems (plane approximation)
lat0, lon0 = STATIONS[0][2], STATIONS[0][3]
east = np.array([(s[3] - lon0) * 111.32 * math.cos(math.radians(lat0))
                 for s in STATIONS])
north = np.array([(s[2] - lat0) * 110.57 for s in STATIONS])
altitude = np.array([s[4] for s in STATIONS])
dist = np.sqrt((east[:, None] - east[None, :]) ** 2
               + (north[:, None] - north[None, :]) ** 2)
check(f"[B-data] every station is within {dist[0].max():.0f} km of Krems",
      dist[0].max() < 46)


# ---- [B-graph] the weighted graph and its Laplacian matrix
print("[B-graph] edges within 35 km, Gaussian weights, L = D - A")
SIGMA = 20.0                                   # km


def laplacian(radius):
    """Adjacency matrix, degrees, and Laplacian matrix of the graph that
    connects stations at most `radius` km apart."""
    A = np.exp(-dist ** 2 / (2 * SIGMA ** 2)) * (dist <= radius)
    np.fill_diagonal(A, 0.0)
    d = A.sum(axis=1)
    return A, d, np.diag(d) - A


RADIUS = 35.0
A, deg, L = laplacian(RADIUS)
n_edges = int(np.count_nonzero(np.triu(A)))
check(f"[B-graph] {n} nodes and {n_edges} edges", n_edges == 27)
check("[B-graph] A is symmetric with zero diagonal and weights in (0, 1)",
      np.allclose(A, A.T) and np.all(np.diag(A) == 0)
      and np.all((A[A > 0] > 0) & (A[A > 0] < 1)))
check(f"[B-graph] edge weights between {A[A > 0].min():.2f} and "
      f"{A[A > 0].max():.2f}; the Krems-Langenlois edge (8 km) weighs "
      f"{A[0, 1]:.2f}", abs(A[0, 1] - math.exp(-dist[0, 1] ** 2 / 800)) < 1e-12)
check("[B-graph] diagonal of L = degrees, off-diagonal of L = -A",
      np.allclose(np.diag(L), deg) and np.allclose(L - np.diag(deg), -A))
check("[B-graph] every row of L sums to zero", np.allclose(L.sum(axis=1), 0))
check(f"[B-graph] Krems has degree {deg[0]:.2f}, the weighted number of "
      f"its {int(np.count_nonzero(A[0]))} neighbors", abs(deg[0] - A[0].sum()) < 1e-12)


# ---- [B-quadform] x^T L x is the sum of weighted squared differences
print("[B-quadform] the quadratic form of L")


def edge_sum(A, v):
    """Sum over the edges {i, j} of A_ij (v_i - v_j)^2."""
    iu, ju = np.triu_indices(len(v), k=1)
    return float(np.sum(A[iu, ju] * (v[iu] - v[ju]) ** 2))


qf = float(x @ L @ x)
check(f"[B-quadform] temperature vector: x^T L x = {qf:.2f} equals the "
      f"edge sum {edge_sum(A, x):.2f} (squared degrees Celsius)",
      abs(qf - edge_sum(A, x)) < 1e-9)
rng = np.random.default_rng(2024)
R = rng.standard_normal((50, n))
check("[B-quadform] identity holds for 50 test vectors with entries drawn "
      "from a fixed seed, all values >= 0",
      all(abs(r @ L @ r - edge_sum(A, r)) < 1e-9 and r @ L @ r >= 0
          for r in R))
ones = np.ones(n)
check("[B-quadform] constant vector: x^T L x = 0 and L 1 = 0",
      abs(ones @ L @ ones) < 1e-12 and np.allclose(L @ ones, 0))
# the largest single term of the edge sum
iu, ju = np.triu_indices(n, k=1)
terms = A[iu, ju] * (x[iu] - x[ju]) ** 2
k = int(np.argmax(terms))
check(f"[B-quadform] largest term: edge {NAMES[iu[k]]}-{NAMES[ju[k]]}, "
      f"weight {A[iu[k], ju[k]]:.2f}, difference {abs(x[iu[k]] - x[ju[k]]):.1f} "
      f"degrees, term {terms[k]:.2f}", terms[k] > 0)


# ---- [B-eigenvalues] eigenvalues: nonnegative, zero with multiplicity =
#      number of connected components
print("[B-eigenvalues] eigenvalues of L and connected components")


def components(A):
    """Number of connected components and a label per node (depth-first
    search over the positive entries of A)."""
    label = -np.ones(len(A), dtype=int)
    c = 0
    for s in range(len(A)):
        if label[s] >= 0:
            continue
        stack = [s]
        label[s] = c
        while stack:
            u = stack.pop()
            for v in np.flatnonzero(A[u] > 0):
                if label[v] < 0:
                    label[v] = c
                    stack.append(v)
        c += 1
    return c, label


TOL = 1e-9
lam, V = np.linalg.eigh(L)
check(f"[B-eigenvalues] all {n} eigenvalues are >= 0 (smallest {lam[0]:.1e}, "
      f"largest {lam[-1]:.2f})", np.all(lam > -TOL))
check("[B-eigenvalues] eigenvalue 0 with the constant vector as eigenvector",
      abs(lam[0]) < TOL and np.allclose(np.abs(V[:, 0]), 1 / math.sqrt(n)))
n_comp, _ = components(A)
check(f"[B-eigenvalues] radius 35 km: connected ({n_comp} component), "
      f"second-smallest eigenvalue {lam[1]:.2f} > 0",
      n_comp == 1 and lam[1] > 1e-6)
eigvals = {RADIUS: lam}
for radius, expected in ((25.0, 2), (20.0, 6)):
    A_r, _, L_r = laplacian(radius)
    lam_r, V_r = np.linalg.eigh(L_r)
    eigvals[radius] = lam_r
    n_comp_r, label_r = components(A_r)
    mult = int(np.sum(np.abs(lam_r) < TOL))
    check(f"[B-eigenvalues] radius {radius:.0f} km: {n_comp_r} components, "
          f"eigenvalue 0 with multiplicity {mult}",
          n_comp_r == expected == mult)
    # the indicator vectors of the components span the eigenspace of 0
    indicators = np.array([(label_r == c).astype(float)
                           for c in range(n_comp_r)])
    check(f"[B-eigenvalues] radius {radius:.0f} km: the indicator vector of "
          f"each component satisfies L x = 0",
          all(np.allclose(L_r @ ind, 0) for ind in indicators))
    if radius == 25.0:
        alone = [NAMES[i] for i in range(n) if np.count_nonzero(A_r[i]) == 0]
        check(f"[B-eigenvalues] radius 25 km: the isolated station is "
              f"{', '.join(alone)}", alone == ["Langenlebarn"])


# ---- [B-normalized] the normalized Laplacian matrices
print("[B-normalized] L_sym and L_rw")
D_isqrt = np.diag(1 / np.sqrt(deg))
L_sym = D_isqrt @ L @ D_isqrt
L_rw = np.diag(1 / deg) @ L
lam_sym = np.linalg.eigvalsh(L_sym)
lam_rw = np.sort(np.linalg.eigvals(L_rw).real)
check(f"[B-normalized] eigenvalues of L_sym lie in [0, 2]: smallest "
      f"{lam_sym[0]:.1e}, largest {lam_sym[-1]:.2f}",
      lam_sym[0] > -TOL and lam_sym[-1] <= 2 + TOL)
check("[B-normalized] L_rw has the same eigenvalues as L_sym",
      np.allclose(lam_sym, lam_rw))
check("[B-normalized] L_sym D^(1/2) 1 = 0 and L_rw 1 = 0",
      np.allclose(L_sym @ np.sqrt(deg), 0) and np.allclose(L_rw @ ones, 0))
check("[B-normalized] L_sym = I - D^(-1/2) A D^(-1/2) and "
      "L_rw = I - D^(-1) A",
      np.allclose(L_sym, np.eye(n) - D_isqrt @ A @ D_isqrt)
      and np.allclose(L_rw, np.eye(n) - np.diag(1 / deg) @ A))
check("[B-normalized] x^T L_sym x equals the edge sum of "
      "A_ij (x_i / sqrt(d_i) - x_j / sqrt(d_j))^2",
      all(abs(r @ L_sym @ r - edge_sum(A, r / np.sqrt(deg))) < 1e-9
          for r in R))


# ---- [B-fiedler] the Fiedler vector splits the stations
print("[B-fiedler] signs of the Fiedler vector (radius 35 km)")
fiedler = V[:, 1]
if fiedler[0] < 0:
    fiedler = -fiedler                         # sign convention: Krems positive
check("[B-fiedler] the entries of the Fiedler vector sum to zero",
      abs(fiedler @ ones) < 1e-9)
side = (fiedler >= 0).astype(int)               # 1: with Krems, 0: the rest
far_east = [NAMES[i] for i in range(n) if east[i] > 20]
negative = [NAMES[i] for i in range(n) if side[i] == 0]
check(f"[B-fiedler] negative entries: {', '.join(negative)}; these are the "
      f"stations more than 20 km east of Krems", sorted(negative) == sorted(far_east))
check("[B-fiedler] entries: "
      + ", ".join(f"{nm} {v:+.2f}" for nm, v in zip(NAMES, fiedler)),
      len(negative) == 3)


# ---- [B-regularize] Laplacian regularization: predict a missing station
print("[B-regularize] leave one station out, predict by its neighbors")
pred = np.array([A[i] @ x / deg[i] for i in range(n)])
# the weighted average minimizes the quadratic form over x_i alone
i0 = 0
grid = pred[i0] + np.linspace(-2, 2, 401)


def qf_with(i, value):
    v = x.copy()
    v[i] = value
    return v @ L @ v


check("[B-regularize] for Krems, the weighted average of its neighbors "
      "minimizes x^T L x over the Krems entry (grid of 401 values)",
      all(qf_with(i0, g) >= qf_with(i0, pred[i0]) - 1e-9 for g in grid))
check("[B-regularize] for every station, the entry of L x at that station "
      "is 0 once its value is the weighted average of its neighbors",
      all(abs((L @ np.where(np.arange(n) == i, pred[i], x))[i]) < 1e-9
          for i in range(n)))
err = pred - x
baseline = np.array([np.delete(x, i).mean() - x[i] for i in range(n)])
mae, mae_base = np.mean(np.abs(err)), np.mean(np.abs(baseline))
check(f"[B-regularize] mean absolute error {mae:.2f} degrees, against "
      f"{mae_base:.2f} for the mean of the other eleven stations",
      mae < mae_base)
worst = int(np.argmax(np.abs(err)))
check(f"[B-regularize] largest error at {NAMES[worst]} ({altitude[worst]:.0f} m): "
      f"predicted {pred[worst]:.1f}, recorded {x[worst]:.1f}, error "
      f"{err[worst]:+.1f} degrees", NAMES[worst] == "Jauerling")
rest = np.delete(np.abs(err), worst)
check(f"[B-regularize] without {NAMES[worst]} the mean absolute error is "
      f"{rest.mean():.2f} degrees; Krems: predicted {pred[0]:.1f}, recorded "
      f"{x[0]:.1f}", rest.mean() < 1)
# the penalized problem (average squared error over the eleven labeled
# stations plus alpha times the quadratic form) with a small penalty weight
# alpha tends to the same value; its minimizer solves a linear system
alpha = 1e-5
mask = np.ones(n)
mask[i0] = 0.0
n_lab = int(mask.sum())
x_alpha = np.linalg.solve(np.diag(mask) / n_lab + alpha * L, mask * x / n_lab)
check(f"[B-regularize] penalized problem with alpha = {alpha:g}: the Krems "
      f"entry {x_alpha[i0]:.3f} is within 0.001 of the weighted average "
      f"{pred[i0]:.3f}", abs(x_alpha[i0] - pred[i0]) < 1e-3)


# ---- [B-plot] CSVs and preview
print("[B-plot] nodes, edges, eigenvalues, preview")
with open(OUT_DIR / "LapMat_nodes.csv", "w") as fh:
    fh.write("name,east,north,altitude,temp,fiedler,side,anchor\n")
    for i, s in enumerate(STATIONS):
        fh.write(f"{NAMES[i]},{east[i]:.2f},{north[i]:.2f},{altitude[i]:.0f},"
                 f"{x[i]:.2f},{fiedler[i]:.3f},{side[i]},{s[6]}\n")
with open(OUT_DIR / "LapMat_edges.csv", "w") as fh:
    fh.write("x,y,u,v,w\n")
    for i, j in zip(iu, ju):
        if A[i, j] > 0:
            fh.write(f"{east[i]:.2f},{north[i]:.2f},{east[j] - east[i]:.2f},"
                     f"{north[j] - north[i]:.2f},{A[i, j]:.3f}\n")
with open(OUT_DIR / "LapMat_eigenvalues.csv", "w") as fh:
    fh.write("i,lam35,lam25,lam20\n")
    for i in range(n):
        fh.write(f"{i + 1},{max(eigvals[35.0][i], 0):.4f},"
                 f"{max(eigvals[25.0][i], 0):.4f},"
                 f"{max(eigvals[20.0][i], 0):.4f}\n")
check(f"[B-plot] {n} nodes, {n_edges} edges, {n} eigenvalues per radius "
      "written", True)

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.6, 4.2))
for i, j in zip(iu, ju):
    if A[i, j] > 0:
        ax1.plot([east[i], east[j]], [north[i], north[j]], color="0.55",
                 lw=1.8 if A[i, j] >= 0.5 else 0.6, zorder=1)
for s_val, mk, lab in ((1, "o", "Fiedler entry >= 0 (circles)"),
                       (0, "s", "Fiedler entry < 0 (squares)")):
    sel = side == s_val
    ax1.scatter(east[sel], north[sel], marker=mk, color="black", s=34,
                zorder=2, label=lab)
for i in range(n):
    anc = STATIONS[i][6]
    dy = {"south": 2.2, "north": -3.6, "east": 0.0}[anc]
    dx = -2.5 if anc == "east" else 0.0
    ax1.annotate(NAMES[i], (east[i] + dx, north[i] + dy), fontsize=7,
                 ha="right" if anc == "east" else "center")
ax1.set_xlabel("km east of Krems")
ax1.set_ylabel("km north of Krems")
ax1.set_title("stations within 35 km joined (thick: weight >= 0.5)")
ax1.set_xlim(-38, 50)
ax1.set_ylim(-32, 44)
ax1.set_aspect("equal")
ax1.legend(frameon=False, fontsize=8, loc="upper center",
           bbox_to_anchor=(0.5, -0.16), ncol=2)
idx = np.arange(1, n + 1)
for radius, mk, lab in ((35.0, "o", "radius 35 km (circles)"),
                        (25.0, "s", "radius 25 km (squares)"),
                        (20.0, "^", "radius 20 km (triangles)")):
    ax2.plot(idx, np.maximum(eigvals[radius], 0), mk, color="black",
             mfc="none" if radius != 35.0 else "black", ms=6, label=lab)
ax2.set_xlabel("index i of the eigenvalue")
ax2.set_ylabel("i-th smallest eigenvalue of L")
ax2.set_title("zero eigenvalues = connected components")
ax2.set_xticks(idx)
ax2.legend(frameon=False, fontsize=8, loc="upper left")
fig.tight_layout()
fig.savefig(OUT_DIR / "LapMat.png", dpi=110)

n_ok = sum(ok for _, ok in report)
print(f"\n{n_ok}/{len(report)} checks pass")
if n_ok != len(report):
    raise SystemExit(1)
