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)