dwave.embedding.diagnose_embedding#

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.

Parameters:

  • 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.

Yields:

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.

Examples

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)