examples/fourcolor.py
def chimera_block_quotient(G, blocks):
    """
    Extract the blocks from a graph, and returns a
    block-quotient graph according to the acceptability
    functions block_good and eblock_good

    Inputs:
        G: a networkx graph
        blocks: a tuple of tuples

    """
    from networkx import Graph
    from itertools import product

    BG = Graph()
    blockid = {}
    for i, b in enumerate(blocks):
        BG.add_node(i)
        if not b or not all(G.has_node(x) for x in b):
            continue
        for q in b:
            if q in blockid:
                raise(RuntimeError, "two blocks overlap")
            blockid[q] = i

    for q, u in blockid.items():
        ublock = blocks[u]
        for p in G[q]:
            if p not in blockid:
                continue
            v = blockid[p]
            if BG.has_edge(u, v) or u == v:
                continue
            vblock = blocks[v]

            if ublock[0][2] == vblock[0][2]:
                block_edges = zip(ublock, vblock)
            else:
                block_edges = product(ublock, vblock)

            if all(G.has_edge(x, y) for x, y in block_edges):
                BG.add_edge(u, v)

    return BG
def chimera_block_quotient(G, blocks):
    from networkx import Graph
    from itertools import product

    BG = Graph()
    blockid = {}
    for i, b in enumerate(blocks):
        BG.add_node(i)
        if not b or not all(G.has_node(x) for x in b):
            continue
        for q in b:
            if q in blockid:
                raise(RuntimeError, "two blocks overlap")
            blockid[q] = i

    for q, u in blockid.items():
        ublock = blocks[u]
        for p in G[q]:
            if p not in blockid:
                continue
            v = blockid[p]
            if BG.has_edge(u, v) or u == v:
                continue
            vblock = blocks[v]

            if ublock[0][2] == vblock[0][2]:
                block_edges = zip(ublock, vblock)
            else:
                block_edges = product(ublock, vblock)

            if all(G.has_edge(x, y) for x, y in block_edges):
                BG.add_edge(u, v)

    return BG
def chimera_block_quotient ( G , blocks ) : from networkx import Graph from itertools import product BG = Graph ( ) blockid = { } for i , b in enumerate ( blocks ) : BG . add_node ( i ) if not b or not all ( G . has_node ( x ) for x in b ) : continue for q in b : if q in blockid : raise ( RuntimeError , "two blocks overlap" ) blockid [ q ] = i for q , u in blockid . items ( ) : ublock = blocks [ u ] for p in G [ q ] : if p not in blockid : continue v = blockid [ p ] if BG . has_edge ( u , v ) or u == v : continue vblock = blocks [ v ] if ublock [ 0 ] [ 2 ] == vblock [ 0 ] [ 2 ] : block_edges = zip ( ublock , vblock ) else : block_edges = product ( ublock , vblock ) if all ( G . has_edge ( x , y ) for x , y in block_edges ) : BG . add_edge ( u , v ) return BG
Extract the blocks from a graph, and returns a
    block-quotient graph according to the acceptability
    functions block_good and eblock_good

    Inputs:
        G: a networkx graph
        blocks: a tuple of tuples
Extract the blocks from a graph and returns a block - quotient graph according to the acceptability functions block_good and eblock_good