Spaces:
Sleeping
Sleeping
Download src/modules/tab_b0_clusters.py from Sierpinksi-Project/NGF_on_Fractale: direct link, hf CLI and curl.
- Browser
- Download file 18.7 kB
-
https://huggingface.co/spaces/Sierpinksi-Project/NGF_on_Fractale/resolve/main/src/modules/tab_b0_clusters.py
- Command line
-
hf download hf://spaces/Sierpinksi-Project/NGF_on_Fractale/src/modules/tab_b0_clusters.py
-
curl -L -o tab_b0_clusters.py https://huggingface.co/spaces/Sierpinksi-Project/NGF_on_Fractale/resolve/main/src/modules/tab_b0_clusters.py
18.7 kB
| from __future__ import annotations | |
| from typing import Dict, List, Sequence, Tuple | |
| import networkx as nx | |
| import numpy as np | |
| import plotly.graph_objects as go | |
| import streamlit as st | |
| from . import dimension_utils | |
| TAB_TITLE = "B.0 – Clusteranalyse" | |
| TAB_ORDER = 50 | |
| def _compute_typical_edge_length(G: nx.Graph, coords: Dict[int, np.ndarray]) -> float: | |
| """Bestimme eine typische Kantenlänge (Median) aus der Einbettung. | |
| Falls keine Kanten oder unvollständige Koordinaten vorhanden sind, | |
| wird 1.0 als Fallback verwendet. | |
| """ | |
| edge_lengths: List[float] = [] | |
| for u, v in G.edges: | |
| if u not in coords or v not in coords: | |
| continue | |
| ru = np.asarray(coords[u], dtype=float) | |
| rv = np.asarray(coords[v], dtype=float) | |
| edge_lengths.append(float(np.linalg.norm(rv - ru))) | |
| if edge_lengths: | |
| return float(np.median(edge_lengths)) | |
| return 1.0 | |
| def _auto_cluster_params( | |
| G: nx.Graph, | |
| coords: Dict[int, np.ndarray], | |
| ell_edge: float, | |
| ) -> Dict[str, float]: | |
| """Heuristische Auto-Setup-Funktion für die Cluster-/Patchanalyse. | |
| Leitet sinnvolle Startwerte für die Regler aus den verfügbaren Daten ab: | |
| - Anzahl Knoten/Kanten | |
| - typische Kantenlänge ℓ_edge | |
| - mittlere Knotengrade | |
| Die Werte werden nur als *Vorschläge* verwendet; der Nutzer kann sie | |
| über die Regler jederzeit überschreiben. | |
| """ | |
| n_nodes = G.number_of_nodes() | |
| n_edges = G.number_of_edges() | |
| n_nodes = max(n_nodes, 1) | |
| # mittlerer Knotengrad | |
| avg_deg = 2.0 * n_edges / n_nodes if n_nodes > 0 else 0.0 | |
| # Radius in Einheiten von ℓ_edge: | |
| # - kleinere Graphen: eher etwas größerer Radius, um genügend Nachbarn zu haben | |
| # - dichte/hochgradige Graphen: Radius leicht reduzieren | |
| if n_nodes < 500: | |
| R_units = 2.0 | |
| elif n_nodes < 2000: | |
| R_units = 2.5 | |
| elif n_nodes < 10000: | |
| R_units = 3.0 | |
| else: | |
| R_units = 3.5 | |
| if avg_deg > 6: | |
| R_units *= 0.9 | |
| elif avg_deg < 3: | |
| R_units *= 1.1 | |
| # Begrenzung auf Sliderbereich | |
| R_units = float(np.clip(R_units, 0.5, 5.0)) | |
| # Dichteschwelle: | |
| # - kleine Graphen: niedrigeres Perzentil, um genügend Knoten zu bekommen | |
| # - große Graphen: höheres Perzentil, um nur die wirklich dichten Regionen zu nehmen | |
| if n_nodes < 500: | |
| percentile = 70 | |
| elif n_nodes < 2000: | |
| percentile = 80 | |
| elif n_nodes < 10000: | |
| percentile = 90 | |
| else: | |
| percentile = 95 | |
| # minimale Clustergröße: | |
| # skalieren mit N, aber begrenzen nach oben/unten | |
| min_cluster_size = max(5, n_nodes // 200) | |
| max_reasonable = max(10, n_nodes // 20) | |
| if min_cluster_size > max_reasonable: | |
| min_cluster_size = max_reasonable | |
| # Radius-Schritte für die Dimensionsanalyse | |
| if n_nodes < 500: | |
| max_r_steps = 5 | |
| elif n_nodes < 2000: | |
| max_r_steps = 6 | |
| elif n_nodes < 10000: | |
| max_r_steps = 7 | |
| else: | |
| max_r_steps = 8 | |
| # Seeds pro Cluster für die Dimensionsanalyse | |
| if n_nodes < 500: | |
| seeds_per_cluster = 2 | |
| elif n_nodes < 2000: | |
| seeds_per_cluster = 3 | |
| else: | |
| seeds_per_cluster = 4 | |
| return { | |
| "R_units": float(R_units), | |
| "percentile": float(percentile), | |
| "min_cluster_size": float(min_cluster_size), | |
| "max_r_steps": float(max_r_steps), | |
| "seeds_per_cluster": float(seeds_per_cluster), | |
| } | |
| def _compute_local_densities( | |
| coords: Dict[int, np.ndarray], | |
| radius: float, | |
| ) -> Tuple[List[int], np.ndarray]: | |
| """Berechne lokale Knotendichten für einen gegebenen geometrischen Radius. | |
| Für jeden Knoten i wird die Anzahl der Knoten innerhalb des Radius R | |
| gezählt: | |
| rho_R(i) = |{ j : ||r_j - r_i|| <= R }| | |
| Rückgabe: | |
| nodes: Liste der Knoten-IDs in derselben Reihenfolge wie rho | |
| rho: Array der Dichten (gleiche Länge wie nodes) | |
| """ | |
| if not coords: | |
| return [], np.zeros(0, dtype=float) | |
| nodes = list(coords.keys()) | |
| pos_arr = np.stack([np.asarray(coords[n], dtype=float) for n in nodes], axis=0) | |
| n = pos_arr.shape[0] | |
| rho = np.zeros(n, dtype=float) | |
| # O(N^2)-Algorithmus, aber mit NumPy-Vektorisierung ausreichend schnell | |
| for i in range(n): | |
| di = np.linalg.norm(pos_arr - pos_arr[i], axis=1) | |
| rho[i] = float((di <= float(radius)).sum()) | |
| return nodes, rho | |
| def _detect_clusters( | |
| G: nx.Graph, | |
| nodes: Sequence[int], | |
| densities: np.ndarray, | |
| percentile: float, | |
| min_cluster_size: int, | |
| ) -> Tuple[List[List[int]], float]: | |
| """Finde Cluster als zusammenhängende Komponenten hochdichter Knoten. | |
| - Die Dichte-Schwelle wird als Perzentil über rho bestimmt. | |
| - Es wird der induzierte Teilgraph der Knoten mit rho >= Schwelle gebildet. | |
| - Zusammenhängende Komponenten mit Größe >= min_cluster_size gelten als Cluster. | |
| Rückgabe: | |
| clusters: Liste von Listen von Knoten-IDs (nach absteigender Größe sortiert) | |
| rho_th: verwendete Dichte-Schwelle | |
| """ | |
| if len(nodes) == 0 or densities.size == 0: | |
| return [], float("nan") | |
| rho_th = float(np.percentile(densities, percentile)) | |
| selected = [n for n, r in zip(nodes, densities) if r >= rho_th] | |
| if not selected: | |
| return [], rho_th | |
| H = G.subgraph(selected).copy() | |
| comps = [ | |
| sorted(list(c)) | |
| for c in nx.connected_components(H) | |
| if len(c) >= min_cluster_size | |
| ] | |
| # Größte Cluster zuerst | |
| comps.sort(key=len, reverse=True) | |
| return comps, rho_th | |
| def _estimate_cluster_dimension( | |
| G: nx.Graph, | |
| coords: Dict[int, np.ndarray], | |
| cluster_nodes: Sequence[int], | |
| max_r_steps: int, | |
| num_seeds: int, | |
| rng: np.random.Generator, | |
| ) -> Tuple[float, float]: | |
| """Schätze die geometrische Dimension eines Clusters. | |
| - Es wird ein Teilgraph auf cluster_nodes gebildet. | |
| - Seeds werden zufällig aus dem Cluster gewählt. | |
| - Es wird compute_ball_growth_geometric auf diesem Teilgraphen verwendet. | |
| - Aus N_x(R) wird mittels estimate_dimension_from_counts die Dimension bestimmt. | |
| Rückgabe: | |
| (d_mean, d_std) – Mittelwert und Streuung über Seeds. | |
| Falls keine sinnvolle Schätzung möglich ist, werden (nan, nan) zurückgegeben. | |
| """ | |
| if len(cluster_nodes) < 2: | |
| return float("nan"), float("nan") | |
| subG = G.subgraph(cluster_nodes).copy() | |
| sub_coords = {n: coords[n] for n in cluster_nodes if n in coords} | |
| if len(sub_coords) < 2: | |
| return float("nan"), float("nan") | |
| available_nodes = list(sub_coords.keys()) | |
| n_seeds = min(max(1, num_seeds), len(available_nodes)) | |
| seeds = rng.choice(available_nodes, size=n_seeds, replace=False) | |
| r_vals, counts = dimension_utils.compute_ball_growth_geometric( | |
| subG, | |
| sub_coords, | |
| seeds, | |
| r_max_steps=max_r_steps, | |
| ) | |
| if r_vals.size == 0 or counts.size == 0: | |
| return float("nan"), float("nan") | |
| # Fit-Bereich: interne Radien (wenn möglich) verwenden | |
| if len(r_vals) >= 3: | |
| r_min_fit = float(r_vals[1]) | |
| r_max_fit = float(r_vals[-1]) | |
| else: | |
| r_min_fit = float(r_vals[0]) | |
| r_max_fit = float(r_vals[-1]) | |
| dims = [] | |
| for k in range(counts.shape[0]): | |
| d_k = dimension_utils.estimate_dimension_from_counts( | |
| r_vals, | |
| counts[k, :], | |
| r_min_fit=r_min_fit, | |
| r_max_fit=r_max_fit, | |
| ) | |
| dims.append(d_k) | |
| d_arr = np.asarray(dims, dtype=float) | |
| if np.all(np.isnan(d_arr)): | |
| return float("nan"), float("nan") | |
| return float(np.nanmean(d_arr)), float(np.nanstd(d_arr)) | |
| def render_tab(context: Dict): | |
| st.subheader("Lokale Cluster- und Patchanalyse") | |
| fractal_id = context["fractal_id"] | |
| level = context["level"] | |
| G_ideal = context["G_ideal"] | |
| pos_ideal = context["pos_ideal"] | |
| G_real = context["G_real"] | |
| pos_real = context["pos_real"] | |
| boundary_nodes = context["boundary_nodes"] | |
| seed_global = int(context.get("random_seed", 42)) | |
| st.markdown( | |
| f""" | |
| **Fraktal:** `{fractal_id}` **Level:** `{level}` | |
| **Knoten (IDEAL):** {G_ideal.number_of_nodes()} **Kanten (IDEAL):** {G_ideal.number_of_edges()} | |
| Dieses Tab analysiert lokale Dichtefluktuationen in der eingebetteten Struktur | |
| und identifiziert hochdichte Cluster/Patches im Graphen. | |
| """ | |
| ) | |
| with st.expander("Einstellungen für die Cluster- und Patchanalyse", expanded=True): | |
| graph_choice = st.radio( | |
| "Graph für die Clusteranalyse", | |
| ("REAL-Graph (empfohlen)", "IDEAL-Graph"), | |
| index=0, | |
| help=( | |
| "Beim REAL-Graph sind Kantengewichte und Geometrie bereits durch Bad und Selbstwechselwirkung " | |
| "verändert. Der IDEAL-Graph dient als Referenz." | |
| ), | |
| ) | |
| if graph_choice.startswith("REAL"): | |
| G = G_real | |
| coords = pos_real | |
| else: | |
| G = G_ideal | |
| coords = pos_ideal | |
| ell_edge = _compute_typical_edge_length(G, coords) | |
| st.markdown( | |
| f"Typische Kantenlänge (Median) in der Einbettung: **ℓ_edge ≈ {ell_edge:.3g}**" | |
| ) | |
| # Auto-Setup: heuristische Vorschläge für alle relevanten Parameter | |
| auto_params = _auto_cluster_params(G, coords, ell_edge) | |
| st.markdown( | |
| "Die initialen Werte der Regler werden automatisch aus den Graphparametern " | |
| "(Anzahl Knoten/Kanten, mittlerer Grad, ℓ_edge) abgeleitet und können bei Bedarf manuell angepasst werden." | |
| ) | |
| # Radius R (in Einheiten von ℓ_edge) | |
| R_units_default = float(np.clip(auto_params["R_units"], 0.5, 5.0)) | |
| R_units = st.slider( | |
| "Radius R für lokale Dichte (in Einheiten von ℓ_edge)", | |
| min_value=0.5, | |
| max_value=5.0, | |
| value=R_units_default, | |
| step=0.5, | |
| help=( | |
| "R bestimmt den lokalen Nachbarschaftsbereich: " | |
| "Für jeden Knoten werden alle Knoten innerhalb Distanz R·ℓ_edge gezählt." | |
| ), | |
| ) | |
| R = float(R_units * ell_edge) | |
| # Dichteschwelle (Perzentil) | |
| percentile_default = int(np.clip(auto_params["percentile"], 50, 99)) | |
| percentile = st.slider( | |
| "Dichteschwelle (Perzentil)", | |
| min_value=50, | |
| max_value=99, | |
| value=percentile_default, | |
| step=1, | |
| help=( | |
| "Knoten mit einer Dichte oberhalb dieses Perzentils werden als hochdicht betrachtet " | |
| "und für die Clusterbildung verwendet." | |
| ), | |
| ) | |
| max_nodes = G.number_of_nodes() | |
| # Sliderbereich dynamisch, Default aus Auto-Setup, aber auf Bereich begrenzt | |
| min_cluster_size_min = 5 | |
| min_cluster_size_max = max(10, max_nodes // 5) if max_nodes > 0 else 10 | |
| min_cluster_size_default = int( | |
| np.clip(auto_params["min_cluster_size"], min_cluster_size_min, min_cluster_size_max) | |
| ) | |
| min_cluster_size = st.slider( | |
| "Minimale Clustergröße (Anzahl Knoten)", | |
| min_value=min_cluster_size_min, | |
| max_value=min_cluster_size_max, | |
| value=min_cluster_size_default, | |
| step=5, | |
| help="Zusammenhängende Komponenten kleiner als diese Größe werden verworfen.", | |
| ) | |
| # max. Radius-Schritte für Dimensionsanalyse | |
| max_r_steps_default = int(np.clip(auto_params["max_r_steps"], 3, 10)) | |
| max_r_steps = st.slider( | |
| "Maximaler Radius (Schritte) für Dimensionsanalyse pro Cluster", | |
| min_value=3, | |
| max_value=10, | |
| value=max_r_steps_default, | |
| step=1, | |
| ) | |
| # Seeds pro Cluster | |
| seeds_default = int(np.clip(auto_params["seeds_per_cluster"], 1, 6)) | |
| seeds_per_cluster = st.slider( | |
| "Anzahl Seeds pro Cluster für Dimensionsanalyse", | |
| min_value=1, | |
| max_value=6, | |
| value=seeds_default, | |
| step=1, | |
| ) | |
| st.markdown( | |
| "Hinweis: Die Berechnung der lokalen Dichte ist O(N²) und kann bei großen Graphen einige Sekunden dauern." | |
| ) | |
| rng = np.random.default_rng(seed_global + 17) | |
| with st.spinner("Berechne lokale Dichten und Cluster ..."): | |
| nodes, rho = _compute_local_densities(coords, radius=R) | |
| if len(nodes) == 0: | |
| st.warning("Keine Koordinaten verfügbar – Clusteranalyse nicht möglich.") | |
| return | |
| clusters, rho_th = _detect_clusters( | |
| G, | |
| nodes, | |
| rho, | |
| percentile=float(percentile), | |
| min_cluster_size=int(min_cluster_size), | |
| ) | |
| st.markdown( | |
| f"Verwendete Dichteschwelle: **ρ_th = {rho_th:.1f}** " | |
| f"(Perzentil {percentile} der lokalen Dichten)." | |
| ) | |
| if not clusters: | |
| st.info( | |
| "Mit den aktuellen Parametern wurden keine Cluster mit ausreichender Größe gefunden. " | |
| "Reduziere die Dichteschwelle oder die minimale Clustergröße." | |
| ) | |
| return | |
| # Robuste Behandlung: kein Slider, wenn genau ein Cluster gefunden wurde | |
| n_clusters = len(clusters) | |
| if n_clusters == 1: | |
| st.info( | |
| "Mit den aktuellen Parametern wurde genau ein Cluster gefunden. " | |
| "Die Analyse wird für diesen einen Cluster durchgeführt." | |
| ) | |
| max_clusters = 1 | |
| else: | |
| max_clusters = st.slider( | |
| "Maximale Anzahl ausgewerteter Cluster (nach Größe)", | |
| min_value=1, | |
| max_value=min(6, n_clusters), | |
| value=min(3, n_clusters), | |
| step=1, | |
| ) | |
| # Dimensionsanalyse pro Cluster | |
| cluster_summaries = [] | |
| for idx, cluster_nodes in enumerate(clusters[:max_clusters]): | |
| d_mean, d_std = _estimate_cluster_dimension( | |
| G, | |
| coords, | |
| cluster_nodes, | |
| max_r_steps=max_r_steps, | |
| num_seeds=seeds_per_cluster, | |
| rng=rng, | |
| ) | |
| dens_values = [rho[nodes.index(n)] for n in cluster_nodes if n in nodes] | |
| avg_dens = float(np.mean(dens_values)) if dens_values else float("nan") | |
| cluster_summaries.append( | |
| { | |
| "Cluster": idx + 1, | |
| "Knoten": len(cluster_nodes), | |
| "⟨ρ_R⟩": avg_dens, | |
| "d_eff": d_mean, | |
| "σ_d": d_std, | |
| } | |
| ) | |
| st.markdown("### Zusammenfassung der größten Cluster") | |
| try: | |
| import pandas as pd # type: ignore | |
| df = pd.DataFrame(cluster_summaries) | |
| st.dataframe(df, use_container_width=True) | |
| except Exception: | |
| # Fallback ohne pandas | |
| for cs in cluster_summaries: | |
| st.markdown( | |
| f"- **Cluster {cs['Cluster']}**: " | |
| f"{cs['Knoten']} Knoten, ⟨ρ_R⟩ ≈ {cs['⟨ρ_R⟩']:.1f}, " | |
| f"d_eff ≈ {cs['d_eff']:.3f} ± {cs['σ_d']:.3f}" | |
| ) | |
| # Visualisierung: Cluster farblich markieren | |
| st.markdown("### Geometrische Struktur der Cluster") | |
| show_edges = st.checkbox( | |
| "Kanten im Plot anzeigen", | |
| value=False, | |
| help="Zur besseren Übersicht können die Kanten ausgeblendet werden.", | |
| ) | |
| # Farbschema für Cluster (begrenzte Palette, wird bei Bedarf zyklisch wiederverwendet) | |
| color_cycle = [ | |
| "#e41a1c", | |
| "#377eb8", | |
| "#4daf4a", | |
| "#984ea3", | |
| "#ff7f00", | |
| "#ffff33", | |
| "#a65628", | |
| "#f781bf", | |
| ] | |
| cluster_id_by_node = {} | |
| for idx, cluster_nodes in enumerate(clusters[:max_clusters]): | |
| for n in cluster_nodes: | |
| cluster_id_by_node[n] = idx | |
| x_bg = [] | |
| y_bg = [] | |
| z_bg = [] | |
| for n in nodes: | |
| if n in cluster_id_by_node: | |
| continue | |
| p = coords[n] | |
| x_bg.append(p[0]) | |
| y_bg.append(p[1]) | |
| z_bg.append(p[2]) | |
| fig = go.Figure() | |
| if show_edges: | |
| x_e = [] | |
| y_e = [] | |
| z_e = [] | |
| for u, v in G.edges: | |
| if u not in coords or v not in coords: | |
| continue | |
| p0 = coords[u] | |
| p1 = coords[v] | |
| x_e += [p0[0], p1[0], None] | |
| y_e += [p0[1], p1[1], None] | |
| z_e += [p0[2], p1[2], None] | |
| fig.add_trace( | |
| go.Scatter3d( | |
| x=x_e, | |
| y=y_e, | |
| z=z_e, | |
| mode="lines", | |
| name="Kanten", | |
| line=dict(width=1, color="rgba(150,150,200,0.35)"), | |
| hoverinfo="skip", | |
| ) | |
| ) | |
| # Hintergrundknoten (nicht im Cluster) | |
| fig.add_trace( | |
| go.Scatter3d( | |
| x=x_bg, | |
| y=y_bg, | |
| z=z_bg, | |
| mode="markers", | |
| name="Hintergrund", | |
| marker=dict(size=2, color="rgba(180,180,180,0.4)"), | |
| hoverinfo="skip", | |
| ) | |
| ) | |
| # Clusterknoten | |
| for idx, cluster_nodes in enumerate(clusters[:max_clusters]): | |
| xs = [] | |
| ys = [] | |
| zs = [] | |
| for n in cluster_nodes: | |
| if n not in coords: | |
| continue | |
| p = coords[n] | |
| xs.append(p[0]) | |
| ys.append(p[1]) | |
| zs.append(p[2]) | |
| color = color_cycle[idx % len(color_cycle)] | |
| fig.add_trace( | |
| go.Scatter3d( | |
| x=xs, | |
| y=ys, | |
| z=zs, | |
| mode="markers", | |
| name=f"Cluster {idx + 1}", | |
| marker=dict(size=4, color=color), | |
| hoverinfo="text", | |
| text=[f"Cluster {idx + 1}, Node {n}" for n in cluster_nodes], | |
| ) | |
| ) | |
| # Randknoten (zur Orientierung) | |
| x_bd = [] | |
| y_bd = [] | |
| z_bd = [] | |
| for b in boundary_nodes: | |
| if b not in coords: | |
| continue | |
| p = coords[b] | |
| x_bd.append(p[0]) | |
| y_bd.append(p[1]) | |
| z_bd.append(p[2]) | |
| if x_bd: | |
| fig.add_trace( | |
| go.Scatter3d( | |
| x=x_bd, | |
| y=y_bd, | |
| z=z_bd, | |
| mode="markers", | |
| name="Randknoten", | |
| marker=dict(size=3, color="black", symbol="diamond"), | |
| hoverinfo="skip", | |
| ) | |
| ) | |
| fig.update_layout( | |
| scene=dict( | |
| xaxis_title="x", | |
| yaxis_title="y", | |
| zaxis_title="z", | |
| aspectmode="data", | |
| ), | |
| legend=dict(orientation="h", yanchor="bottom", y=1.02, xanchor="left", x=0.0), | |
| margin=dict(l=0, r=0, b=0, t=30), | |
| ) | |
| st.plotly_chart(fig, use_container_width=True) | |