NGF_on_Fractale / src /modules /dimension_utils.py
antaris's picture
Upload 33 files
5543795 verified
Raw History Blame Contribute Delete
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)