# Source code for tryalgo.dilworth

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Decompose DAG into a minimum number of chains
jill-jenn vie et christoph durr - 2015-2018
"""
from tryalgo.bipartite_matching import max_bipartite_matching
# snip{
[docs]
def dilworth(graph):
"""Decompose a DAG into a minimum number of chains by Dilworth
:param graph: directed graph in listlist or listdict format
:assumes: graph is acyclic
:returns: table giving for each vertex the number of its chains
:complexity: same as matching
"""
n = len(graph)
match = max_bipartite_matching(graph) # maximum matching
part = [None] * n # partition into chains
nb_chains = 0
for v in range(n - 1, -1, -1): # in inverse topological order
if part[v] is None: # start of chain
u = v
while u is not None: # follow the chain
part[u] = nb_chains # mark
u = match[u]
nb_chains += 1
return part
# snip}