Spaces:
Sleeping
Sleeping
File size: 5,308 Bytes
5543795 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 |
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)
|