tritium demo dijkstra
transcript ·
python ·
c ·
rust
# TRITIUM-PROVENANCE sha256=cecf307e190155d45c2cc7a93a750de16f8670bcbb0f247d9967748079f4e335 lang=python
# TRITIUM-HEIGHT high=0.12 mid=0.20 low=0.68 fns=14
# TRITIUM-PSEUDO fn=fill_list
#| fn fill_list(vals, n, v):
#| return 0
# TRITIUM-HEIGHT fn=fill_list high=0.00 mid=0.34 low=0.66 role=mid_helper
def fill_list(vals, n, v):
i = 0
while i < n:
vals[i] = v
i = i + 1
return 0
# TRITIUM-PSEUDO fn=sift_up
#| fn sift_up(heap_dist, heap_node, i):
#| return i
# TRITIUM-HEIGHT fn=sift_up high=0.00 mid=0.31 low=0.69 role=mid_helper
def sift_up(heap_dist, heap_node, i):
while i > 0:
p = (i - 1) // 2
if heap_dist[i] >= heap_dist[p]:
break
tmp_dist = heap_dist[i]
heap_dist[i] = heap_dist[p]
heap_dist[p] = tmp_dist
tmp_node = heap_node[i]
heap_node[i] = heap_node[p]
heap_node[p] = tmp_node
i = p
return i
# TRITIUM-PSEUDO fn=sift_down
#| fn sift_down(heap_dist, heap_node, last):
#| return i
# TRITIUM-HEIGHT fn=sift_down high=0.00 mid=0.43 low=0.57 role=mid_helper
def sift_down(heap_dist, heap_node, last):
i = 0
while True:
l = i * 2 + 1
r = l + 1
if l > last:
break
m = l
if r <= last and heap_dist[r] < heap_dist[l]:
m = r
if heap_dist[i] <= heap_dist[m]:
break
tmp_dist = heap_dist[i]
heap_dist[i] = heap_dist[m]
heap_dist[m] = tmp_dist
tmp_node = heap_node[i]
heap_node[i] = heap_node[m]
heap_node[m] = tmp_node
i = m
return i
# TRITIUM-PSEUDO fn=dist_init
#| fn dist_init(dist, n, start, inf):
#| fill_list(dist, n, inf)
#| dist[start] = 0
#| return 0
# TRITIUM-HEIGHT fn=dist_init high=0.38 mid=0.12 low=0.50
def dist_init(dist: list[int], n: int, start: int, inf: int) -> int:
fill_list(dist, n, inf)
dist[start] = 0
return 0
# TRITIUM-PSEUDO fn=heap_push
#| fn heap_push(hd, hu, n, d, u):
#| hd[n] = d
#| hu[n] = u
#| sift_up(hd, hu, n)
#| return n + 1
# TRITIUM-HEIGHT fn=heap_push high=0.23 mid=0.15 low=0.61
def heap_push(hd: list[int], hu: list[int], n: int, d: int, u: int) -> int:
hd[n] = d
hu[n] = u
sift_up(hd, hu, n)
return n + 1
# TRITIUM-PSEUDO fn=heap_min_d
#| fn heap_min_d(hd, hu, n):
#| return hd[0]
# TRITIUM-HEIGHT fn=heap_min_d high=0.00 mid=0.00 low=1.00 role=algo_mid
def heap_min_d(hd: list[int], hu: list[int], n: int) -> int:
return hd[0]
# TRITIUM-PSEUDO fn=heap_min_u
#| fn heap_min_u(hd, hu, n):
#| return hu[0]
# TRITIUM-HEIGHT fn=heap_min_u high=0.00 mid=0.00 low=1.00 role=algo_mid
def heap_min_u(hd: list[int], hu: list[int], n: int) -> int:
return hu[0]
# TRITIUM-PSEUDO fn=heap_pop
#| fn heap_pop(hd, hu, n):
#| sift_down(...)
#| return last
# TRITIUM-HEIGHT fn=heap_pop high=0.17 mid=0.17 low=0.67
def heap_pop(hd: list[int], hu: list[int], n: int) -> int:
last = n - 1
hd[0] = hd[last]
hu[0] = hu[last]
sift_down(hd, hu, last - 1)
return last
# TRITIUM-PSEUDO fn=list_get
#| fn list_get(vals, i):
#| return vals[i]
# TRITIUM-HEIGHT fn=list_get high=0.00 mid=0.00 low=1.00 role=algo_mid
def list_get(vals: list[int], i: int) -> int:
return vals[i]
# TRITIUM-PSEUDO fn=stale_visit
#| fn stale_visit(dist, u, d):
#| return int(d > list_get(dist, u))
# TRITIUM-HEIGHT fn=stale_visit high=0.00 mid=0.43 low=0.57
def stale_visit(dist: list[int], u: int, d: int) -> int:
return int(d > list_get(dist, u))
# TRITIUM-PSEUDO fn=relax_edge
#| fn relax_edge(dist, hd, hu, heap_len, u, v, w):
#| new_dist = dist[u] + w
#| if new_dist < dist[v]:
#| dist[v] = new_dist
#| heap_len = heap_push(hd, hu, heap_len, new_dist, v)
#| return heap_len
# TRITIUM-HEIGHT fn=relax_edge high=0.15 mid=0.27 low=0.58 role=algo_mid
def relax_edge(dist: list[int], hd: list[int], hu: list[int], heap_len: int, u: int, v: int, w: int) -> int:
new_dist = dist[u] + w
if new_dist < dist[v]:
dist[v] = new_dist
heap_len = heap_push(hd, hu, heap_len, new_dist, v)
return heap_len
# TRITIUM-PSEUDO fn=edge_relax
#| fn edge_relax(dist, hd, hu, heap_len, dest, weight, e, u):
#| v = list_get(dest, e)
#| w = list_get(weight, e)
#| return relax_edge(dist, hd, hu, heap_len, u, v, w)
# TRITIUM-HEIGHT fn=edge_relax high=0.18 mid=0.21 low=0.61
def edge_relax(dist: list[int], hd: list[int], hu: list[int], heap_len: int, dest: list[int], weight: list[int], e: int, u: int) -> int:
v = list_get(dest, e)
w = list_get(weight, e)
return relax_edge(dist, hd, hu, heap_len, u, v, w)
# TRITIUM-PSEUDO fn=scan_neighbors
#| fn scan_neighbors(dist, hd, hu, heap_len, dest, weight, offsets, u):
#| edge_relax(...)
#| return heap_len
# TRITIUM-HEIGHT fn=scan_neighbors high=0.12 mid=0.23 low=0.65
def scan_neighbors(dist: list[int], hd: list[int], hu: list[int], heap_len: int, dest: list[int], weight: list[int], offsets: list[int], u: int) -> int:
e = list_get(offsets, u)
end = list_get(offsets, u + 1)
while e < end:
heap_len = edge_relax(dist, hd, hu, heap_len, dest, weight, e, u)
e = e + 1
return heap_len
# TRITIUM-PSEUDO fn=dijkstra
#| fn dijkstra(n, offsets, dest, weight, start, dist, hd, hu):
#| dist_init(...)
#| heap_push(...)
#| heap_min_d(...)
#| heap_min_u(...)
#| heap_pop(...)
#| scan_neighbors(...)
#| stale_visit(...)
#| return 0
# TRITIUM-HEIGHT fn=dijkstra high=0.46 mid=0.19 low=0.35
def dijkstra(n: int, offsets: list[int], dest: list[int], weight: list[int], start: int, dist: list[int], hd: list[int], hu: list[int]) -> int:
inf = 1000000000
dist_init(dist, n, start, inf)
heap_len = heap_push(hd, hu, 0, 0, start)
while heap_len > 0:
d = heap_min_d(hd, hu, heap_len)
u = heap_min_u(hd, hu, heap_len)
heap_len = heap_pop(hd, hu, heap_len)
if stale_visit(dist, u, d) == 1:
continue
heap_len = scan_neighbors(dist, hd, hu, heap_len, dest, weight, offsets, u)
return 0