{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "weightedgraph.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# weighted graph \u2014 Python demo\n\nNumerical companion to the entry [weighted graph](https://dictionaryofml.org/terms/weightedgraph.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 'weightedgraph'. Ten days of 2024 at Krems (every 37th day) are the nodes of a graph; the feature vector of a day holds its morning minimum and its maximum daytime temperature. Two days are joined by an edge when one is among the three nearest neighbors of the other in the feature plane, and the edge carries a Gaussian weight that falls off with the Euclidean distance between the two days. The demo builds this similarity graph, its weight matrix, and the weighted node degrees, and checks the properties the entry states: the weight matrix is symmetric with a zero diagonal and nonnegative entries, the edge set is the set of positive entries, a row sum is a weighted node degree, and the unweighted graph is the special case with entries 0 and 1. The same construction on all 366 days shows what graph clustering uses: the edges between the cold and the warm days carry a small share of the total weight.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/weightedgraph.py`](https://dictionaryofml.org/terms/weightedgraph.py); CC BY 4.0.\n\nBefore running a downloaded copy, scan it: `uvx bandit -q -t B102,B307,B602,B605 weightedgraph.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(), \"weightedgraph.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"A weighted graph on days of one year at Krems an der Donau: nodes,\nundirected edges, nonnegative edge weights and the weight matrix.\n\nPurpose\n-------\nNumerical companion to the glossary entry 'weightedgraph'.  Ten days of\n2024 at Krems (every 37th day) are the nodes of a graph; the feature\nvector of a day holds its morning minimum and its maximum daytime\ntemperature.  Two days are joined by an edge when one is among the\nthree nearest neighbors of the other in the feature plane, and the\nedge carries a Gaussian weight that falls off with the Euclidean\ndistance between the two days.  The demo builds this similarity graph,\nits weight matrix, and the weighted node degrees, and checks the\nproperties the entry states: the weight matrix is symmetric with a zero\ndiagonal and nonnegative entries, the edge set is the set of positive\nentries, a row sum is a weighted node degree, and the unweighted graph\nis the special case with entries 0 and 1.  The same construction on\nall 366 days shows what graph clustering uses: the edges between the\ncold and the warm days carry a small share of the total weight.\n\nDeterministic: no randomness anywhere.  Self-contained: numpy +\nmatplotlib only; the GeoSphere download falls back to the committed\nCSV.\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 37th day of the year gives the ten nodes, numbered\n             1 to 10 in order of date.\n[B-weights]  Gaussian weights for all 45 pairs of days, with the width\n             set to the mean distance of a day to its third nearest\n             neighbor; the 3-nearest-neighbor graph keeps an edge when\n             one day is among the three nearest of the other.  Weight\n             matrix: symmetric, zero diagonal, nonnegative; edges =\n             positive entries; row sums = weighted degrees; the\n             unweighted graph has entries 0 and 1.\n[B-cut]      The cold days (maximum temperature below 18 degrees) and\n             the warm days: the edges between the two sets carry a\n             smaller share of the weight than of the edges.\n[B-year]     The 10-nearest-neighbor graph on all 366 days: number of\n             edges, weighted degrees, and the share of the total weight\n             that joins a cold day with a warm day; no edge joins a\n             January or February day with a July or August day.\n[B-plot]     CSVs for the figure (nodes, edges in two weight classes,\n             the weight matrix) and the matplotlib preview.\n\nOutputs\n-------\nweightedgraph_weather.csv      : date, tmin, tmax (committed copy).\nweightedgraph_nodes.csv        : node, date, tmin, tmax of the ten days.\nweightedgraph_pairs.csv        : every pair of nodes with its distance,\n                                 its Gaussian weight and its weight in\n                                 the 3-nearest-neighbor graph.\nweightedgraph_edges_strong.csv : edges of weight at least 0.5 as\n                                 nan-separated segments (x, y).\nweightedgraph_edges_weak.csv   : edges of weight below 0.5, same form.\nweightedgraph_matrix.csv       : i, ip, w; the 10 x 10 weight matrix of\n                                 the 3-nearest-neighbor graph, row-wise.\nweightedgraph.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 / \"weightedgraph_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)\ndates_all = [d for d, _, _ in records]\nm_all = len(X_all)\n\n\n# ---- the two constructions of a similarity graph\ndef pairwise_distances(X):\n    \"\"\"Euclidean distance between every pair of rows of X.\"\"\"\n    diff = X[:, None, :] - X[None, :, :]\n    return np.sqrt(np.sum(diff ** 2, axis=-1))\n\n\ndef gaussian_weights(D, sigma):\n    \"\"\"Gaussian weight exp(-d^2 / (2 sigma^2)) for every pair, zero on\n    the diagonal (no self-loops).\"\"\"\n    W = np.exp(-D ** 2 / (2.0 * sigma ** 2))\n    np.fill_diagonal(W, 0.0)\n    return W\n\n\ndef knn_mask(D, k):\n    \"\"\"Symmetric 0/1 matrix: entry (i, i') is 1 when i' is among the k\n    nearest neighbors of i or i among the k nearest of i'.\"\"\"\n    n = len(D)\n    Dn = D.copy()\n    np.fill_diagonal(Dn, np.inf)\n    nearest = np.argsort(Dn, axis=1)[:, :k]\n    M = np.zeros((n, n), dtype=int)\n    for i in range(n):\n        M[i, nearest[i]] = 1\n    return np.maximum(M, M.T)\n\n\ndef knn_width(D, k):\n    \"\"\"Mean distance of a node to its k-th nearest neighbor.\"\"\"\n    Dn = D.copy()\n    np.fill_diagonal(Dn, np.inf)\n    return float(np.mean(np.sort(Dn, axis=1)[:, k - 1]))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-days]** Every 37th day of the year gives the ten nodes, numbered 1 to 10 in order of date."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-days] every 37th day of 2024 as the ten nodes\")\nidx = np.arange(0, m_all, 37)\nX = X_all[idx]\ndates = [dates_all[i] for i in idx]\nn = len(X)\ncheck(f\"[B-days] {n} nodes: \" + \", \".join(dates), n == 10)\ncheck(\"[B-days] the ten feature vectors are distinct\",\n      len({tuple(x) for x in X}) == n)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-weights]** Gaussian weights for all 45 pairs of days, with the width set to the mean distance of a day to its third nearest neighbor; the 3-nearest-neighbor graph keeps an edge when one day is among the three nearest of the other. Weight matrix: symmetric, zero diagonal, nonnegative; edges = positive entries; row sums = weighted degrees; the unweighted graph has entries 0 and 1."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-weights] Gaussian weights and the 3-nearest-neighbor graph\")\nK = 3\nD = pairwise_distances(X)\nsigma = knn_width(D, K)\nW_full = gaussian_weights(D, sigma)\nM_knn = knn_mask(D, K)\nW = W_full * M_knn\niu = np.triu_indices(n, k=1)\nn_pairs = len(iu[0])\nn_edges = int(np.sum(M_knn[iu]))\ncheck(f\"[B-weights] width sigma = {sigma:.2f} degrees (mean distance to \"\n      f\"the {K}rd nearest neighbor)\", 2 < sigma < 15)\ncheck(f\"[B-weights] the fully connected graph has a positive weight on \"\n      f\"all {n_pairs} pairs\", n_pairs == 45 and np.all(W_full[iu] > 0))\ncheck(f\"[B-weights] the {K}-nearest-neighbor graph keeps {n_edges} of the \"\n      f\"{n_pairs} pairs as edges\", n * K / 2 <= n_edges <= n * K)\ncheck(\"[B-weights] the weight matrix is symmetric\", np.allclose(W, W.T))\ncheck(\"[B-weights] its diagonal is zero (no self-loops)\",\n      np.all(np.diag(W) == 0))\ncheck(\"[B-weights] its entries are nonnegative\", np.all(W >= 0))\ncheck(\"[B-weights] the edge set is the set of positive entries\",\n      np.array_equal((W > 0).astype(int), M_knn))\ndeg = W.sum(axis=1)\ncheck(\"[B-weights] a row sum of the weight matrix is the weighted degree \"\n      \"of the node, the sum of the weights of its edges\",\n      np.allclose(deg, [W[i, M_knn[i] == 1].sum() for i in range(n)]))\ncheck(\"[B-weights] the unweighted graph has the entries 0 and 1 only\",\n      set(np.unique(M_knn)) == {0, 1})\nw_edges = W[iu][M_knn[iu] == 1]\nn_strong = int(np.sum(w_edges >= 0.5))\ncheck(f\"[B-weights] edge weights between {w_edges.min():.2f} and \"\n      f\"{w_edges.max():.2f}; {n_strong} edges weigh at least 0.5 and \"\n      f\"{n_edges - n_strong} less\", 0 < n_strong < n_edges)\ni_max, i_min = int(np.argmax(deg)), int(np.argmin(deg))\ncheck(f\"[B-weights] weighted degrees from {deg[i_min]:.2f} (node \"\n      f\"{i_min + 1}, {dates[i_min]}) to {deg[i_max]:.2f} (node {i_max + 1}, \"\n      f\"{dates[i_max]}); unweighted degrees from {M_knn.sum(1).min()} to \"\n      f\"{M_knn.sum(1).max()}\", deg[i_min] > 0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-cut]** The cold days (maximum temperature below 18 degrees) and the warm days: the edges between the two sets carry a smaller share of the weight than of the edges."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-cut] the edges between the cold and the warm days\")\nTHRESH = 18.0\ncold = X[:, 1] < THRESH\nn_cold, n_warm = int(cold.sum()), int((~cold).sum())\ncut = float(W[cold][:, ~cold].sum())\nwithin_cold = float(W[cold][:, cold].sum() / 2)\nwithin_warm = float(W[~cold][:, ~cold].sum() / 2)\ntotal = float(W[iu].sum())\nn_cut = int(M_knn[cold][:, ~cold].sum())\ncheck(f\"[B-cut] {n_cold} cold days (nodes \"\n      + \", \".join(str(i + 1) for i in np.flatnonzero(cold))\n      + f\") and {n_warm} warm days\", n_cold >= 3 and n_warm >= 3)\ncheck(f\"[B-cut] {n_cut} of the {n_edges} edges ({100 * n_cut / n_edges:.1f}%) \"\n      f\"join a cold with a warm day; they carry {cut:.2f} of the total \"\n      f\"weight {total:.2f} ({100 * cut / total:.1f}%), so they are lighter \"\n      f\"than the average edge (inside the cold days {within_cold:.2f}, \"\n      f\"inside the warm days {within_warm:.2f})\",\n      cut / total < n_cut / n_edges)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-year]** The 10-nearest-neighbor graph on all 366 days: number of edges, weighted degrees, and the share of the total weight that joins a cold day with a warm day; no edge joins a January or February day with a July or August day."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-year] the 10-nearest-neighbor graph on all 366 days\")\nK_YEAR = 10\nD_all = pairwise_distances(X_all)\nsigma_all = knn_width(D_all, K_YEAR)\nM_all = knn_mask(D_all, K_YEAR)\nW_all = gaussian_weights(D_all, sigma_all) * M_all\niu_all = np.triu_indices(m_all, k=1)\nn_edges_all = int(M_all[iu_all].sum())\ndeg_all = W_all.sum(axis=1)\ncold_all = X_all[:, 1] < THRESH\ncut_all = float(W_all[cold_all][:, ~cold_all].sum())\ntotal_all = float(W_all[iu_all].sum())\nmonths = np.array([int(d[5:7]) for d in dates_all])\nwinter = np.isin(months, [1, 2])\nsummer = np.isin(months, [7, 8])\ncheck(f\"[B-year] sigma = {sigma_all:.2f} degrees; {n_edges_all} edges on \"\n      f\"{m_all} nodes, out of {len(iu_all[0])} pairs\",\n      m_all * K_YEAR / 2 <= n_edges_all <= m_all * K_YEAR)\ncheck(f\"[B-year] weighted degrees from {deg_all.min():.2f} to \"\n      f\"{deg_all.max():.2f}\", deg_all.min() > 0)\ncheck(f\"[B-year] {int(cold_all.sum())} cold and {int((~cold_all).sum())} \"\n      f\"warm days; the edges between them carry {100 * cut_all / total_all:.1f}% \"\n      f\"of the total weight\", cut_all / total_all < 0.1)\ncheck(\"[B-year] no edge joins a January or February day with a July or \"\n      \"August day\", M_all[winter][:, summer].sum() == 0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-plot]** CSVs for the figure (nodes, edges in two weight classes, the weight matrix) and the matplotlib preview."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-plot] nodes, edges in two weight classes, weight matrix\")\nwith open(OUT_DIR / \"weightedgraph_nodes.csv\", \"w\") as fh:\n    fh.write(\"node,date,tmin,tmax\\n\")\n    for i in range(n):\n        fh.write(f\"{i + 1},{dates[i]},{X[i, 0]:.1f},{X[i, 1]:.1f}\\n\")\nwith open(OUT_DIR / \"weightedgraph_pairs.csv\", \"w\") as fh:\n    fh.write(\"i,ip,distance,w_full,w_knn\\n\")\n    for i, ip in zip(*iu):\n        fh.write(f\"{i + 1},{ip + 1},{D[i, ip]:.3f},{W_full[i, ip]:.4f},\"\n                 f\"{W[i, ip]:.4f}\\n\")\nstrong, weak = [], []\nfor i, ip in zip(*iu):\n    if M_knn[i, ip]:\n        (strong if W[i, ip] >= 0.5 else weak).append((i, ip))\nfor name, edges in ((\"strong\", strong), (\"weak\", weak)):\n    with open(OUT_DIR / f\"weightedgraph_edges_{name}.csv\", \"w\") as fh:\n        fh.write(\"x,y\\n\")\n        for i, ip in edges:\n            fh.write(f\"{X[i, 0]:.1f},{X[i, 1]:.1f}\\n\"\n                     f\"{X[ip, 0]:.1f},{X[ip, 1]:.1f}\\nnan,nan\\n\")\nwith open(OUT_DIR / \"weightedgraph_matrix.csv\", \"w\") as fh:\n    fh.write(\"i,ip,w\\n\")\n    for i in range(n):\n        for ip in range(n):\n            fh.write(f\"{i + 1},{ip + 1},{W[i, ip]:.4f}\\n\")\ncheck(f\"[B-plot] {len(strong)} strong and {len(weak)} weak edges written, \"\n      f\"{n_edges} in all\", len(strong) + len(weak) == n_edges)\n\nfig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.6, 4.2),\n                               gridspec_kw={\"width_ratios\": [1.15, 1]})\nfor i, ip in strong:\n    ax1.plot(X[[i, ip], 0], X[[i, ip], 1], color=\"black\", lw=1.8)\nfor i, ip in weak:\n    ax1.plot(X[[i, ip], 0], X[[i, ip], 1], color=\"0.55\", lw=0.7)\nax1.plot([], [], color=\"black\", lw=1.8, label=\"edge weight at least 0.5\")\nax1.plot([], [], color=\"0.55\", lw=0.7, label=\"edge weight below 0.5\")\nax1.scatter(X[:, 0], X[:, 1], marker=\"o\", color=\"black\", s=30,\n            label=\"the ten days (nodes)\", zorder=3)\nfor i in range(n):\n    ax1.annotate(str(i + 1), (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(\"3-nearest-neighbor graph on ten days of 2024\")\nax1.legend(frameon=False, fontsize=8, loc=\"upper left\")\nim = ax2.imshow(W, cmap=\"Greys\", vmin=0, vmax=1, origin=\"upper\",\n                extent=(0.5, n + 0.5, n + 0.5, 0.5))\nax2.set_xticks(range(1, n + 1))\nax2.set_yticks(range(1, n + 1))\nax2.set_xlabel(\"node i'\")\nax2.set_ylabel(\"node i\")\nax2.set_title(\"weight matrix (dark = large weight)\")\nfig.colorbar(im, ax=ax2, fraction=0.046, pad=0.04, label=\"edge weight\")\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"weightedgraph.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)"
  }
 ]
}