Files
MeltMind/tools/s3b_graph.py

201 lines
11 KiB
Python

"""Fixed S3-B(a) geometry and exact capacity events. No data or label I/O."""
from itertools import combinations
import time
import numpy as np
from scipy.sparse import coo_matrix, diags
from scipy.sparse.csgraph import connected_components
from scipy.sparse.linalg import cg
from boundary_distance import SurfaceDistance
SOLVER = dict(name='scipy.sparse.linalg.cg', preconditioner='Jacobi',
rtol=1e-11, atol=0., maxiter=2000, warm_start=True,
acceptance_residual=1e-8, flux_tolerance=1e-8,
negative_flux_tolerance=1e-10, mass_tolerance=1e-8,
tie_mass_tolerance=1e-12, event_batching=False)
class NumericalFailure(RuntimeError):
pass
def weighted_median(values, mass):
values, mass = np.asarray(values), np.asarray(mass)
if values.shape != mass.shape or not np.isfinite(values).all() or np.any(mass <= 0):
raise ValueError('Invalid weighted median domain')
order = np.argsort(values, kind='stable')
return float(values[order[np.searchsorted(np.cumsum(mass[order]), mass.sum()/2, side='left')]])
def distal_regions(distance, mass, edges, raw_ids):
"""Strict distal induced graph includes original zero-conductance edges."""
n = len(mass)
if not np.isfinite(distance).all():
return dict(status='INVALID_GEODESIC', threshold=None, regions=[])
threshold = weighted_median(distance, mass)
ids = np.flatnonzero(distance > threshold)
local = np.full(n, -1, dtype=np.int64); local[ids] = np.arange(len(ids))
e = edges[(local[edges] >= 0).all(axis=1)]
if not len(ids):
return dict(status='NO_USABLE_DISTAL_PAIR', threshold=threshold, regions=[])
graph = coo_matrix((np.ones(2*len(e)),
(np.r_[local[e[:, 0]], local[e[:, 1]]],
np.r_[local[e[:, 1]], local[e[:, 0]]])),
shape=(len(ids), len(ids))).tocsr()
count, labels = connected_components(graph, directed=False)
groups = [ids[labels == j] for j in range(count)]
groups.sort(key=lambda a: (-float(mass[a].sum()), int(raw_ids[a].min())))
selected = groups[:2]
valid = len(selected) == 2 and all(mass[a].sum() >= .05*mass.sum() for a in selected)
return dict(status='VALID' if valid else 'NO_USABLE_DISTAL_PAIR', threshold=threshold,
distal_volume=float(mass[ids].sum()), distal_components=count,
regions=[dict(local_ids=a.tolist(), raw_ids=raw_ids[a].tolist(),
volume=float(mass[a].sum())) for a in selected])
def edge_geometry(x, tetra, faces, dw, cached_edges, cached_mass, query_progress=None):
if (not np.isfinite(x).all() or not np.isfinite(dw).all() or np.any(dw < 0)
or len(dw) != len(x)):
raise ValueError('Invalid geometry/distance')
start = time.process_time()
cells = x[tetra]
volumes = np.abs(np.linalg.det(cells[:, 1:] - cells[:, :1]))/6
if not np.isfinite(volumes).all() or np.any(volumes <= 0):
raise ValueError('Nonpositive tetrahedron')
mass = np.bincount(tetra.ravel(), weights=np.repeat(volumes/4, 4), minlength=len(x))
if np.any(mass <= 0) or not np.allclose(mass, cached_mass, rtol=1e-12, atol=0):
raise ValueError('Original node capacity differs')
all_edges = np.sort(np.concatenate([tetra[:, [i, j]] for i, j in combinations(range(4), 2)]), axis=1)
edges, inverse = np.unique(all_edges, axis=0, return_inverse=True)
if not np.array_equal(edges, cached_edges):
raise ValueError('Original edge identity differs')
edge_volume = np.bincount(inverse, weights=np.tile(volumes/6, 6), minlength=len(edges))
length = np.linalg.norm(x[edges[:, 1]] - x[edges[:, 0]], axis=1)
if np.any(length <= 0) or not np.isfinite(length).all():
raise ValueError('Invalid edge length')
n = len(x)
wall_edges = np.sort(np.concatenate([faces[:, [0, 1]], faces[:, [0, 2]], faces[:, [1, 2]]]), axis=1)
keys = edges[:, 0].astype(np.int64)*n + edges[:, 1]
wall_keys = np.unique(wall_edges[:, 0].astype(np.int64)*n + wall_edges[:, 1])
is_wall = np.isin(keys, wall_keys)
both_wall = (dw[edges] == 0).all(axis=1)
if not both_wall[is_wall].all():
raise ValueError('Surface edge endpoints not original zero-distance nodes')
midpoint = dw[edges].mean(axis=1)
midpoint[is_wall] = 0.
queries = np.flatnonzero(both_wall & ~is_wall)
geometry_cpu = time.process_time()-start
start = time.process_time()
if len(queries):
surface = SurfaceDistance(x[faces])
for k in range(0, len(queries), 256):
ids = queries[k:k+256]
midpoint[ids] = surface.query(x[edges[ids]].mean(axis=1))
if query_progress:
query_progress(min(k+256, len(queries)), len(queries))
midpoint_cpu = time.process_time()-start
if not np.isfinite(midpoint).all() or np.any(midpoint < 0):
raise NumericalFailure('Invalid midpoint distance')
g = edge_volume/length**2*midpoint**2
if not np.isfinite(g).all() or np.any((midpoint > 0) & (g <= 0)):
raise NumericalFailure('Positive conductance underflow/invalid value')
return dict(mass=mass, edges=edges, edge_volume=edge_volume, midpoint=midpoint, conductance=g,
exact_query_edge_ids=queries, boundary_edges=is_wall,
geometry_CPU_s=geometry_cpu, midpoint_CPU_s=midpoint_cpu)
def pressure_step(adjacency, laplacian, wet, seed, previous, Q=1., solver=cg):
ids = np.flatnonzero(wet)
a = laplacian[ids][:, ids].tocsr()
diagonal = a.diagonal()
if np.any(diagonal <= 0):
raise NumericalFailure('Positive-source pressure matrix is singular')
b = np.zeros(len(ids)); b[np.searchsorted(ids, seed)] = Q
iterations = 0
def callback(_):
nonlocal iterations
iterations += 1
start = time.process_time(); wall = time.monotonic()
p, info = solver(a, b, x0=previous[ids], M=diags(1/diagonal),
rtol=SOLVER['rtol'], atol=SOLVER['atol'],
maxiter=SOLVER['maxiter'], callback=callback)
cpu, elapsed = time.process_time()-start, time.monotonic()-wall
residual = float(np.linalg.norm(a@p-b)/Q)
if info != 0 or not np.isfinite(p).all() or not np.isfinite(residual) or residual > SOLVER['acceptance_residual']:
raise NumericalFailure(f'CG failed: info={info}, iterations={iterations}, residual={residual}')
pressure = np.zeros(len(wet)); pressure[ids] = p
rates = np.asarray(adjacency @ pressure); rates[wet] = 0.
if np.any(rates < -SOLVER['negative_flux_tolerance']*Q):
raise NumericalFailure('Negative front flux exceeds accepted tolerance')
negative_roundoff = float(-rates[rates < 0].sum())
rates[rates < 0] = 0.
imbalance = float(abs(rates.sum()-Q)/Q)
if imbalance > SOLVER['flux_tolerance']:
raise NumericalFailure(f'Flux balance {imbalance} exceeds tolerance')
return pressure, rates, dict(iterations=iterations, pressure_residual=residual,
flux_imbalance=imbalance, negative_flux_roundoff=negative_roundoff,
solve_CPU_s=cpu, solve_wall_s=elapsed, wetted_nodes=len(ids), matrix_nnz=a.nnz)
def fill_events(edges, g, mass, seed, event_callback=None, state_callback=None, Q=1., solver=cg):
"""One pressure solve per exact event; simultaneous capacity ties only."""
n = len(mass); M = float(mass.sum())
if not np.isfinite(mass).all() or np.any(mass <= 0) or not np.isfinite(g).all() or np.any(g < 0) or Q <= 0:
raise ValueError('Invalid event domain')
positive = g > 0
scale = float(g.max()) if positive.any() else 1.
gn = g[positive]/scale
if np.any(gn <= 0):
raise NumericalFailure('Conductance normalization underflow')
e = edges[positive]
adj = coo_matrix((np.tile(gn, 2), (np.r_[e[:, 0], e[:, 1]], np.r_[e[:, 1], e[:, 0]])), shape=(n, n)).tocsr()
lap = diags(np.asarray(adj.sum(axis=1)).ravel()) - adj
remaining = np.asarray(mass, float).copy(); remaining[seed] = 0.
wet = np.zeros(n, bool); wet[seed] = True
arrival = np.full(n, np.nan); arrival[seed] = 0.
pressure = np.zeros(n); clock = 0.; rounding = 0.; events = 0
initial = float(mass[seed]); total_solve = 0.
def state(status):
return dict(status=status, remaining_volume=float(remaining.sum()), total_volume=M,
initial_seed_volume=initial, filled_nodes=int(wet.sum()), events=events,
graph_time=clock, cumulative_rounding_volume=rounding,
conductance_normalization=scale, solve_CPU_s=total_solve)
if state_callback: state_callback(state('INITIALIZED'), remaining, arrival)
while not wet.all():
front_counts = np.asarray(adj @ wet.astype(float)); front_counts[wet] = 0.
if not (front_counts > 0).any():
return arrival, remaining, state('BLOCKED')
event_cpu = time.process_time()
pressure, rates, diagnostic = pressure_step(adj, lap, wet, seed, pressure, Q, solver)
active = rates > 0
if not active.any():
raise NumericalFailure('Positive graph frontier but no positive numerical flow')
dt = float(np.min(remaining[active]/rates[active]))
if not np.isfinite(dt) or dt <= 0 or clock+dt <= clock:
raise NumericalFailure('Nonpositive/unrepresentable exact event time')
before = float(remaining.sum())
new = remaining - dt*rates
tolerance = SOLVER['tie_mass_tolerance']*M
if np.min(new) < -tolerance:
raise NumericalFailure('Capacity overshoot')
exhausted = (~wet) & active & (new <= tolerance)
if not exhausted.any():
raise NumericalFailure('No capacity exhausted in exact event')
correction = float(np.abs(new[exhausted]).sum())
new[exhausted] = 0.
if abs((before-new.sum())-Q*dt) > SOLVER['mass_tolerance']*M:
raise NumericalFailure('Per-event volume conservation failed')
next_clock = clock+dt
if rounding+correction > SOLVER['mass_tolerance']*M or abs((M-new.sum()-initial)-Q*next_clock) > SOLVER['mass_tolerance']*M:
raise NumericalFailure('Cumulative volume conservation failed')
remaining = new; clock = next_clock; rounding += correction
wet[exhausted] = True; arrival[exhausted] = clock; events += 1
total_solve += diagnostic['solve_CPU_s']
diagnostic.update(event=events, graph_time=clock, delta_time=dt, newly_wet=int(exhausted.sum()),
remaining_volume=float(remaining.sum()), rounding_volume=correction,
front_count=int(active.sum()), split_concentration=float(np.sum((rates/Q)**2)),
event_CPU_s=time.process_time()-event_cpu)
if event_callback: event_callback(diagnostic)
if state_callback: state_callback(state('RUNNING'), remaining, arrival)
if events > n: raise NumericalFailure('Event count exceeds node count')
return arrival, remaining, state('COMPLETE')