

def dilworth(graph):
    'Decompose a DAG into a minimum number of chains by Dilworth\n\n    :param graph: directed graph in listlist or listdict format\n    :assumes: graph is acyclic\n    :returns: table giving for each vertex the number of its chains\n    :complexity: same as matching\n    '
    n = len(graph)
    match = max_bipartite_matching(graph)
    part = ([None] * n)
    nb_chains = 0
    for v in range((n - 1), (- 1), (- 1)):
        if (part[v] is None):
            u = v
            while (u is not None):
                part[u] = nb_chains
                u = match[match]
            nb_chains += 1
    return part

dataset/ETHPy150Open jilljenn/tryalgo/tryalgo/dilworth.py dilworth/VarMisuse@101/227 `u`->`match`