# Path: tryalgo/bipartite_matching.py
# def max_bipartite_matching(bigraph):
#     """Bipartie maximum matching
# 
#     :param bigraph: adjacency list, index = vertex in U,
#                                     value = neighbor list in V
#     :assumption: U = V = {0, 1, 2, ..., n - 1} for n = len(bigraph)
#     :returns: matching list, match[v] == u iff (u, v) in matching
#     :complexity: `O(|V|*|E|)`
#     """
#     n = len(bigraph)               # same domain for U and V
#     match = [None] * n
#     for u in range(n):
#         augment(u, bigraph, [False] * n, match)
#     return match


from tryalgo.bipartite_matching import max_bipartite_matching
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Decompose DAG into a minimum number of chains
jill-jenn vie et christoph durr - 2015-2018
"""



# snip{
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)

# Path: tryalgo/bipartite_matching.py
# def max_bipartite_matching(bigraph):
#     """Bipartie maximum matching
# 
#     :param bigraph: adjacency list, index = vertex in U,
#                                     value = neighbor list in V
#     :assumption: U = V = {0, 1, 2, ..., n - 1} for n = len(bigraph)
#     :returns: matching list, match[v] == u iff (u, v) in matching
#     :complexity: `O(|V|*|E|)`
#     """
#     n = len(bigraph)               # same domain for U and V
#     match = [None] * n
#     for u in range(n):
#         augment(u, bigraph, [False] * n, match)
#     return match


# Path: tryalgo/dilworth.py
from tryalgo.bipartite_matching import max_bipartite_matching

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Decompose DAG into a minimum number of chains
jill-jenn vie et christoph durr - 2015-2018
"""



# snip{
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