074_topological_sort.sio

//@ run-pass
// HumanEval 074: Topological Sort (Kahn's Algorithm)
//
// Given a directed acyclic graph (DAG) with n nodes and edge list,
// produce a topological ordering. Uses Kahn's algorithm: repeatedly
// remove nodes with in-degree 0 and append to result.
// Returns the number of nodes in the result (less than n means cycle).

struct Buf { data: [i64; 256] }

fn topo_sort(n: i64, edges_from: [i64; 256], edges_to: [i64; 256], num_edges: i64, out: &!Buf) -> i64 with Mut, Panic {
    // Compute in-degrees
    var in_deg: [i64; 256] = [0; 256]
    var i: i64 = 0
    while i < num_edges {
        let to = edges_to[i]
        in_deg[to] = in_deg[to] + 1
        i = i + 1
    }

    // Queue of nodes with in-degree 0
    var queue: [i64; 256] = [0; 256]
    var q_front: i64 = 0
    var q_back: i64 = 0

    var v: i64 = 0
    while v < n {
        if in_deg[v] == 0 {
            queue[q_back] = v
            q_back = q_back + 1
        }
        v = v + 1
    }

    var out_len: i64 = 0

    while q_front < q_back {
        let node = queue[q_front]
        q_front = q_front + 1

        out.data[out_len] = node
        out_len = out_len + 1

        // Decrement in-degree of neighbors
        var e: i64 = 0
        while e < num_edges {
            if edges_from[e] == node {
                let neighbor = edges_to[e]
                in_deg[neighbor] = in_deg[neighbor] - 1
                if in_deg[neighbor] == 0 {
                    queue[q_back] = neighbor
                    q_back = q_back + 1
                }
            }
            e = e + 1
        }
    }

    out_len
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: Linear chain 0->1->2->3
    var ef1: [i64; 256] = [0; 256]
    var et1: [i64; 256] = [0; 256]
    ef1[0] = 0
    et1[0] = 1
    ef1[1] = 1
    et1[1] = 2
    ef1[2] = 2
    et1[2] = 3
    var o1 = Buf { data: [0; 256] }
    let n1 = topo_sort(4, ef1, et1, 3, &!o1)
    assert(n1 == 4)
    assert(o1.data[0] == 0)
    assert(o1.data[1] == 1)
    assert(o1.data[2] == 2)
    assert(o1.data[3] == 3)

    // Test 2: Diamond DAG: 0->{1,2}, 1->3, 2->3
    var ef2: [i64; 256] = [0; 256]
    var et2: [i64; 256] = [0; 256]
    ef2[0] = 0
    et2[0] = 1
    ef2[1] = 0
    et2[1] = 2
    ef2[2] = 1
    et2[2] = 3
    ef2[3] = 2
    et2[3] = 3
    var o2 = Buf { data: [0; 256] }
    let n2 = topo_sort(4, ef2, et2, 4, &!o2)
    assert(n2 == 4)
    // 0 must be first, 3 must be last
    assert(o2.data[0] == 0)
    assert(o2.data[3] == 3)

    // Test 3: No edges (5 independent nodes)
    var ef3: [i64; 256] = [0; 256]
    var et3: [i64; 256] = [0; 256]
    var o3 = Buf { data: [0; 256] }
    let n3 = topo_sort(5, ef3, et3, 0, &!o3)
    assert(n3 == 5)

    // Test 4: Single node
    var ef4: [i64; 256] = [0; 256]
    var et4: [i64; 256] = [0; 256]
    var o4 = Buf { data: [0; 256] }
    let n4 = topo_sort(1, ef4, et4, 0, &!o4)
    assert(n4 == 1)
    assert(o4.data[0] == 0)

    // Test 5: Wider DAG: 0->2, 1->2, 2->3, 2->4
    var ef5: [i64; 256] = [0; 256]
    var et5: [i64; 256] = [0; 256]
    ef5[0] = 0
    et5[0] = 2
    ef5[1] = 1
    et5[1] = 2
    ef5[2] = 2
    et5[2] = 3
    ef5[3] = 2
    et5[3] = 4
    var o5 = Buf { data: [0; 256] }
    let n5 = topo_sort(5, ef5, et5, 4, &!o5)
    assert(n5 == 5)
    // 0 and 1 before 2, 2 before 3 and 4

    // Verify ordering constraints
    var pos0: i64 = 0
    var pos1: i64 = 0
    var pos2: i64 = 0
    var pos3: i64 = 0
    var pos4: i64 = 0
    var k: i64 = 0
    while k < 5 {
        if o5.data[k] == 0 { pos0 = k }
        if o5.data[k] == 1 { pos1 = k }
        if o5.data[k] == 2 { pos2 = k }
        if o5.data[k] == 3 { pos3 = k }
        if o5.data[k] == 4 { pos4 = k }
        k = k + 1
    }
    assert(pos0 < pos2)
    assert(pos1 < pos2)
    assert(pos2 < pos3)
    assert(pos2 < pos4)

    println("074_topological_sort: ALL TESTS PASSED")
    0
}