{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "edgeweight.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# edge weight \u2014 Python demo\n\nNumerical companion to the entry [edge weight](https://dictionaryofml.org/terms/edgeweight.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nNumerical companion to the glossary entry 'edgeweight'. Eight days of 2024 at Krems, every 46th day from 1 January, are the nodes of a graph. Each day is a data point with the feature vector (morning minimum temperature, maximum daytime temperature). The edge weight of a pair of days is the Gaussian similarity exp(-d^2 / (2 sigma^2)) of their feature vectors, with d their Euclidean distance and sigma = 5 degrees Celsius.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/edgeweight.py`](https://dictionaryofml.org/terms/edgeweight.py); CC BY 4.0.\n\nBefore running a downloaded copy, scan it: `uvx bandit -q -t B102,B307,B602,B605 edgeweight.py` (B102,B307,B602,B605 are the exec, eval and shell checks of [bandit](https://bandit.readthedocs.io/)) reports nothing: the script runs no shell command and evaluates no generated code."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# Notebook shim: the script resolves output paths relative to __file__,\n# which a notebook kernel does not define; everything lands in the\n# working directory instead.\nimport os\n__file__ = os.path.join(os.getcwd(), \"edgeweight.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"Edge weights among eight days at Krems an der Donau: the Gaussian\nsimilarity of their feature vectors, the k-nearest-neighbor graph, and the\nweighted sums that graph clustering and convex clustering build from them.\n\nPurpose\n-------\nNumerical companion to the glossary entry 'edgeweight'.  Eight days of\n2024 at Krems, every 46th day from 1 January, are the nodes of a graph.\nEach day is a data point with the feature vector (morning minimum\ntemperature, maximum daytime temperature).  The edge weight of a pair of\ndays is the Gaussian similarity exp(-d^2 / (2 sigma^2)) of their feature\nvectors, with d their Euclidean distance and sigma = 5 degrees Celsius.\n\nThe demo checks the entry's claims: the weight matrix is symmetric with a\nzero diagonal and entries in (0, 1]; the weight falls with the distance\nand is exp(-1/2) at distance sigma; the width sigma decides how many\npairs carry a visible weight; the k-nearest-neighbor graph keeps few of\nthe 28 pairs and stays connected; the Laplacian quadratic form of a node\nsignal is the weighted sum of its squared differences over the edges, and\nfor the indicator of a cluster it is the total weight of the edges that\nleave the cluster; the fusion penalty of convex clustering for a hard\nclustering is the distance between the two centroids times that total\nweight.\n\nDeterministic (no randomness).  Self-contained: numpy + matplotlib only;\nthe GeoSphere download falls back to the committed CSV.\n\nBlocks\n------\n[B-data]      Download the daily minimum and maximum temperature of 2024\n              at Krems (GeoSphere station 3805) or read the committed\n              copy; 366 days, no missing value.\n[B-days]      Every 46th day as a node: eight days, their feature vectors\n              and pairwise Euclidean distances; the nearest and the\n              farthest pair.\n[B-weights]   Gaussian edge weights with sigma = 5: symmetric weight\n              matrix, zero diagonal, entries in (0, 1]; the weight of the\n              nearest and of the farthest pair; how many of the 28 pairs\n              weigh at least 0.5 and how many below 0.01; the same counts\n              for sigma = 1 and sigma = 50.\n[B-knn]       The 2-nearest-neighbor graph: an edge whenever either day is\n              among the two nearest neighbors of the other; its number of\n              edges, its connectivity, the weights it keeps and drops.\n[B-quadform]  The Laplacian quadratic form of a node signal equals the\n              weighted sum of squared differences over the edges; for the\n              indicator of the cold days it is the total weight of the\n              edges between cold and warm days, smaller than for a split\n              by calendar; the convex-clustering penalty of the hard\n              clustering is the centroid distance times that total weight.\n[B-plot]      CSVs for the figure (nodes, edges in three weight classes,\n              the 28 pairs, the Gaussian curve) and the preview.\n\nOutputs\n-------\nedgeweight_weather.csv       : date, tmin, tmax (committed copy).\nedgeweight_nodes.csv         : the eight days: index, date, label, tmin,\n                               tmax, cold (1 for a cold day), and the\n                               anchor of the label in the figure.\nedgeweight_edges_strong.csv  : edges with weight >= 0.5 as NaN-separated\n                               paths (x, y).\nedgeweight_edges_medium.csv  : edges with 0.1 <= weight < 0.5.\nedgeweight_edges_weak.csv    : edges with 0.01 <= weight < 0.1.\nedgeweight_pairs.csv         : the 28 pairs: i, j, distance, weight, knn\n                               (1 if the pair is an edge of the 2-NN graph).\nedgeweight_curve.csv         : distance, weight for the Gaussian curve.\nedgeweight.png               : matplotlib preview (checking only).\n\"\"\"\n\n# /// script\n# requires-python = \">=3.10\"\n# dependencies = [\"matplotlib==3.10.7\", \"numpy==2.3.4\"]\n# ///\n\nimport json\nimport urllib.request\nfrom pathlib import Path\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\n\nOUT_DIR = Path(__file__).parent\n\nreport = []\n\n\ndef check(name, ok):\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-data]** Download the daily minimum and maximum temperature of 2024 at Krems (GeoSphere station 3805) or read the committed copy; 366 days, no missing value."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-data] daily minimum and maximum temperature at Krems, 2024\")\nURL = (\"https://dataset.api.hub.geosphere.at/v1/station/historical/\"\n       \"klima-v2-1d?parameters=tlmin,tlmax&station_ids=3805\"\n       \"&start=2024-01-01&end=2024-12-31\")\nCSV = OUT_DIR / \"edgeweight_weather.csv\"\ntry:\n    with urllib.request.urlopen(URL, timeout=120) as resp:\n        payload = json.load(resp)\n    params = payload[\"features\"][0][\"properties\"][\"parameters\"]\n    records = [(stamp[:10], lo, hi)\n               for stamp, lo, hi in zip(payload[\"timestamps\"],\n                                        params[\"tlmin\"][\"data\"],\n                                        params[\"tlmax\"][\"data\"])]\n    with open(CSV, \"w\") as fh:\n        fh.write(\"date,tmin,tmax\\n\")\n        for day, lo, hi in records:\n            fh.write(f\"{day},{lo},{hi}\\n\")\n    print(f\"    downloaded {len(records)} days\")\nexcept OSError as err:\n    print(f\"    download failed ({err}); reading the committed CSV\")\n    rows = CSV.read_text().strip().splitlines()[1:]\n    records = [(d, float(a), float(b))\n               for d, a, b in (r.split(\",\") for r in rows)]\n\ncheck(\"[B-data] 366 days for 2024\", len(records) == 366)\ncheck(\"[B-data] no day is missing a temperature\",\n      all(lo is not None and hi is not None for _, lo, hi in records))\nX_all = np.array([[lo, hi] for _, lo, hi in records], dtype=float)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-days]** Every 46th day as a node: eight days, their feature vectors and pairwise Euclidean distances; the nearest and the farthest pair."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-days] every 46th day of 2024 as a node\")\nSTEP = 46\nidx = np.arange(0, len(X_all), STEP)\nX = X_all[idx]\ndates = [records[i][0] for i in idx]\nMONTHS = [\"Jan\", \"Feb\", \"Mar\", \"Apr\", \"May\", \"Jun\",\n          \"Jul\", \"Aug\", \"Sep\", \"Oct\", \"Nov\", \"Dec\"]\nlabels = [f\"{int(d[8:10])} {MONTHS[int(d[5:7]) - 1]}\" for d in dates]\nn = len(X)\ncheck(f\"[B-days] {n} nodes: \" + \", \".join(labels), n == 8)\nD = np.sqrt(((X[:, None, :] - X[None, :, :]) ** 2).sum(axis=-1))\niu = np.triu_indices(n, 1)\npairs = list(zip(iu[0], iu[1]))\ncheck(f\"[B-days] {len(pairs)} pairs of days\", len(pairs) == n * (n - 1) // 2)\nnear = min(pairs, key=lambda p: D[p])\nfar = max(pairs, key=lambda p: D[p])\ncheck(f\"[B-days] nearest pair {labels[near[0]]} and {labels[near[1]]} at \"\n      f\"distance {D[near]:.1f}; farthest pair {labels[far[0]]} and \"\n      f\"{labels[far[1]]} at distance {D[far]:.1f}\",\n      D[near] < 2 and D[far] > 25)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-weights]** Gaussian edge weights with sigma = 5: symmetric weight matrix, zero diagonal, entries in (0, 1]; the weight of the nearest and of the farthest pair; how many of the 28 pairs weigh at least 0.5 and how many below 0.01; the same counts for sigma = 1 and sigma = 50."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "def gaussian_weights(D, sigma):\n    \"\"\"Weight matrix of the fully connected graph: Gaussian similarity of\n    the feature vectors, zero on the diagonal (no self-loops).\"\"\"\n    A = np.exp(-D ** 2 / (2 * sigma ** 2))\n    np.fill_diagonal(A, 0.0)\n    return A\n\n\nprint(\"[B-weights] Gaussian edge weights of the eight days\")\nSIGMA = 5.0\nA = gaussian_weights(D, SIGMA)\nw = A[iu]\ncheck(\"[B-weights] the weight matrix is symmetric with a zero diagonal\",\n      np.allclose(A, A.T) and np.all(np.diag(A) == 0))\ncheck(\"[B-weights] every weight lies in (0, 1]\",\n      np.all(w > 0) and np.all(w <= 1))\ncheck(\"[B-weights] the weight falls with the distance: larger distance, \"\n      \"smaller weight, for every two pairs\",\n      np.all(np.diff(w[np.argsort(D[iu])]) <= 1e-15))\ncheck(f\"[B-weights] weight at distance sigma = {SIGMA:.0f}: \"\n      f\"exp(-1/2) = {np.exp(-0.5):.2f}\",\n      abs(np.exp(-D[near] ** 2 / (2 * SIGMA ** 2)) - A[near]) < 1e-12)\ncheck(f\"[B-weights] nearest pair weight {A[near]:.2f}; farthest pair \"\n      f\"weight {A[far]:.1e}\", A[near] > 0.9 and A[far] < 1e-5)\nn_strong, n_weak = int(np.sum(w >= 0.5)), int(np.sum(w < 0.01))\nn_medium = int(np.sum((w >= 0.1) & (w < 0.5)))\nn_faint = int(np.sum((w >= 0.01) & (w < 0.1)))\ncheck(f\"[B-weights] sigma = {SIGMA:.0f}: {n_strong} pairs weigh at least \"\n      f\"0.5, {n_medium} between 0.1 and 0.5, {n_faint} between 0.01 and \"\n      f\"0.1, {n_weak} below 0.01\", n_strong + n_medium + n_faint + n_weak\n      == len(pairs))\nA1, A50 = gaussian_weights(D, 1.0), gaussian_weights(D, 50.0)\ncheck(f\"[B-weights] sigma = 1: {int(np.sum(A1[iu] >= 0.01))} of the \"\n      f\"{len(pairs)} pairs weigh at least 0.01; sigma = 50: the smallest \"\n      f\"weight is {A50[iu].min():.2f}\",\n      np.sum(A1[iu] >= 0.01) <= 2 and A50[iu].min() > 0.85)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-knn]** The 2-nearest-neighbor graph: an edge whenever either day is among the two nearest neighbors of the other; its number of edges, its connectivity, the weights it keeps and drops."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-knn] the 2-nearest-neighbor graph\")\nK = 2\nnearest = np.argsort(D + np.eye(n) * 1e9, axis=1)[:, :K]\nE_knn = np.zeros((n, n), dtype=bool)\nfor i in range(n):\n    for j in nearest[i]:\n        E_knn[i, j] = E_knn[j, i] = True\nA_knn = np.where(E_knn, A, 0.0)\nknn_pairs = [p for p in pairs if E_knn[p]]\ncheck(f\"[B-knn] {len(knn_pairs)} of the {len(pairs)} pairs are edges of \"\n      f\"the {K}-NN graph\", 0 < len(knn_pairs) < len(pairs))\ncheck(\"[B-knn] the sparsified weight matrix stays symmetric\",\n      np.allclose(A_knn, A_knn.T))\nreach = {0}\nfrontier = [0]\nwhile frontier:\n    i = frontier.pop()\n    for j in np.flatnonzero(E_knn[i]):\n        if j not in reach:\n            reach.add(j)\n            frontier.append(j)\ncheck(f\"[B-knn] the {K}-NN graph is connected\", len(reach) == n)\nkept = np.array([A[p] for p in knn_pairs])\ndropped_pairs = [p for p in pairs if not E_knn[p]]\nheavy = max(dropped_pairs, key=lambda p: A[p])\nlight = min(knn_pairs, key=lambda p: A[p])\ncheck(f\"[B-knn] kept weights range from {kept.min():.2f} ({labels[light[0]]}\"\n      f\" and {labels[light[1]]}) to {kept.max():.2f}; the heaviest dropped \"\n      f\"pair, {labels[heavy[0]]} and {labels[heavy[1]]}, weighs \"\n      f\"{A[heavy]:.2f}: the {K}-NN graph is not a threshold on the weights\",\n      A[heavy] > kept.min())\ncheck(f\"[B-knn] both days of the dropped pair have {K} closer neighbors \"\n      f\"than each other\",\n      all(np.sum(D[i] < D[heavy]) >= K + 1 for i in heavy))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-quadform]** The Laplacian quadratic form of a node signal equals the weighted sum of squared differences over the edges; for the indicator of the cold days it is the total weight of the edges between cold and warm days, smaller than for a split by calendar; the convex-clustering penalty of the hard clustering is the centroid distance times that total weight."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-quadform] the Laplacian quadratic form and the fusion penalty\")\nL = np.diag(A.sum(axis=1)) - A\n\n\ndef quad_form(A, u):\n    return float(u @ (np.diag(A.sum(axis=1)) - A) @ u)\n\n\ndef edge_sum(A, u):\n    return float(sum(A[i, j] * (u[i] - u[j]) ** 2 for i, j in pairs))\n\n\nrng_signal = X[:, 1] - X[:, 1].mean()        # a node signal: centered tmax\ncheck(\"[B-quadform] u^T L u equals the weighted sum over the edges of \"\n      \"(u_i - u_i')^2, for the maximum temperatures as node signal\",\n      abs(quad_form(A, rng_signal) - edge_sum(A, rng_signal)) < 1e-9)\ncold = (X[:, 1] < 20).astype(float)          # cold day: maximum below 20\nn_cold = int(cold.sum())\ncut_cold = float(sum(A[i, j] for i, j in pairs if cold[i] != cold[j]))\ncheck(f\"[B-quadform] indicator of the {n_cold} cold days (maximum below \"\n      f\"20 degrees): u^T L u = {quad_form(A, cold):.2f} equals the total \"\n      f\"weight {cut_cold:.2f} of the edges between cold and warm days\",\n      abs(quad_form(A, cold) - cut_cold) < 1e-9)\ncalendar = (np.arange(n) < n // 2).astype(float)\ncut_cal = float(sum(A[i, j] for i, j in pairs if calendar[i] != calendar[j]))\ncheck(f\"[B-quadform] a split into the first four and the last four days \"\n      f\"cuts total weight {cut_cal:.2f}, more than the cold/warm split\",\n      cut_cal > cut_cold)\nc_cold, c_warm = X[cold == 1].mean(axis=0), X[cold == 0].mean(axis=0)\nW_hard = np.where(cold[:, None] == 1, c_cold, c_warm)\npenalty = float(sum(A[i, j] * np.linalg.norm(W_hard[i] - W_hard[j])\n                    for i, j in pairs))\ndist_c = float(np.linalg.norm(c_cold - c_warm))\ncheck(f\"[B-quadform] convex-clustering penalty of the hard clustering: \"\n      f\"{penalty:.1f} = centroid distance {dist_c:.1f} times the total \"\n      f\"weight {cut_cold:.2f}\", abs(penalty - dist_c * cut_cold) < 1e-9)\ncheck(f\"[B-quadform] total weight of all {len(pairs)} pairs: {w.sum():.2f}; \"\n      f\"the cold/warm split cuts {100 * cut_cold / w.sum():.0f} percent of \"\n      f\"it, the calendar split {100 * cut_cal / w.sum():.0f} percent\",\n      cut_cold < w.sum() / 2 < cut_cal)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-plot]** CSVs for the figure (nodes, edges in three weight classes, the 28 pairs, the Gaussian curve) and the preview."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-plot] nodes, edges by weight class, pairs, Gaussian curve\")\n# where the pgfplots label of a node sits (anchor of the label relative\n# to the point), chosen so that no two labels overlap\nANCHOR = {\"1 Jan\": \"north west\", \"18 Nov\": \"west\", \"16 Feb\": \"south west\",\n          \"3 Oct\": \"north\", \"2 Apr\": \"north west\", \"18 May\": \"south east\",\n          \"3 Jul\": \"south\", \"18 Aug\": \"south\"}\nwith open(OUT_DIR / \"edgeweight_nodes.csv\", \"w\") as fh:\n    fh.write(\"node,date,label,tmin,tmax,cold,anchor\\n\")\n    for i in range(n):\n        fh.write(f\"{i + 1},{dates[i]},{labels[i]},{X[i, 0]:.1f},\"\n                 f\"{X[i, 1]:.1f},{int(cold[i])},{ANCHOR[labels[i]]}\\n\")\nCLASSES = {\"strong\": (0.5, 1.01), \"medium\": (0.1, 0.5), \"weak\": (0.01, 0.1)}\nn_drawn = 0\nfor name, (lo, hi) in CLASSES.items():\n    with open(OUT_DIR / f\"edgeweight_edges_{name}.csv\", \"w\") as fh:\n        fh.write(\"x,y\\n\")                 # NaN rows break the path between edges\n        for i, j in pairs:\n            if lo <= A[i, j] < hi:\n                fh.write(f\"{X[i, 0]:.1f},{X[i, 1]:.1f}\\n\"\n                         f\"{X[j, 0]:.1f},{X[j, 1]:.1f}\\nnan,nan\\n\")\n                n_drawn += 1\ncheck(f\"[B-plot] {n_drawn} of the {len(pairs)} pairs are drawn as edges \"\n      f\"(weight at least 0.01)\", n_drawn == len(pairs) - n_weak)\nwith open(OUT_DIR / \"edgeweight_pairs.csv\", \"w\") as fh:\n    fh.write(\"i,j,distance,weight,knn\\n\")\n    for i, j in pairs:\n        fh.write(f\"{i + 1},{j + 1},{D[i, j]:.4f},{A[i, j]:.6f},\"\n                 f\"{int(E_knn[i, j])}\\n\")\ngrid = np.linspace(0, 28, 141)\nwith open(OUT_DIR / \"edgeweight_curve.csv\", \"w\") as fh:\n    fh.write(\"distance,weight\\n\")\n    for d in grid:\n        fh.write(f\"{d:.2f},{np.exp(-d ** 2 / (2 * SIGMA ** 2)):.6f}\\n\")\n\nfig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.6, 4.0))\nSTYLE = {\"strong\": dict(lw=2.4, ls=\"-\", color=\"black\"),\n         \"medium\": dict(lw=0.9, ls=\"-\", color=\"0.35\"),\n         \"weak\": dict(lw=0.8, ls=\":\", color=\"0.5\")}\nfor name, (lo, hi) in CLASSES.items():\n    first = True\n    for i, j in pairs:\n        if lo <= A[i, j] < hi:\n            ax1.plot([X[i, 0], X[j, 0]], [X[i, 1], X[j, 1]], **STYLE[name],\n                     label=f\"weight in [{lo:.2g}, {hi if hi < 1 else 1:.2g}]\"\n                     if first else None)\n            first = False\nax1.scatter(X[:, 0], X[:, 1], marker=\"o\", color=\"black\", s=28, zorder=3,\n            label=\"the eight days (nodes)\")\nfor i in range(n):\n    ax1.annotate(labels[i], (X[i, 0], X[i, 1]), textcoords=\"offset points\",\n                 xytext=(4, 4), fontsize=8)\nax1.set_xlabel(\"morning minimum temperature (\u00b0C)\")\nax1.set_ylabel(\"maximum daytime temperature (\u00b0C)\")\nax1.set_title(\"Gaussian edge weights (sigma = 5 \u00b0C) among eight days\")\nax1.legend(frameon=False, fontsize=8, loc=\"upper left\")\nax2.plot(grid, np.exp(-grid ** 2 / (2 * SIGMA ** 2)), \"k-\", lw=1.2,\n         label=\"exp(-d^2 / (2 sigma^2))\")\nknn_mask = np.array([E_knn[p] for p in pairs])\nax2.scatter(D[iu][knn_mask], w[knn_mask], marker=\"o\", color=\"black\", s=30,\n            label=\"pair kept in the 2-NN graph\")\nax2.scatter(D[iu][~knn_mask], w[~knn_mask], marker=\"s\", facecolors=\"none\",\n            edgecolors=\"black\", s=30, label=\"pair dropped by the 2-NN graph\")\nax2.set_xlabel(\"Euclidean distance d between the feature vectors (\u00b0C)\")\nax2.set_ylabel(\"edge weight\")\nax2.set_title(\"the 28 pairs on the Gaussian curve\")\nax2.legend(frameon=False, fontsize=8)\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"edgeweight.png\", dpi=110)\n\nn_ok = sum(ok for _, ok in report)\nprint(f\"\\n{n_ok}/{len(report)} checks pass\")\nif n_ok != len(report):\n    raise SystemExit(1)"
  }
 ]
}