tritium demo dijkstra
transcript ·
python ·
c ·
rust
/* TRITIUM-PROVENANCE sha256=cecf307e190155d45c2cc7a93a750de16f8670bcbb0f247d9967748079f4e335 lang=c */
/* TRITIUM-HEIGHT high=0.16 mid=0.31 low=0.52 fns=11 */
#include <stdint.h>
#include <math.h>
// TRITIUM-PSEUDO fn=dist_init
//| fn dist_init(dist, n, start, inf):
//| return 0L
// TRITIUM-HEIGHT fn=dist_init high=0.00 mid=0.34 low=0.66
int64_t dist_init(int64_t* dist, int64_t n, int64_t start, int64_t inf) {
int64_t i;
i = 0L;
while (i < n) {
dist[i] = inf;
i = (i + 1L);
}
dist[start] = 0L;
return 0L;
}
// TRITIUM-PSEUDO fn=heap_push
//| fn heap_push(heap_dist, heap_node, n, d, u):
//| return n + 1L
// TRITIUM-HEIGHT fn=heap_push high=0.00 mid=0.33 low=0.67
int64_t heap_push(int64_t* heap_dist, int64_t* heap_node, int64_t n, int64_t d, int64_t u) {
int64_t i;
int64_t parent;
i = n;
heap_dist[i] = d;
heap_node[i] = u;
while (i > 0L) {
parent = (i - 1L) / 2L;
if (heap_dist[i] >= heap_dist[parent]) {
break;
}
int64_t swap = heap_dist[i];
heap_dist[i] = heap_dist[parent];
heap_dist[parent] = swap;
int64_t tmp_node = heap_node[i];
heap_node[i] = heap_node[parent];
heap_node[parent] = tmp_node;
i = parent;
}
return n + 1L;
}
// TRITIUM-PSEUDO fn=heap_min_d
//| fn heap_min_d(heap_dist, heap_node, n):
//| return heap_dist[0L]
// TRITIUM-HEIGHT fn=heap_min_d high=0.00 mid=0.00 low=1.00 role=leaf_charset
int64_t heap_min_d(int64_t* heap_dist, int64_t* heap_node, int64_t n) {
return heap_dist[0L];
}
// TRITIUM-PSEUDO fn=heap_min_u
//| fn heap_min_u(heap_dist, heap_node, n):
//| return heap_node[0L]
// TRITIUM-HEIGHT fn=heap_min_u high=0.00 mid=0.00 low=1.00 role=leaf_charset
int64_t heap_min_u(int64_t* heap_dist, int64_t* heap_node, int64_t n) {
return heap_node[0L];
}
// TRITIUM-PSEUDO fn=heap_pop
//| fn heap_pop(heap_dist, heap_node, n):
//| return n - 1L
// TRITIUM-HEIGHT fn=heap_pop high=0.00 mid=0.42 low=0.58
int64_t heap_pop(int64_t* heap_dist, int64_t* heap_node, int64_t n) {
int64_t i;
int64_t diff;
int64_t sum_2;
int64_t sum;
int64_t i_2;
diff = n - 1L;
heap_dist[0L] = heap_dist[diff];
heap_node[0L] = heap_node[diff];
i = 0L;
diff = (diff - 1L);
while (1) {
sum_2 = (i * 2L) + 1L;
sum = sum_2 + 1L;
if (sum_2 > diff) {
break;
}
i_2 = sum_2;
if (sum <= diff) {
if (heap_dist[sum] < heap_dist[sum_2]) {
i_2 = sum;
}
}
if (heap_dist[i] <= heap_dist[i_2]) {
break;
}
int64_t swap = heap_dist[i];
heap_dist[i] = heap_dist[i_2];
heap_dist[i_2] = swap;
int64_t tmp_node = heap_node[i];
heap_node[i] = heap_node[i_2];
heap_node[i_2] = tmp_node;
i = i_2;
}
return n - 1L;
}
// 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=leaf_charset
int64_t list_get(int64_t* vals, int64_t i) {
return vals[i];
}
// TRITIUM-PSEUDO fn=stale_visit
//| fn stale_visit(dist, u, d):
//| return (d > (list_get(dist, u))) ? 1L : 0L
// TRITIUM-HEIGHT fn=stale_visit high=0.00 mid=1.00 low=0.00 role=leaf_charset
int64_t stale_visit(int64_t* dist, int64_t u, int64_t d) {
return (d > (list_get(dist, u))) ? 1L : 0L;
}
// TRITIUM-PSEUDO fn=relax_edge
//| fn relax_edge(dist, heap_dist, heap_node, heap_len, u, v, w):
//| sum
//| sum = dist[u] + w
//| if (sum < dist[v]) {
//| dist[v] = sum
//| heap_len = heap_push(heap_dist, heap_node, heap_len, sum, v)
//| }
//| return heap_len
// TRITIUM-HEIGHT fn=relax_edge high=0.21 mid=0.38 low=0.41 role=leaf_charset
int64_t relax_edge(int64_t* dist, int64_t* heap_dist, int64_t* heap_node, int64_t heap_len, int64_t u, int64_t v, int64_t w) {
int64_t sum;
sum = dist[u] + w;
if (sum < dist[v]) {
dist[v] = sum;
heap_len = heap_push(heap_dist, heap_node, heap_len, sum, v);
}
return heap_len;
}
// TRITIUM-PSEUDO fn=edge_relax
//| fn edge_relax(dist, heap_dist, heap_node, heap_len, dest, weight, e, u):
//| return relax_edge(dist, heap_dist, heap_node, heap_len, u, list_get(dest, e), list_get(weight, e))
// TRITIUM-HEIGHT fn=edge_relax high=0.67 mid=0.33 low=0.00
int64_t edge_relax(int64_t* dist, int64_t* heap_dist, int64_t* heap_node, int64_t heap_len, int64_t* dest, int64_t* weight, int64_t e, int64_t u) {
return relax_edge(dist, heap_dist, heap_node, heap_len, u, list_get(dest, e), list_get(weight, e));
}
// TRITIUM-PSEUDO fn=scan_neighbors
//| fn scan_neighbors(dist, heap_dist, heap_node, heap_len, dest, weight, offsets, u):
//| edge_relax(...)
//| return heap_len
// TRITIUM-HEIGHT fn=scan_neighbors high=0.27 mid=0.40 low=0.33
int64_t scan_neighbors(int64_t* dist, int64_t* heap_dist, int64_t* heap_node, int64_t heap_len, int64_t* dest, int64_t* weight, int64_t* offsets, int64_t u) {
int64_t idx;
idx = list_get(offsets, u);
while (idx < (list_get(offsets, u + 1L))) {
heap_len = edge_relax(dist, heap_dist, heap_node, heap_len, dest, weight, idx, u);
idx = (idx + 1L);
}
return heap_len;
}
// TRITIUM-PSEUDO fn=dijkstra
//| fn dijkstra(n, offsets, dest, weight, start, dist, heap_dist, heap_node):
//| dist_init(...)
//| heap_push(...)
//| heap_min_u(...)
//| heap_pop(...)
//| stale_visit(...)
//| heap_min_d(...)
//| scan_neighbors(...)
//| return 0L
// TRITIUM-HEIGHT fn=dijkstra high=0.65 mid=0.23 low=0.12
int64_t dijkstra(int64_t n, int64_t* offsets, int64_t* dest, int64_t* weight, int64_t start, int64_t* dist, int64_t* heap_dist, int64_t* heap_node) {
int64_t inf;
int64_t heap_len;
int64_t u;
inf = 1000000000L;
dist_init(dist, n, start, inf);
heap_len = heap_push(heap_dist, heap_node, 0L, 0L, start);
while (heap_len > 0L) {
u = heap_min_u(heap_dist, heap_node, heap_len);
heap_len = heap_pop(heap_dist, heap_node, heap_len);
if (!(((stale_visit(dist, u, heap_min_d(heap_dist, heap_node, heap_len))) == 1L))) {
heap_len = scan_neighbors(dist, heap_dist, heap_node, heap_len, dest, weight, offsets, u);
}
}
return 0L;
}