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)

**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)