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

# BipartiteMatching.imperfections

All Samples(5)  |  Call(3)  |  Derive(0)  |  Import(2)
Find edges that do not belong to any perfect matching of G.
The input format is the same as for matching(), and the output
is a subgraph of the input graph in the same format.

For each edge v->w in the output subgraph, imperfections[v][w]
is itself a subgraph of the input, induced by a set of
vertices that must be matched to each other, including w but
not including v.

def imperfections(graph):
"""
Find edges that do not belong to any perfect matching of G.
The input format is the same as for matching(), and the output
is a subgraph of the input graph in the same format.

For each edge v->w in the output subgraph, imperfections[v][w]
is itself a subgraph of the input, induced by a set of
vertices that must be matched to each other, including w but
not including v.
"""
M,A,B = matching(graph)
if len(M) != len(graph):
return graph    # whole graph is imperfect

orientation = {}
for v in graph:
orientation[v,True]=[]
for w in graph[v]:
if M[w] == v:
orientation[w,False]=[(v,True)]
else:
orientation[v,True].append((w,False))

components = {}
for C in StronglyConnectedComponents(orientation):
induced = {v:{w for w,bit2 in C[v,bit]} for v,bit in C if bit}
for v,bit in C:
if not bit:   # don't forget the matched edges!
for v in C:
components[v] = induced

imperfections = {}
for v in graph:
imperfections[v] = {w:components[w,False] for w in graph[v]
if M[w] != v and
components[v,True] != components[w,False]}

return imperfections

import sys
from optparse import OptionParser
from BipartiteMatching import imperfections
from StrongConnectivity import StronglyConnectedComponents
from Repetitivity import NonrepetitiveGraph
graph[r] = [c for c in range(9)
imp = imperfections(graph)
forced = []
locs &=~ bit
imp = imperfections(graph)
for d in imp.keys():
if not imp[d]: