zad1.py

from checker import chordal_checker
from lexBFS import lexBFS, Node, gen_nodes_list

def chordal_check(V, L):
    G = gen_nodes_list(V, L)
    G : list[Node]
    order = lexBFS(G, V)
    og_idx_to_order = [None] * (V + 1)
    for i in range(V):
        og_idx_to_order[order[i]] = i

    RN = [set() for _ in range(V + 1)]
    parent = [None] * (V + 1)

    for i in range(1, V): # nie ma sensu sprawdzać pierwszego elementu order, bo wszystko puste
        v = order[i]
        last_idx = -1
        for u in G[v].out:
            u_idx = og_idx_to_order[u]
            if u_idx < i:
                RN[v].add(u)
                if u_idx > last_idx:
                    last_idx = u_idx
                
        parent[v] = order[last_idx] if last_idx != -1 else None

        if parent[v] is not None and not (RN[v] - {parent[v]} <= RN[parent[v]]):
            return False

    return True


chordal_checker(chordal_check)