examples/fourcolor.py
def embed_with_quotient(source_graph, target_graph, M=16, N=16, L=4, **args):
    """
    Produce an embedding in target_graph suitable to
    check if source_graph is 4-colorable.  More generally,
    if target_graph is a (M,N,L) Chimera subgraph, the
    test is for L-colorability.  This depends heavily upon
    the Chimera structure

    Inputs:
        source_graph, target_graph: networkx graphs
        M,N,L: integers defining the base chimera topology

    Outputs:
        emb: a dictionary mapping (v,i)

    """
    from random import sample
    blocks = list(chimera_blocks(M, N, L))

    BG = chimera_block_quotient(target_graph, blocks)

    ublocks = {block: (block[0][2], i)
               for (i, block) in enumerate(blocks) if BG.has_node(i)}
    source_e = list(source_graph.edges())
    source_n = {x for e in source_e for x in e}
    fabric_e = list(BG.edges())

    # Construct the hints:
    # Goal: each source node must be connected to one horizontal block and one
    #       vertical block (by Chimera structure, each source node will
    #       contain a full (horizontal and vertical) unit cell
    # Construction:
    #   0. for each source node `z`, construct two dummy nodes (z,0) and (z,1)
    #     in both the source and target graphs used by the embedder
    #   1. fix the embedding `(z,u) -> (z,u)` for all dummy nodes
    #   2. for each target block `i` with orientation `u`, and for each source
    #     node `z`, add the target edge `((z,u), i)`
    #   3. for each source node `z` and each orientation `u`, add the source
    #     edge `((z,u), z)`

    fix_chains = {}
    for z in source_n:
        for u in (0, 1):
            source_e.append(((z, u), z))
            fix_chains[z, u] = [(z, u)]
        for u, i in ublocks.values():
            fabric_e.append(((z, u), i))

    # first, grab a few embeddings in the quotient graph. this is super fast
    embs = filter(None, [find_embedding(source_e, fabric_e,
                                        fixed_chains=fix_chains,
                                        chainlength_patience=0,
                                        **args) for _ in range(10)])

    # select the best-looking candidate so far
    emb = min(embs, key=lambda e: sorted((len(c)
                                          for c in e.values()), reverse=True))

    # work down the chainlengths in our embeding
    for _ in range(10):
        emb = find_embedding(source_e, fabric_e,
                             fixed_chains=fix_chains,
                             initial_chains=emb,
                             chainlength_patience=3,
                             skip_initialization=True,
                             **args)

    # next, translate the block-embedding to a qubit-embedding
    newemb = {}
    for v in source_n:
        for k in range(L):
            newemb[v, k] = [blocks[i][k] for i in emb[v]]

    return newemb
def embed_with_quotient(source_graph, target_graph, M=16, N=16, L=4, **args):
    """
    Produce an embedding in target_graph suitable to
    check if source_graph is 4-colorable.  More generally,
    if target_graph is a (M,N,L) Chimera subgraph, the
    test is for L-colorability.  This depends heavily upon
    the Chimera structure

    Inputs:
        source_graph, target_graph: networkx graphs
        M,N,L: integers defining the base chimera topology

    Outputs:
        emb: a dictionary mapping (v,i)

    """
    from random import sample
    blocks = list(chimera_blocks(M, N, L))

    BG = chimera_block_quotient(target_graph, blocks)

    ublocks = {block: (block[0][2], i)
               for (i, block) in enumerate(blocks) if BG.has_node(i)}
    source_e = list(source_graph.edges())
    source_n = {x for e in source_e for x in e}
    fabric_e = list(BG.edges())

    # Construct the hints:
    # Goal: each source node must be connected to one horizontal block and one
    #       vertical block (by Chimera structure, each source node will
    #       contain a full (horizontal and vertical) unit cell
    # Construction:
    #   0. for each source node `z`, construct two dummy nodes (z,0) and (z,1)
    #     in both the source and target graphs used by the embedder
    #   1. fix the embedding `(z,u) -> (z,u)` for all dummy nodes
    #   2. for each target block `i` with orientation `u`, and for each source
    #     node `z`, add the target edge `((z,u), i)`
    #   3. for each source node `z` and each orientation `u`, add the source
    #     edge `((z,u), z)`

    fix_chains = {}
    for z in source_n:
        for u in (0, 1):
            source_e.append(((z, u), z))
            fix_chains[z, u] = [(z, u)]
        for u, i in ublocks.values():
            fabric_e.append(((z, u), i))

    # first, grab a few embeddings in the quotient graph. this is super fast
    embs = filter(None, [find_embedding(source_e, fabric_e,
                                        fixed_chains=fix_chains,
                                        chainlength_patience=0,
                                        **args) for _ in range(10)])

    # select the best-looking candidate so far
    emb = min(embs, key=lambda e: sorted((len(c)
                                          for c in e.values()), reverse=True))

    # work down the chainlengths in our embeding
    for _ in range(10):
        emb = find_embedding(source_e, fabric_e,
                             fixed_chains=fix_chains,
                             initial_chains=emb,
                             chainlength_patience=3,
                             skip_initialization=True,
                             **args)

    # next, translate the block-embedding to a qubit-embedding
    newemb = {}
    for v in source_n:
        for k in range(L):
            newemb[v, k] = [blocks[i][k] for i in emb[v]]

    return newemb
Produce an embedding in target_graph suitable to
    check if source_graph is 4-colorable.  More generally,
    if target_graph is a (M,N,L) Chimera subgraph, the
    test is for L-colorability.  This depends heavily upon
    the Chimera structure

    Inputs:
        source_graph, target_graph: networkx graphs
        M,N,L: integers defining the base chimera topology

    Outputs:
        emb: a dictionary mapping (v,i)