nx_graph.nx source
↩ module page · 111 lines · 3404 B
1// nx_graph.nx -- foundational graph theory primitives.
2//
3// Adjacency matrix representation for small graphs (caller manages
4// the n x n array as flat i64 buffer).
5//
6// genealogy_id: euler_1736 (konigsberg_bridges) + classical
7// lineage_id: zfc_separation + relation_symmetry
8// axioms: NX_AX_ZFC_SEPARATION, NX_AX_REL_SYMMETRY
9
10// nx_safety_envelope:
11// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
12// sil_target: SIL1
13// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
14// verdict: NOT_YET_EVALUATED
15
16import "syscalls.nx"
17import "nx_axioms.nx"
18
19// Degree of vertex v in an n x n adjacency matrix (flat i64 array).
20func nx_graph_degree(adj: *i64, n: i64, v: i64) -> i64 {
21 if v < 0 { return -1 }
22 if v >= n { return -1 }
23 var deg: i64 = 0
24 var u: i64 = 0
25 while u < n {
26 if adj[v * n + u] != 0 { deg = deg + 1 }
27 u = u + 1
28 }
29 return deg
30}
31
32// Count edges in undirected graph. Each edge counted once.
33func nx_graph_edge_count(adj: *i64, n: i64) -> i64 {
34 var count: i64 = 0
35 var i: i64 = 0
36 while i < n {
37 var j: i64 = i + 1
38 while j < n {
39 if adj[i * n + j] != 0 { count = count + 1 }
40 j = j + 1
41 }
42 i = i + 1
43 }
44 return count
45}
46
47// Eulerian circuit existence: connected graph with all vertices of
48// even degree. Returns 1 if Eulerian circuit exists, 0 if not.
49//
50// Used directly for Freek #54 (Konigsberg bridges -- famously NO
51// Eulerian circuit because all 4 vertices have odd degree).
52func nx_graph_has_eulerian_circuit(adj: *i64, n: i64) -> i64 {
53 var v: i64 = 0
54 while v < n {
55 let d: i64 = nx_graph_degree(adj, n, v)
56 if d - (d / 2) * 2 != 0 { return 0 } // odd degree
57 v = v + 1
58 }
59 return 1
60}
61
62// BFS visit count: starts from vertex 0, returns count of reachable
63// vertices. Used for connectivity check.
64func nx_graph_bfs_count(adj: *i64, n: i64, start: i64) -> i64 {
65 let visited: *i64 = (sys_mmap(n * 8)) as *i64
66 let queue: *i64 = (sys_mmap(n * 8)) as *i64
67 var i: i64 = 0
68 while i < n { visited[i] = 0; i = i + 1 }
69 queue[0] = start
70 visited[start] = 1
71 var head: i64 = 0
72 var tail: i64 = 1
73 var count: i64 = 1
74 while head < tail {
75 let v: i64 = queue[head]
76 head = head + 1
77 var u: i64 = 0
78 while u < n {
79 if adj[v * n + u] != 0 {
80 if visited[u] == 0 {
81 visited[u] = 1
82 queue[tail] = u
83 tail = tail + 1
84 count = count + 1
85 }
86 }
87 u = u + 1
88 }
89 }
90 return count
91}
92
93// Connectivity check: BFS from vertex 0 reaches all n vertices?
94func nx_graph_is_connected(adj: *i64, n: i64) -> i64 {
95 if n <= 0 { return 0 }
96 if nx_graph_bfs_count(adj, n, 0) == n { return 1 }
97 return 0
98}
99
100// Friendship theorem witness (Freek #83):
101// In a graph where every pair of vertices has exactly one common friend,
102// there exists a vertex adjacent to all others (politician).
103// Substrate: given adj matrix, return such a politician vertex or -1.
104func nx_graph_friendship_politician(adj: *i64, n: i64) -> i64 {
105 var v: i64 = 0
106 while v < n {
107 if nx_graph_degree(adj, n, v) == n - 1 { return v }
108 v = v + 1
109 }
110 return -1
111}