lib/algo/legacy/topo.viv

# Generated by tools/algo/legacy.py from the corpus: do not edit.
# TheAlgorithms' Kahn topological sort (graphs.viv), with the helpers it calls.
# Element comparisons are routed through lib/algo/legacy/order.viv; nothing else changes.
from algo.legacy.order import lg_eq
from algo.legacy.seq_argsort import seq_argsort

# from study/idioms/thealgorithms-python/graphs.viv: row_offsets by_source index_of topological_sort

#| off[v] is where v's neighbors start in the sorted edge list; off[n] is the edge count.
def row_offsets(n, src: Arr) -> Arr {
    off = zeros(n + 1.0)
    for e to len(src) {
        off[src[e] + 1.0] += 1.0
    }
    for v to n {
        off[v + 1.0] += off[v]
    }
    return off
}

#| The edges grouped by source, each group in insertion order (argsort is stable).
def by_source(src: Arr) -> Arr {
    return seq_argsort(src)
}

#| Where k sits in keys, or -1 (a dict lookup, by linear search).
def index_of(keys: Arr, k) {
    for i to len(keys) {
        if lg_eq(keys[i], k) {
            return i
        }
    }
    return -1.0
}

#| graphs/kahns_algorithm_topo.py. The graph is a dict in Python: `keys` lists its keys
#| in insertion order and edge e goes from key src[e] to key dst[e]. Returns the keys in
#| topological order, or an empty array where Python returns None (a cycle).
def topological_sort(keys: Arr, src_keys: Arr, dst_keys: Arr) -> Arr {
    n = len(keys)
    src = zeros(len(src_keys))
    dst = zeros(len(dst_keys))
    for e to len(src) {
        src[e] = index_of(keys, src_keys[e])
        dst[e] = index_of(keys, dst_keys[e])
    }
    order = by_source(src)
    off = row_offsets(n, src)
    nbr = take(dst, order)
    indegree = zeros(n)
    for e to len(dst) {
        indegree[dst[e]] += 1.0
    }
    queue = zeros(n)
    head = 0.0
    tail = 0.0
    for v to n {
        if indegree[v] == 0.0 {
            queue[tail] = v
            tail += 1.0
        }
    }
    topo = zeros(n)
    processed = 0.0
    while head < tail {
        vertex = queue[head]
        head += 1.0
        topo[processed] = keys[vertex]
        processed += 1.0
        for k to off[vertex + 1.0] - off[vertex] {
            neighbor = nbr[off[vertex] + k]
            indegree[neighbor] -= 1.0
            if indegree[neighbor] == 0.0 {
                queue[tail] = neighbor
                tail += 1.0
            }
        }
    }
    if processed != n {
        return zeros(0.0)
    }
    return topo
}