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
        


src/p/y/pystream-HEAD/lib/PADS/Sudoku.py   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]: