Source code for minorminer.utils.diagnostic

# Copyright 2018 D-Wave Systems Inc.
#
#    Licensed under the Apache License, Version 2.0 (the "License");
#    you may not use this file except in compliance with the License.
#    You may obtain a copy of the License at
#
#        http://www.apache.org/licenses/LICENSE-2.0
#
#    Unless required by applicable law or agreed to in writing, software
#    distributed under the License is distributed on an "AS IS" BASIS,
#    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#    See the License for the specific language governing permissions and
#    limitations under the License.
#
# ================================================================================================

import networkx as nx

from minorminer.utils import MissingChainError, ChainOverlapError, \
    DisconnectedChainError, InvalidNodeError, MissingEdgeError

__all__ = ['diagnose_embedding', 'is_valid_embedding', 'verify_embedding']


[docs]def diagnose_embedding(emb, source, target): """Diagnose a minor embedding. Produces a generator that lists all issues with the embedding. User-friendly variants of this function are :func:`is_valid_embedding`, which returns a bool, and :func:`verify_embedding`, which raises the first observed error. Args: 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/:obj:`networkx.Graph`): Graph to be embedded as a NetworkX graph or a list of edges. target (list/:obj:`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 :exc:`.EmbeddingError`. :exc:`.MissingChainError`, snode: a source node label that does not occur as a key of `emb`, or for which emb[snode] is empty. :exc:`.ChainOverlapError`, tnode, snode0, snode1: a target node which occurs in both `emb[snode0]` and `emb[snode1]`. :exc:`.DisconnectedChainError`, snode: a source node label whose chain is not a connected subgraph of `target`. :exc:`.InvalidNodeError`, tnode, snode: a source node label and putative target node label that is not a node of `target`. :exc:`.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: # doctest: +SKIP ... print(problem) (<class 'dwave.embedding.exceptions.InvalidNodeError'>, 1, 'a') (<class 'dwave.embedding.exceptions.ChainOverlapError'>, 2, 2, 0) """ if not hasattr(source, 'edges'): source = nx.Graph(source) if not hasattr(target, 'edges'): target = nx.Graph(target) labels = {} embedded = set() overlaps = set() for x in source: try: embx = emb[x] missing_chain = len(embx) == 0 except KeyError: missing_chain = True if missing_chain: yield MissingChainError, x continue all_present = True for q in embx: if q not in target: all_present = False yield InvalidNodeError, x, q elif x not in labels.setdefault(q, {x}): labels[q].add(x) overlaps.add(q) if all_present: embedded.add(x) if not nx.is_connected(target.subgraph(embx)): yield DisconnectedChainError, x for q in overlaps: nodes = list(labels[q]) root = nodes[0] for x in nodes[1:]: yield ChainOverlapError, q, root, x yielded = nx.Graph() for p, q in target.subgraph(labels).edges(): yielded.add_edges_from((x, y) for x in labels[p] for y in labels[q]) for x, y in source.edges(): if x == y: continue if x in embedded and y in embedded and not yielded.has_edge(x, y): yield MissingEdgeError, x, y
[docs]def is_valid_embedding(emb, source, target): """A simple (bool) diagnostic for minor embeddings. See :func:`diagnose_embedding` for a more detailed diagnostic and more information. Args: 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 (graph or edgelist): Graph to be embedded. target (graph or edgelist): Graph being embedded into. Returns: bool: True if `emb` is valid. """ for _ in diagnose_embedding(emb, source, target): return False return True
[docs]def verify_embedding(emb, source, target, ignore_errors=()): """A simple (exception-raising) diagnostic for minor embeddings. See :func:`diagnose_embedding` for a more detailed diagnostic and more information. Args: 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 (graph or edgelist): Graph to be embedded target (graph or edgelist): Graph being embedded into Raises: EmbeddingError: A catch-all class for the following errors: MissingChainError: A key is missing from `emb` or the associated chain is empty. ChainOverlapError: Two chains contain the same target node. DisconnectedChainError: A chain is disconnected. InvalidNodeError: A chain contains a node label not found in `target`. MissingEdgeError: A source edge is not represented by any target edges. Returns: bool: True if no exception is raised. """ for error in diagnose_embedding(emb, source, target): eclass = error[0] if eclass not in ignore_errors: raise eclass(*error[1:]) return True