diagnose_embedding(emb, source, target)[source]#

Diagnose a minor embedding.

Produces a generator that lists all issues with the embedding. User-friendly variants of this function are is_valid_embedding(), which returns a bool, and verify_embedding(), which raises the first observed error.

  • emb (dict) – A mapping of source nodes to arrays of target nodes as a dict of form {s: [t, …], …}, where s is a source-graph variable and t is a target-graph variable.

  • source (list/networkx.Graph) – Graph to be embedded as a NetworkX graph or a list of edges.

  • target (list/networkx.Graph) – Graph being embedded into as a NetworkX graph or a list of edges.


Errors yielded in the form ExceptionClass, arg1, arg2,…, where the arguments following the class are used to construct the exception object, which are subclasses of EmbeddingError.

MissingChainError, snode: a source node label that does not occur as a key of emb, or for which emb[snode] is empty.

ChainOverlapError, tnode, snode0, snode1: a target node which occurs in both emb[snode0] and emb[snode1].

DisconnectedChainError, snode: a source node label whose chain is not a connected subgraph of target.

InvalidNodeError, tnode, snode: a source node label and putative target node label that is not a node of target.

MissingEdgeError, snode0, snode1: a pair of source node labels defining an edge that is not present between their chains.


This example diagnoses an invalid embedding from a triangular source graph to a square target graph. A valid embedding, such as emb = {0: [1], 1: [0], 2: [2, 3]}, yields no errors.

>>> from dwave.embedding import diagnose_embedding
>>> import networkx as nx
>>> source = nx.complete_graph(3)
>>> target = nx.cycle_graph(4)
>>> embedding = {0: [2], 1: [1, 'a'], 2: [2, 3]}
>>> diagnosis = diagnose_embedding(embedding, source, target)
>>> for problem in diagnosis:  
...     print(problem)
(<class 'dwave.embedding.exceptions.InvalidNodeError'>, 1, 'a')
(<class 'dwave.embedding.exceptions.ChainOverlapError'>, 2, 2, 0)