add explicit verify_embedding function

[aidanproy]

Something like:

def verify_embedding(G_edges, A_edges, emb):
# verify that emb is valid embedding of graph G in graph A
# this function should have the same input/output format as embedding functions
# Here, emb is a list of lists and G/A are lists of edges.

# make G,A networkx graphs.
A = nx.Graph(A_edges)
G = nx.Graph(G_edges)
n = len(A)
m = len(G)

if m != len(emb):
    print 'Invalid: dimension mismatch.\n'
    return False

# make sure chains don't overlap
inti = [-1]*n
for i in range(len(emb)):
    for k in emb[i]:
        if inti[k] != -1:
            print 'Invalid: vertices %d and %d overlap\n' % (inti[k], i)
            return False
        inti[k] = i


# make sure chains aren't mapping on to nonworking qubits
working = [False]*n
for e in A.edges:
    working[e[0]] = True
    working[e[1]] = True
for i in range(len(emb)):
    for k in emb[i]:
        if not(working[k]):
            print 'Invalid: vertices mapped onto non-working qubit\n'
            return False

# check whether a target node is mapped to a connected component.
used = [False] * m
for e in G.edges:
    used[e[0]] = True
    used[e[1]] = True
for i in range(len(emb)):
    # empty is ok if that variable is not used
    if emb[i]==[] and used[i]:
        print 'Invalid: vertex %d is empty\n' % 0
        return False

    # get components:
    Gc = A.subgraph(emb[i])
    if nx.number_connected_components(Gc) != 1:
        print('Invalid: vertex %d is not connected\n' % i)
        return False

# check edges
for e in G.edges:
    x, y = e
    Gc = A.subgraph(emb[x]+emb[y])
    if nx.number_connected_components(Gc) != 1:
        print 'Invalid: edge %d %d is not covered\n' % (x,y)
        return False

return True