from __future__ import annotations from typing import Dict, Iterable, List, Sequence, Tuple import networkx as nx import numpy as np def choose_seed_nodes( G: nx.Graph, boundary_nodes: Sequence[int], num_seeds: int, rng: np.random.Generator, ) -> List[int]: boundary_nodes = set(boundary_nodes) interior = [n for n in G.nodes if n not in boundary_nodes] candidates = interior if len(interior) >= num_seeds else list(G.nodes) candidates = list(candidates) if len(candidates) <= num_seeds: return candidates idx = rng.choice(len(candidates), size=num_seeds, replace=False) return [candidates[i] for i in idx] def compute_ball_growth( G: nx.Graph, seeds: Sequence[int], r_max: int, use_edge_weights: bool = False, ) -> Tuple[List[int], np.ndarray]: """ Berechne für jede Saat und jeden Radius 1..r_max die Ballgröße N_x(r). Wenn use_edge_weights=False: Es wird die ungewichtete Graphdistanz (Anzahl Schritte) verwendet (nx.single_source_shortest_path_length). Wenn use_edge_weights=True: Es wird eine gewichtete Distanz verwendet, bei der jede Kante die effektive Länge length(u, v, data) = 1 / max(weight_{uv}, eps) trägt, wobei weight_{uv} = G.edges[u, v].get("weight", 1.0) und eps eine kleine positive Konstante ist. Die Distanzen werden über nx.single_source_dijkstra_path_length berechnet. N_x(r) zählt dann die Anzahl der Knoten mit Distanz <= r. Rückgabe: r_vals: Liste der Radien (1..r_max) counts: Array der Form (n_seeds, len(r_vals)) """ r_vals = list(range(1, r_max + 1)) n_seeds = len(seeds) counts = np.zeros((n_seeds, len(r_vals)), dtype=float) for k, s in enumerate(seeds): if use_edge_weights: # gewichtete Distanzen mit effektiver Kantenlänge 1/weight def edge_length(u: int, v: int, data: Dict) -> float: w = float(data.get("weight", 1.0)) if w <= 0.0: w = 1e-8 return 1.0 / w lengths_dict = nx.single_source_dijkstra_path_length( G, source=s, cutoff=float(r_max), weight=edge_length, ) else: # ungewichtete Graphdistanz lengths_dict = nx.single_source_shortest_path_length(G, s, cutoff=r_max) if not lengths_dict: continue dists = np.fromiter((float(d) for d in lengths_dict.values()), dtype=float) for i, r in enumerate(r_vals): counts[k, i] = float((dists <= float(r)).sum()) return r_vals, counts def compute_ball_growth_geometric( G: nx.Graph, coords: Dict[int, np.ndarray], seeds: Sequence[int], r_max_steps: int, ) -> Tuple[np.ndarray, np.ndarray]: """ Berechne Ballgrößen N_x(R) in der eingebetteten Geometrie. Für jeden Seed x und jeden Radius R_i = i * ell_edge (i=1..r_max_steps) wird N_x(R_i) = |{ y : ||r_y - r_x|| <= R_i }| bestimmt, wobei ell_edge die typische Kantenlänge (Median) der Kanten im Graphen ist. Rückgabe: r_vals: Array der geometrischen Radien R_i counts: Array der Form (n_seeds, len(r_vals)) """ if r_max_steps <= 0 or len(seeds) == 0: return np.array([], dtype=float), np.zeros((0, 0), dtype=float) # typische Kantenlänge aus der Einbettung bestimmen 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: ell_edge = float(np.median(edge_lengths)) else: ell_edge = 1.0 # Radii in Einheiten von ell_edge r_vals = np.arange(1, r_max_steps + 1, dtype=float) * ell_edge # Knotenliste und Positionsarray für schnelle Distanzberechnung nodes = list(coords.keys()) pos_arr = np.stack([np.asarray(coords[n], dtype=float) for n in nodes], axis=0) index = {n: i for i, n in enumerate(nodes)} n_seeds = len(seeds) counts = np.zeros((n_seeds, len(r_vals)), dtype=float) for k, s in enumerate(seeds): if s not in index: continue idx_s = index[s] rs = pos_arr[idx_s] dists = np.linalg.norm(pos_arr - rs, axis=1) for i, R in enumerate(r_vals): counts[k, i] = float((dists <= float(R)).sum()) return r_vals, counts def estimate_dimension_from_counts( r_vals: Sequence[int], N_vals: Sequence[float], r_min_fit: int, r_max_fit: int, ) -> float: """ Schätze die effektive Dimension aus N(r) durch Fit von log N vs. log r im Fenster [r_min_fit, r_max_fit]. """ r_arr = np.asarray(r_vals, dtype=float) N_arr = np.asarray(N_vals, dtype=float) mask = ( (r_arr >= float(r_min_fit)) & (r_arr <= float(r_max_fit)) & (r_arr > 0.0) & (N_arr > 0.0) ) if mask.sum() < 2: return float("nan") log_r = np.log(r_arr[mask]) log_N = np.log(N_arr[mask]) slope, _ = np.polyfit(log_r, log_N, 1) return float(slope)