Did I find the right examples for you? yes no      Crawl my project      Python Jobs

All Samples(4)  |  Call(4)  |  Derive(0)  |  Import(0)
Find maximum cardinality matching of a bipartite graph (U,V,E).
The input format is a dictionary mapping members of U to lists
of their neighbors in V.  The output is a triple (M,A,B) where M is a
dictionary mapping members of V to their matches in U, A is the part
of the maximum independent set in U, and B is the part of the MIS in V.
The same object may occur in both U and V, and is treated as two
distinct vertices if this happens.

        def matching(graph):
    """
    Find maximum cardinality matching of a bipartite graph (U,V,E).
    The input format is a dictionary mapping members of U to lists
    of their neighbors in V.  The output is a triple (M,A,B) where M is a
    dictionary mapping members of V to their matches in U, A is the part
    of the maximum independent set in U, and B is the part of the MIS in V.
    The same object may occur in both U and V, and is treated as two
    distinct vertices if this happens.
    """

    # initialize greedy matching (redundant, but faster than full search)
    matching = {}
    for u in graph:
        for v in graph[u]:
            if v not in matching:
                matching[v] = u
                break

    while True:
        # structure residual graph into layers
        # pred[u] gives the neighbor in the previous layer for u in U
        # preds[v] gives a list of neighbors in the previous layer for v in V
        # unmatched gives a list of unmatched vertices in final layer of V,
        # and is also used as a flag value for pred[u] when u is in the first layer
        preds = {}
        unmatched = []
        pred = {u:unmatched for u in graph}
        for v in matching:
            del pred[matching[v]]
        layer = list(pred)

        # repeatedly extend layering structure by another pair of layers
        while layer and not unmatched:
            newLayer = {}
            for u in layer:
                for v in graph[u]:
                    if v not in preds:
                        newLayer.setdefault(v,[]).append(u)
            layer = []
            for v in newLayer:
                preds[v] = newLayer[v]
                if v in matching:
                    layer.append(matching[v])
                    pred[matching[v]] = v
                else:
                    unmatched.append(v)

        # did we finish layering without finding any alternating paths?
        if not unmatched:
            unlayered = {}
            for u in graph:
                for v in graph[u]:
                    if v not in preds:
                        unlayered[v] = None
            return (matching,list(pred),list(unlayered))

        # recursively search backward through layers to find alternating paths
        # recursion returns true if found path, false otherwise
        def recurse(v):
            if v in preds:
                L = preds[v]
                del preds[v]
                for u in L:
                    if u in pred:
                        pu = pred[u]
                        del pred[u]
                        if pu is unmatched or recurse(pu):
                            matching[v] = u
                            return True
            return False

        for v in unmatched: recurse(v)
        


src/p/y/pystream-HEAD/lib/PADS/PartialOrder.py   pystream(Download)
def MinimumPathDecomposition(G):
    """
    Cover a directed acyclic graph with a minimum number of paths.
    """
    M,A,B = BipartiteMatching.matching(G)
        raise ValueError("MaximumAntichain: input is not acyclic.")
    TC = TransitiveClosure(G)
    M,A,B = BipartiteMatching.matching(TransitiveClosure(G))
    return set(A).intersection(B)
 

src/p/a/PADS-0.0.20131119/pads/PartialOrder.py   PADS(Download)
def MinimumPathDecomposition(G):
    """
    Cover a directed acyclic graph with a minimum number of paths.
    """
    M,A,B = BipartiteMatching.matching(G)
        raise ValueError("MaximumAntichain: input is not acyclic.")
    TC = TransitiveClosure(G)
    M,A,B = BipartiteMatching.matching(TransitiveClosure(G))
    return set(A).intersection(B)