nx_graphalg_test.nx source

1// nx_graphalg_test.nx -- smoke for graph algorithms. 2 3import "syscalls.nx" 4import "nx_graphalg.nx" 5 6func main() -> i64 { 7 // === Test 1: construct + neighbor query === 8 let g: *GraphAdj = nx_graphalg_alloc(5, 4) 9 nx_graphalg_add_edge(g, 0, 1, 10) 10 nx_graphalg_add_edge(g, 0, 2, 5) 11 nx_graphalg_add_edge(g, 1, 3, 20) 12 if nx_graphalg_neighbor_count(g, 0) != 2 { return 1 } 13 if nx_graphalg_neighbor_count(g, 1) != 1 { return 2 } 14 if nx_graphalg_neighbor_count(g, 4) != 0 { return 3 } 15 if nx_graphalg_neighbor(g, 0, 0) != 1 { return 4 } 16 if nx_graphalg_neighbor(g, 0, 1) != 2 { return 5 } 17 if nx_graphalg_neighbor_weight(g, 0, 0) != 10 { return 6 } 18 19 // === Test 2: undirected edge === 20 let g2: *GraphAdj = nx_graphalg_alloc(3, 4) 21 nx_graphalg_add_undirected_edge(g2, 0, 1, 7) 22 if nx_graphalg_neighbor_count(g2, 0) != 1 { return 10 } 23 if nx_graphalg_neighbor_count(g2, 1) != 1 { return 11 } 24 if nx_graphalg_neighbor(g2, 0, 0) != 1 { return 12 } 25 if nx_graphalg_neighbor(g2, 1, 0) != 0 { return 13 } 26 27 // === Test 3: BFS on chain 0->1->2->3->4 === 28 let chain: *GraphAdj = nx_graphalg_alloc(5, 2) 29 nx_graphalg_add_edge(chain, 0, 1, 1) 30 nx_graphalg_add_edge(chain, 1, 2, 1) 31 nx_graphalg_add_edge(chain, 2, 3, 1) 32 nx_graphalg_add_edge(chain, 3, 4, 1) 33 let dist: *i64 = (sys_mmap(5 * 8)) as *i64 34 nx_graphalg_bfs(chain, 0, dist) 35 if dist[0] != 0 { return 20 } 36 if dist[1] != 1 { return 21 } 37 if dist[2] != 2 { return 22 } 38 if dist[3] != 3 { return 23 } 39 if dist[4] != 4 { return 24 } 40 41 // === Test 4: BFS unreachable === 42 let split: *GraphAdj = nx_graphalg_alloc(4, 2) 43 nx_graphalg_add_edge(split, 0, 1, 1) 44 nx_graphalg_add_edge(split, 2, 3, 1) 45 let dist2: *i64 = (sys_mmap(4 * 8)) as *i64 46 nx_graphalg_bfs(split, 0, dist2) 47 if dist2[0] != 0 { return 30 } 48 if dist2[1] != 1 { return 31 } 49 if dist2[2] != NX_GRAPHALG_INF { return 32 } 50 if dist2[3] != NX_GRAPHALG_INF { return 33 } 51 52 // === Test 5: Dijkstra shortest path === 53 let dg: *GraphAdj = nx_graphalg_alloc(4, 3) 54 nx_graphalg_add_edge(dg, 0, 1, 10) 55 nx_graphalg_add_edge(dg, 0, 2, 3) 56 nx_graphalg_add_edge(dg, 1, 3, 1) 57 nx_graphalg_add_edge(dg, 2, 3, 2) 58 let dd: *i64 = (sys_mmap(4 * 8)) as *i64 59 let dp: *i64 = (sys_mmap(4 * 8)) as *i64 60 nx_graphalg_dijkstra(dg, 0, dd, dp) 61 if dd[0] != 0 { return 40 } 62 if dd[1] != 10 { return 41 } 63 if dd[2] != 3 { return 42 } 64 if dd[3] != 5 { return 43 } 65 if dp[3] != 2 { return 44 } 66 if dp[2] != 0 { return 45 } 67 if dp[1] != 0 { return 46 } 68 69 // === Test 6: Dijkstra with parallel edges === 70 let dg2: *GraphAdj = nx_graphalg_alloc(3, 3) 71 nx_graphalg_add_edge(dg2, 0, 1, 100) 72 nx_graphalg_add_edge(dg2, 0, 1, 5) 73 nx_graphalg_add_edge(dg2, 1, 2, 7) 74 let dd2: *i64 = (sys_mmap(3 * 8)) as *i64 75 let dp2: *i64 = (sys_mmap(3 * 8)) as *i64 76 nx_graphalg_dijkstra(dg2, 0, dd2, dp2) 77 if dd2[1] != 5 { return 50 } 78 if dd2[2] != 12 { return 51 } 79 80 // === Test 7: topological sort on DAG === 81 let dag: *GraphAdj = nx_graphalg_alloc(4, 3) 82 nx_graphalg_add_edge(dag, 0, 1, 0) 83 nx_graphalg_add_edge(dag, 0, 2, 0) 84 nx_graphalg_add_edge(dag, 1, 3, 0) 85 nx_graphalg_add_edge(dag, 2, 3, 0) 86 let order: *i64 = (sys_mmap(4 * 8)) as *i64 87 if nx_graphalg_toposort(dag, order) != 0 { return 60 } 88 if order[0] != 0 { return 61 } 89 if order[3] != 3 { return 62 } 90 var mid_ok: i64 = 0 91 if order[1] == 1 { if order[2] == 2 { mid_ok = 1 } } 92 if order[1] == 2 { if order[2] == 1 { mid_ok = 1 } } 93 if mid_ok != 1 { return 63 } 94 95 // === Test 8: cycle detection === 96 let cyc: *GraphAdj = nx_graphalg_alloc(3, 2) 97 nx_graphalg_add_edge(cyc, 0, 1, 0) 98 nx_graphalg_add_edge(cyc, 1, 2, 0) 99 nx_graphalg_add_edge(cyc, 2, 0, 0) 100 let order2: *i64 = (sys_mmap(3 * 8)) as *i64 101 if nx_graphalg_toposort(cyc, order2) != -1 { return 70 } 102 103 return 0 104}