Files
MeltMind/tools/route_feasibility.py

181 lines
13 KiB
Python

"""CPU-only prototypes for geometry grouping and local coordinate frames.
No fitted model, frozen type ontology, split, or physical thickness estimator.
All mesh nodes and edges are retained; partitions add an aggregation mapping.
"""
import argparse
import hashlib
import heapq
import itertools
import json
from pathlib import Path
import resource
import time
import numpy as np
from scipy.sparse import coo_matrix,diags
from scipy.sparse.csgraph import connected_components,dijkstra
from scipy.stats import spearmanr
def graph_from_edges(n,edges,lengths=None):
weights=np.ones(len(edges)) if lengths is None else lengths
return coo_matrix((np.r_[weights,weights],(np.r_[edges[:,0],edges[:,1]],np.r_[edges[:,1],edges[:,0]])),shape=(n,n)).tocsr()
def node_tensor(points,tet,volumes,distance,graph,steps=3):
q=points[tet]
gradient=np.linalg.solve(q[:,1:]-q[:,:1],(distance[tet[:,1:]]-distance[tet[:,:1]])[...,None])[...,0]
norm=np.linalg.norm(gradient,axis=1);good=norm>1e-8
normal=gradient/np.where(good,norm,1)[:,None]
cellvolume=np.abs(np.linalg.det(q[:,1:]-q[:,:1]))/6
raw=np.zeros((len(points),9));mass=np.zeros(len(points))
outer=(normal[:,:,None]*normal[:,None,:]).reshape(-1,9)
for j in range(4):
np.add.at(raw,tet[:,j],outer*(cellvolume*good/4)[:,None])
np.add.at(mass,tet[:,j],cellvolume*good/4)
raw/=np.where(mass>0,mass,1)[:,None]
# A stated mesh-dependent stencil, NOT a physical-length neighbourhood.
adjacency=graph.copy();adjacency.data[:]=1;adjacency.setdiag(1)
weights=adjacency@diags(volumes)
average=diags(1/np.asarray(weights.sum(axis=1)).ravel())@weights
for _ in range(steps):raw=average@raw
tensor=raw.reshape(-1,3,3)
return tensor,average,dict(zero_gradient_tet_fraction=float((~good).mean()),initial_unsupported_node_fraction=float((mass==0).mean()),diffusion_steps=steps,gradient_norm_quantiles=np.quantile(norm,[0,.5,.99,1]).tolist())
def spectral_features(tensor):
values,basis=np.linalg.eigh(tensor);values=values[:,::-1];basis=basis[:,:,::-1]
tr=values.sum(1);frac=values/np.where(tr>1e-12,tr,1)[:,None]
gap1=(values[:,0]-values[:,1])/np.maximum(values[:,0],1e-12)
gap2=(values[:,1]-values[:,2])/np.maximum(values[:,0],1e-12)
axis=(tr>1e-10)&(gap1>.1)
full=axis&(gap2>.1)
# Proxy tensor-rank labels, NOT frozen wall/rib/junction semantics.
kind=np.full(len(tensor),2,dtype=np.int8)
kind[(frac[:,0]>=.8)&(tr>1e-10)]=0
kind[(frac[:,0]<.65)&(frac[:,1]>=.25)&(frac[:,2]<=.15)&(tr>1e-10)]=1
kind[tr<=1e-10]=3
return dict(eigenvalues=values,basis=basis,fraction=frac,gap1=gap1,gap2=gap2,axis=axis,full=full,kind=kind)
def farthest_seeds(points,mass,k):
center=np.average(points,axis=0,weights=mass)
first=int(np.argmax(np.sum((points-center)**2,axis=1)))
seeds=[first];nearest=np.sum((points-points[first])**2,axis=1)
for _ in range(1,k):
nearest[seeds]=-1
i=int(np.argmax(nearest));seeds.append(i)
nearest=np.minimum(nearest,np.sum((points-points[i])**2,axis=1))
return np.array(seeds)
def connected_voronoi(graph,seeds):
"""Positive-weight multi-source graph paths guarantee connected assigned cells."""
n=graph.shape[0];labels=np.full(n,-1,dtype=np.int32);dist=np.full(n,np.inf)
queue=[]
for group,node in enumerate(seeds):
dist[node]=0;labels[node]=group;heapq.heappush(queue,(0.,group,int(node)))
while queue:
value,group,u=heapq.heappop(queue)
if value!=dist[u] or group!=labels[u]:continue
for pos in range(graph.indptr[u],graph.indptr[u+1]):
v=int(graph.indices[pos]);candidate=value+graph.data[pos]
if candidate<dist[v]:
dist[v]=candidate;labels[v]=group;heapq.heappush(queue,(candidate,group,v))
if np.any(labels<0):raise ValueError('Disconnected source graph: needs component-aware seeds')
return labels
def partition_report(labels,graph,edges,points,mass,kind):
k=int(labels.max()+1);volume=np.bincount(labels,weights=mass,minlength=k);fractions=volume/volume.sum()
component_counts=[];aspect=[];entropy=0
for group in range(k):
ids=np.flatnonzero(labels==group)
component_counts.append(int(connected_components(graph[ids][:,ids],directed=False,return_labels=False)))
delta=points[ids]-np.average(points[ids],axis=0,weights=mass[ids])
covariance=(delta*mass[ids,None]).T@delta/mass[ids].sum()
eig=np.linalg.eigvalsh(covariance)
aspect.append(float(np.sqrt(max(eig[-1],0)/max(eig[0],1e-24))))
hist=np.bincount(kind[ids],weights=mass[ids],minlength=4);prob=hist/hist.sum();nz=prob>0
entropy+=fractions[group]*float(-(prob[nz]*np.log(prob[nz])).sum())
cross=labels[edges[:,0]]!=labels[edges[:,1]]
pairs=np.unique(np.sort(labels[edges[cross]],axis=1),axis=0)
quotient=graph_from_edges(k,pairs)
return dict(k=k,component_counts=component_counts,all_connected=all(c==1 for c in component_counts),volume_fractions=fractions.tolist(),max_to_mean_volume=float(fractions.max()*k),min_to_mean_volume=float(fractions.min()*k),aspect=aspect,within_region_type_entropy=entropy,cross_edge_fraction=float(cross.mean()),quotient_edges=len(pairs),quotient_components=int(connected_components(quotient,directed=False,return_labels=False)),retained_original_edges=len(edges),repair_nodes=0)
def matched_acceptance(candidate,reference):
# Provisional implementation screen, preregistered here before outputs.
volume_l1=float(np.abs(np.sort(candidate['volume_fractions'])-np.sort(reference['volume_fractions'])).sum())
q=np.array([.1,.5,.9]);ca=np.quantile(candidate['aspect'],q);ra=np.quantile(reference['aspect'],q)
aspect_log_delta=float(np.max(np.abs(np.log(np.maximum(ca,1e-12)/np.maximum(ra,1e-12)))))
cut_delta=abs(candidate['cross_edge_fraction']-reference['cross_edge_fraction'])
passed=candidate['all_connected'] and candidate['k']==reference['k'] and volume_l1<=.1 and aspect_log_delta<=np.log(1.25) and cut_delta<=.05
return dict(pass_provisional=bool(passed),sorted_volume_fraction_l1=volume_l1,aspect_quantile_max_abs_log_ratio=aspect_log_delta,cross_edge_fraction_delta=cut_delta,limits=dict(volume_l1=.1,aspect_ratio=1.25,cross_edge_fraction_delta=.05),status='engineering feasibility only; not a statistical equivalence test or frozen trial rule')
def bottleneck(graph,times,sources):
best=np.full(len(times),np.inf);queue=[]
for node in sources:best[node]=times[node];heapq.heappush(queue,(float(times[node]),int(node)))
while queue:
t,u=heapq.heappop(queue)
if t!=best[u]:continue
for pos in range(graph.indptr[u],graph.indptr[u+1]):
v=int(graph.indices[pos]);candidate=max(t,times[v])
if candidate<best[v]:best[v]=candidate;heapq.heappush(queue,(float(candidate),v))
return best
def filling_baselines(graph,points,fill,mass,gate):
started=time.monotonic();gate_dist=np.linalg.norm(points-gate,axis=1);nearest=int(np.argmin(gate_dist))
geodesic=dijkstra(graph,directed=False,indices=nearest)
# Spearman does not fit a scale; no train/test split or fitted L2 is invented.
result=dict(gate_node=nearest,gate_distance_raw=float(gate_dist[nearest]),spearman_geodesic_fill=float(spearmanr(geodesic,fill).statistic),relative_l2=None,relative_l2_reason='No frozen training groups; no scale fitted on evaluation parts',violations=[])
for fraction in [0.,1e-6,1e-4]:
tol=float(fraction*fill.max())
for label,sources in [('yml_nearest',np.array([nearest])),('near_minimum_diagnostic',np.flatnonzero(fill<=fill.min()+tol))]:
m=bottleneck(graph,fill,sources);bad=m>fill+tol
result['violations'].append(dict(gate=label,source_count=len(sources),tolerance_fraction=fraction,tolerance_seconds=tol,nodes=int(bad.sum()),volume_fraction=float(mass[bad].sum()/mass.sum()),max_delay_seconds=float((m-fill).max())))
result['wall_seconds']=time.monotonic()-started
return result
def main():
p=argparse.ArgumentParser();p.add_argument('sample',type=Path);p.add_argument('distance',type=Path);p.add_argument('output',type=Path);p.add_argument('--k',type=int,default=32);a=p.parse_args()
a.output.mkdir(parents=True,exist_ok=True);target=a.output/(a.sample.stem+'.routes.json')
if target.exists():raise FileExistsError('Preserve previous route result; use a new output directory')
start=time.monotonic();d=np.load(a.sample);x=d['points_raw'];edges=d['edges'];mass=d['node_volume_raw'];tet=d['tetra'];distance=np.load(a.distance)
if len(distance)!=len(x) or not np.isfinite(distance).all():raise ValueError('Invalid cached distance')
lengths=np.linalg.norm(x[edges[:,0]]-x[edges[:,1]],axis=1)
if (lengths<=0).any():raise ValueError('Zero length graph edge')
graph=graph_from_edges(len(x),edges,lengths);marks={}
tick=time.monotonic();tensor,average,meta=node_tensor(x,tet,mass,distance,graph);features=spectral_features(tensor);marks['descriptor_seconds']=time.monotonic()-tick
axis=features['axis'];full=features['full'];kind=features['kind'];E=features['basis'];rng=np.random.default_rng(1729)
rotations={};q,_=np.linalg.qr(rng.normal(size=(3,3)))
for name,R in [('rotation',q*np.linalg.det(q)),('reflection',q@np.diag([-1.,1.,1.]))]:
transformed=x@R.T+np.array([3.1,-7.,2.]);t2,_,_=node_tensor(transformed,tet,mass,distance,graph)
f2=spectral_features(t2);expected=R@tensor@R.T
b2=f2['basis'];basis_expected=R@E
sign=np.sign(np.einsum('nij,nij->nj',basis_expected,b2));sign[sign==0]=1
frame_error=np.linalg.norm(b2*sign[:,None,:]-basis_expected,axis=(1,2))
rotations[name]=dict(tensor_max_abs_error=float(abs(t2-expected).max()),type_change_fraction=float((kind!=f2['kind']).mean()),validity_change_fraction=float((full!=f2['full']).mean()),full_frame_orbit_max_error=float(frame_error[full&f2['full']].max(initial=0)),normal_projector_max_error=float(np.abs(b2[axis,:,0,None]*b2[axis,None,:,0]-basis_expected[axis,:,0,None]*basis_expected[axis,None,:,0]).max(initial=0)))
local_center=average@x;delta=x-local_center;local=np.einsum('ni,nij->nj',delta,E);reconstruction=np.einsum('nj,nij->ni',local,E)+local_center
masks=dict(full_frame_node_fraction=float(full.mean()),full_frame_volume_fraction=float(mass[full].sum()/mass.sum()),normal_axis_node_fraction=float(axis.mean()),normal_axis_volume_fraction=float(mass[axis].sum()/mass.sum()),ambiguous_node_fraction=float((~full).mean()),reconstruction_max_error_raw=float(abs(reconstruction-x).max()),rank_proxy_node_counts=np.bincount(kind,minlength=4).tolist(),rank_proxy_volume_fractions=(np.bincount(kind,weights=mass,minlength=4)/mass.sum()).tolist())
# A modest stencil sensitivity check, not evidence of remeshing stability.
t5,_,_=node_tensor(x,tet,mass,distance,graph,steps=5);f5=spectral_features(t5)
sensitivity=dict(type_change_fraction_3_vs_5_hops=float((kind!=f5['kind']).mean()),full_validity_change_fraction_3_vs_5_hops=float((full!=f5['full']).mean()))
tick=time.monotonic();seeds=farthest_seeds(x,mass,a.k);partition_results={};label_cache={}
random_kind=kind[rng.permutation(len(x))]
for name,alpha,types in [('generic',0,kind),('type_alpha1',1,kind),('type_alpha4',4,kind),('control_alpha1',1,random_kind),('control_alpha4',4,random_kind)]:
then=time.monotonic();weight=lengths*(1+alpha*(types[edges[:,0]]!=types[edges[:,1]]));g=graph_from_edges(len(x),edges,weight)
labels=connected_voronoi(g,seeds);report=partition_report(labels,graph,edges,x,mass,kind);report['seconds']=time.monotonic()-then
if name!='generic':report['matching']=matched_acceptance(report,partition_results['generic'])
partition_results[name]=report;label_cache[name]=labels
marks['partition_seconds']=time.monotonic()-tick
tick=time.monotonic();baseline=filling_baselines(graph,x,d['fill_time_raw'],mass,d['gate_location_raw']);marks['baseline_seconds']=time.monotonic()-tick
np.savez_compressed(a.output/(a.sample.stem+'.route_arrays.npz'),tensor=tensor,type_proxy=kind,frame_valid=full,axis_valid=axis,seeds=seeds,**label_cache)
result=dict(case=a.sample.stem,nodes=len(x),edges=len(edges),k=a.k,source_sample_sha256=hashlib.sha256(a.sample.read_bytes()).hexdigest(),source_distance_sha256=hashlib.sha256(a.distance.read_bytes()).hexdigest(),descriptor=meta,frames=masks,pose_checks=rotations,stencil_sensitivity=sensitivity,partitions=partition_results,baselines=baseline,timings=marks,wall_seconds=time.monotonic()-start,peak_rss_kib=resource.getrusage(resource.RUSAGE_SELF).ru_maxrss,scope='Three-part feasibility prototype. No training, split, full-corpus rate, type ontology, thickness or chart map claim.')
target.write_text(json.dumps(result,indent=2,allow_nan=False)+'\n');print(json.dumps({k:result[k] for k in ['case','frames','pose_checks','stencil_sensitivity','timings','wall_seconds','peak_rss_kib']},indent=2),flush=True)
if __name__=='__main__':main()