Spaces:
Sleeping
Sleeping
Download src/modules/dimension_utils.py from Sierpinksi-Project/NGF_on_Fractale: direct link, hf CLI and curl.
- Browser
- Download file 5.31 kB
-
https://huggingface.co/spaces/Sierpinksi-Project/NGF_on_Fractale/resolve/main/src/modules/dimension_utils.py
- Command line
-
hf download hf://spaces/Sierpinksi-Project/NGF_on_Fractale/src/modules/dimension_utils.py
-
curl -L -o dimension_utils.py https://huggingface.co/spaces/Sierpinksi-Project/NGF_on_Fractale/resolve/main/src/modules/dimension_utils.py
5.31 kB
| 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) | |