nx_graphalg.nx source
↩ module page · 210 lines · 6424 B
1// nx_graphalg.nx -- graph algorithms (BFS + Dijkstra + topological sort).
2//
3// Adjacency-list representation with bounded fan-out (max_edges per
4// vertex). Pure i64. Priority queue via sketch_min_heap.
5//
6// Sibling of nx_graph.nx (which provides adjacency-MATRIX primitives
7// for math/theorem use); this module provides adjacency-LIST graph
8// algorithms for navigation, planning, and dependency resolution.
9//
10// What this unlocks:
11// + shortest-path navigation (Dijkstra, BFS)
12// + dependency resolution / build order (topological sort)
13// + planning, routing, scheduling
14// + control-flow + dataflow + call-graph reasoning
15// + state-machine reachability
16//
17// Representation:
18// adj_to[u * max_edges + j] : target of u's jth edge
19// adj_w [u * max_edges + j] : weight of that edge
20// adj_size[u] : current edge count of u (0..max_edges)
21//
22// genealogy_id: dijkstra_1959 + kahn_1962_topological + moore_1959_bfs
23// lineage_id: adjacency_list + priority_queue_dijkstra
24
25// nx_safety_envelope:
26// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
27// sil_target: SIL1
28// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
29// verdict: NOT_YET_EVALUATED
30
31import "syscalls.nx"
32import "sketch_min_heap.nx"
33
34const NX_GRAPHALG_INF: i64 = 9000000000000000000
35
36struct GraphAdj {
37 n_vertices: i64,
38 max_edges: i64,
39 adj_size: *i64,
40 adj_to: *i64,
41 adj_w: *i64,
42}
43
44func nx_graphalg_alloc(n_vertices: i64, max_edges: i64) -> *GraphAdj {
45 let g: *GraphAdj = (sys_mmap(40)) as *GraphAdj
46 g.n_vertices = n_vertices
47 g.max_edges = max_edges
48 g.adj_size = (sys_mmap(n_vertices * 8)) as *i64
49 g.adj_to = (sys_mmap(n_vertices * max_edges * 8)) as *i64
50 g.adj_w = (sys_mmap(n_vertices * max_edges * 8)) as *i64
51 var i: i64 = 0
52 while i < n_vertices {
53 g.adj_size[i] = 0
54 i = i + 1
55 }
56 return g
57}
58
59func nx_graphalg_add_edge(g: *GraphAdj, u: i64, v: i64, w: i64) -> i64 {
60 let sz: i64 = g.adj_size[u]
61 if sz >= g.max_edges { return -1 }
62 let idx: i64 = u * g.max_edges + sz
63 g.adj_to[idx] = v
64 g.adj_w[idx] = w
65 g.adj_size[u] = sz + 1
66 return 0
67}
68
69func nx_graphalg_add_undirected_edge(g: *GraphAdj, u: i64, v: i64,
70 w: i64) -> i64 {
71 let r1: i64 = nx_graphalg_add_edge(g, u, v, w)
72 if r1 != 0 { return r1 }
73 return nx_graphalg_add_edge(g, v, u, w)
74}
75
76func nx_graphalg_neighbor_count(g: *GraphAdj, u: i64) -> i64 {
77 return g.adj_size[u]
78}
79
80func nx_graphalg_neighbor(g: *GraphAdj, u: i64, j: i64) -> i64 {
81 return g.adj_to[u * g.max_edges + j]
82}
83
84func nx_graphalg_neighbor_weight(g: *GraphAdj, u: i64, j: i64) -> i64 {
85 return g.adj_w[u * g.max_edges + j]
86}
87
88// ===== BFS shortest path (unweighted) ==================================
89
90func nx_graphalg_bfs(g: *GraphAdj, src: i64, dist_out: *i64) -> i64 {
91 var i: i64 = 0
92 while i < g.n_vertices {
93 dist_out[i] = NX_GRAPHALG_INF
94 i = i + 1
95 }
96 dist_out[src] = 0
97 let queue: *i64 = (sys_mmap(g.n_vertices * 8)) as *i64
98 var head: i64 = 0
99 var tail: i64 = 0
100 queue[tail] = src
101 tail = tail + 1
102 while head < tail {
103 let u: i64 = queue[head]
104 head = head + 1
105 let du: i64 = dist_out[u]
106 let nb: i64 = nx_graphalg_neighbor_count(g, u)
107 var j: i64 = 0
108 while j < nb {
109 let v: i64 = nx_graphalg_neighbor(g, u, j)
110 if dist_out[v] == NX_GRAPHALG_INF {
111 dist_out[v] = du + 1
112 queue[tail] = v
113 tail = tail + 1
114 }
115 j = j + 1
116 }
117 }
118 return 0
119}
120
121// ===== Dijkstra shortest path (non-negative weights) ===================
122
123func nx_graphalg_dijkstra(g: *GraphAdj, src: i64,
124 dist_out: *i64, pred_out: *i64) -> i64 {
125 var i: i64 = 0
126 while i < g.n_vertices {
127 dist_out[i] = NX_GRAPHALG_INF
128 pred_out[i] = -1
129 i = i + 1
130 }
131 dist_out[src] = 0
132 let heap: *MinHeap = nx_heap_alloc(g.n_vertices * g.max_edges + 8)
133 nx_heap_push(heap, 0, src)
134 while nx_heap_size(heap) > 0 {
135 let cur_dist: i64 = nx_heap_peek_key(heap)
136 let u: i64 = nx_heap_peek_value(heap)
137 nx_heap_pop(heap)
138 if cur_dist <= dist_out[u] {
139 let nb: i64 = nx_graphalg_neighbor_count(g, u)
140 var j: i64 = 0
141 while j < nb {
142 let v: i64 = nx_graphalg_neighbor(g, u, j)
143 let w: i64 = nx_graphalg_neighbor_weight(g, u, j)
144 let candidate: i64 = cur_dist + w
145 if candidate < dist_out[v] {
146 dist_out[v] = candidate
147 pred_out[v] = u
148 nx_heap_push(heap, candidate, v)
149 }
150 j = j + 1
151 }
152 }
153 }
154 return 0
155}
156
157// ===== Topological sort (Kahn's algorithm) =============================
158//
159// Returns 0 on success, -1 if cycle detected.
160
161func nx_graphalg_toposort(g: *GraphAdj, order_out: *i64) -> i64 {
162 let indeg: *i64 = (sys_mmap(g.n_vertices * 8)) as *i64
163 var i: i64 = 0
164 while i < g.n_vertices {
165 indeg[i] = 0
166 i = i + 1
167 }
168 var u: i64 = 0
169 while u < g.n_vertices {
170 let nb: i64 = nx_graphalg_neighbor_count(g, u)
171 var j: i64 = 0
172 while j < nb {
173 let v: i64 = nx_graphalg_neighbor(g, u, j)
174 indeg[v] = indeg[v] + 1
175 j = j + 1
176 }
177 u = u + 1
178 }
179 let queue: *i64 = (sys_mmap(g.n_vertices * 8)) as *i64
180 var head: i64 = 0
181 var tail: i64 = 0
182 var v0: i64 = 0
183 while v0 < g.n_vertices {
184 if indeg[v0] == 0 {
185 queue[tail] = v0
186 tail = tail + 1
187 }
188 v0 = v0 + 1
189 }
190 var n_emitted: i64 = 0
191 while head < tail {
192 let cur: i64 = queue[head]
193 head = head + 1
194 order_out[n_emitted] = cur
195 n_emitted = n_emitted + 1
196 let nb: i64 = nx_graphalg_neighbor_count(g, cur)
197 var k: i64 = 0
198 while k < nb {
199 let nv: i64 = nx_graphalg_neighbor(g, cur, k)
200 indeg[nv] = indeg[nv] - 1
201 if indeg[nv] == 0 {
202 queue[tail] = nv
203 tail = tail + 1
204 }
205 k = k + 1
206 }
207 }
208 if n_emitted != g.n_vertices { return -1 }
209 return 0
210}