nx_uv_closed_cut_candidate_t280.nx source
↩ module page · 67 lines · 3949 B
1// nx_uv_closed_cut_candidate_t280.nx -- Computes a graph-shortest path cut between approximate-diameter pins in a chart-preserving manner.
2import "nx_uv_chart_topology_candidate_t280.nx"
3import "nx_graphalg.nx"
4// A chart-preserving cut along a graph-shortest path between the existing
5// approximate-diameter pins. Distances are integer source-edge lengths (Q12),
6// not an assertion of a continuous geodesic or an anatomically chosen seam.
7func uct_graph_free(g:*GraphAdj)->i64{
8 if g==(0 as *GraphAdj){return 0}
9 sys_munmap(g.adj_size as *u8,g.n_vertices*UV_I64)
10 sys_munmap(g.adj_to as *u8,g.n_vertices*g.max_edges*UV_I64)
11 sys_munmap(g.adj_w as *u8,g.n_vertices*g.max_edges*UV_I64)
12 return sys_munmap(g as *u8,__size_of(GraphAdj))
13}
14func uct_closed_path(m:*i64,c:i64,target:*i64,outwords:*i64)->*i64{
15 if outwords==(0 as *i64){return 0 as *i64};outwords[0]=0
16 if m==(0 as *i64){return 0 as *i64};if target==(0 as *i64){return 0 as *i64}
17 if c<0{return 0 as *i64};if c>=uv_chart_count(m){return 0 as *i64}
18 if uv_stage(target)!=UV_ST_NEW{return 0 as *i64}
19 let nv:i64=m[UV_H_NV];if target[UV_H_NV]!=nv{return 0 as *i64};if target[UV_H_NT]!=m[UV_H_NT]{return 0 as *i64}
20 var pv:i64=0;while pv<nv{if uv_vx(m,pv)!=uv_vx(target,pv){return 0 as *i64};if uv_vy(m,pv)!=uv_vy(target,pv){return 0 as *i64};if uv_vz(m,pv)!=uv_vz(target,pv){return 0 as *i64};pv=pv+1}
21 var pt:i64=0;while pt<m[UV_H_NT]{var pk:i64=0;while pk<3{if uv_ti(m,pt,pk)!=uv_ti(target,pt,pk){return 0 as *i64};pk=pk+1};pt=pt+1}
22 let top:*i64=uct_measure(m);if top==(0 as *i64){return 0 as *i64}
23 var eligible:i64=0;if top[c*UCT_ROW+6]==2{if top[c*UCT_ROW+3]==0{if top[c*UCT_ROW+5]==0{eligible=1}}}
24 sys_munmap_direct(top as *u8,uv_chart_count(m)*UCT_ROW*UV_I64)
25 if eligible==0{return 0 as *i64}
26 let work:*i64=sys_mmap_try((nv*3+2)*UV_I64) as *i64
27 if (work as i64)<=0{return 0 as *i64}
28 let pins:*i64=((work as i64)+nv*3*UV_I64) as *i64
29 if uv_pins_for(m,c,pins)!=UV_MIN_PINS{sys_munmap_direct(work as *u8,(nv*3+2)*UV_I64);return 0 as *i64}
30 let source:i64=m[m[UV_O_UVSRC]+pins[0]];let destination:i64=m[m[UV_O_UVSRC]+pins[1]]
31 let p0:i64=m[m[UV_O_CSTART]+c];let p1:i64=m[m[UV_O_CSTART]+c+1]
32 var p:i64=p0
33 while p<p1{let t:i64=m[m[UV_O_CORDER]+p];var k:i64=0;while k<3{
34 let a:i64=uv_ti(m,t,k);let b:i64=uv_ti(m,t,(k+1)%3);work[a]=work[a]+1;work[b]=work[b]+1;k=k+1
35 };p=p+1}
36 var maxedges:i64=0;var v:i64=0;while v<nv{if work[v]>maxedges{maxedges=work[v]};v=v+1}
37 if maxedges>NCP_MAX/UV_I64/nv{sys_munmap_direct(work as *u8,(nv*3+2)*UV_I64);return 0 as *i64}
38 let g:*GraphAdj=nx_graphalg_alloc(nv,maxedges)
39 var valid:i64=1;p=p0
40 while p<p1{let t:i64=m[m[UV_O_CORDER]+p];var k:i64=0;while k<3{
41 let a:i64=uv_ti(m,t,k);let b:i64=uv_ti(m,t,(k+1)%3);let weight:i64=uvi_len_q(m,a,b)
42 if weight>(NX_GRAPHALG_INF-1)/nv{valid=0}
43 if weight<=0{valid=0}else{if nx_graphalg_add_undirected_edge(g,a,b,weight)!=0{valid=0}};k=k+1
44 };p=p+1}
45 let dist:*i64=((work as i64)+nv*UV_I64) as *i64
46 let pred:*i64=((work as i64)+nv*2*UV_I64) as *i64
47 if valid==1{if nx_graphalg_dijkstra(g,source,dist,pred)!=0{valid=0}}
48 var length:i64=0;var cur:i64=destination
49 if valid==1{
50 if dist[cur]>=NX_GRAPHALG_INF{valid=0}
51 while cur!=source{if valid==0{break};if length>=nv{valid=0;break}
52 let next:i64=pred[cur];if next<0{valid=0;break};if next>=nv{valid=0;break};if dist[next]>=dist[cur]{valid=0;break}
53 cur=next;length=length+1
54 }
55 }
56 var out:*i64=0 as *i64
57 if valid==1{if length>0{
58 out=sys_mmap_try((1+length*2)*UV_I64) as *i64
59 if (out as i64)<=0{out=0 as *i64}else{
60 out[0]=length;cur=destination;var i:i64=0
61 while cur!=source{let next:i64=pred[cur];out[1+i*2]=cur;out[2+i*2]=next;cur=next;i=i+1}
62 i=0;while i<length{if uv_seam_set(target,out[1+i*2],out[2+i*2])!=UV_OK{valid=0};i=i+1}
63 if valid==0{sys_munmap_direct(out as *u8,(1+length*2)*UV_I64);out=0 as *i64}else{outwords[0]=1+length*2}
64 }
65 }}
66 uct_graph_free(g);sys_munmap_direct(work as *u8,(nv*3+2)*UV_I64);return out
67}