code wiki / _hdl_build / nx_geo_route.nx
`nx_geo_route.nx` source

1// nx_geo_route.nx -- LIB: GEO-008 routing -- INTEGER-EXACT Dijkstra shortest path on a weighted
2// graph (road network). Edge weights are integer meters (from GEO-003 geo_distance), so the path is
3// EXACT and DETERMINISTIC -- the marquee exceed angle vs float routers (OSRM/Valhalla/Google), whose
4// float weights admit non-deterministic tie-breaking. Adjacency-matrix form (clear + small-graph
5// fast; a heap is the scale rung, GEO-008b). Composes the rungs below; production road graphs ride
6// the sovereign store (OSM as last-mile DATA). license_tier: ORIGINAL
7import "nx_syscalls.nx"
8const GEO_MAGIC_1024: i64 = 1024
9
10const GEO_INF: i64 = 1099511627776   // 2^40 -- "unreachable" sentinel (well above any earth path in m)
11
12// Dijkstra from `src` over an n-node graph. adj is a flat n*n matrix; adj[u*n+v] > 0 is the weight
13// of edge u->v, 0 means no edge. Writes shortest distances to dist[] and predecessors to prev[]
14// (prev[src] = -1; prev[unreachable] = -1, dist = GEO_INF).
15func geo_dijkstra(adj: *i64, n: i64, src: i64, dist: *i64, prev: *i64) -> i64 {
16    let visited: *i64 = sys_mmap(8 * n) as *i64
17    var i: i64 = 0
18    while i < n { dist[i] = GEO_INF; prev[i] = 0 - 1; visited[i] = 0; i = i + 1 }
19    dist[src] = 0
20    var iter: i64 = 0
21    while iter < n {
22        var u: i64 = 0 - 1
23        var best: i64 = GEO_INF
24        var j: i64 = 0
25        while j < n {
26            if visited[j] == 0 { if dist[j] < best { best = dist[j]; u = j } }
27            j = j + 1
28        }
29        if u < 0 { iter = n } else {
30            visited[u] = 1
31            var v: i64 = 0
32            while v < n {
33                let w: i64 = adj[u * n + v]
34                if w > 0 {
35                    let nd: i64 = dist[u] + w
36                    if nd < dist[v] { dist[v] = nd; prev[v] = u }
37                }
38                v = v + 1
39            }
40            iter = iter + 1
41        }
42    }
43    return 0
44}
45
46// reconstruct the path src->dest from prev[] into path[] (src first); returns hop count (0 if no path).
47func geo_path(prev: *i64, src: i64, dest: i64, path: *i64) -> i64 {
48    let tmp: *i64 = sys_mmap(8 * GEO_MAGIC_1024) as *i64
49    var k: i64 = 0
50    var cur: i64 = dest
51    var go: i64 = 1
52    while go == 1 {
53        tmp[k] = cur
54        k = k + 1
55        if cur == src { go = 0 } else {
56            if prev[cur] < 0 { go = 0; k = 0 } else { cur = prev[cur] }   // no path -> empty
57        }
58    }
59    var i: i64 = 0
60    while i < k { path[i] = tmp[k - 1 - i]; i = i + 1 }
61    return k
62}
63
64// ISOCHRONE: indices of all nodes reachable within `budget` cost from the source (dist[] from
65// geo_dijkstra). The "what's reachable within X" query. Returns count; writes indices to out_idx.
66func geo_isochrone(dist: *i64, n: i64, budget: i64, out_idx: *i64) -> i64 {
67    var c: i64 = 0
68    var i: i64 = 0
69    while i < n {
70        if dist[i] <= budget { out_idx[c] = i; c = c + 1 }
71        i = i + 1
72    }
73    return c
74}
nx_geo_route.nx source

`nx_geo_route.nx` source
