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

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! induced.setdefault(M[v],set()).add(v) 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

**pystream**(Download)

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) if rows[r].mask & cols[c].mask & locs] imp = imperfections(graph) mask = 0 forced = []

graph[d].append(unmask[bit]) locs &=~ bit imp = imperfections(graph) for d in imp.keys(): if not imp[d]:

src/p/a/PADS-0.0.20131119/pads/Sudoku.py

**PADS**(Download)

import sys from optparse import OptionParser from BipartiteMatching import imperfections from StrongConnectivity import StronglyConnectedComponents from Repetitivity import NonrepetitiveGraph

graph[d].append(unmask[bit]) locs &=~ bit imp = imperfections(graph) for d in imp.keys(): if not imp[d]: