dwave.embedding.target_to_source

target_to_source(target_adjacency, embedding)

Derive the source adjacency from an embedding and target adjacency.

Parameters:

• target_adjacency (dict/networkx.Graph) – Target adjacency as a dict of form {v: Nv, ...} where v is a node in the target graph and Nv is the neighbors of v as an iterable; or a NetworkX graph.

• embedding (dict) – Mapping from a source graph to a target graph.

Returns:

Adjacency of the source graph.

Return type:

dict

Raises:

ValueError – If any node in the target_adjacency is assigned more than one node in the source graph by embedding.

Examples

>>> from dwave.embedding import target_to_source
...
>>> target_adjacency = {0: {1, 3}, 1: {0, 2}, 2: {1, 3}, 3: {0, 2}}  # a square graph
>>> embedding = {'a': {0}, 'b': {1}, 'c': {2, 3}}
>>> source_adjacency = target_to_source(target_adjacency, embedding)
>>> source_adjacency == {'a': {'b', 'c'}, 'b': {'a', 'c'}, 'c': {'a', 'b'}}
True

This example inputs a NetworkX graph.

>>> import networkx as nx
...
>>> target_graph = nx.complete_graph(5)
>>> embedding = {'a': {0, 1, 2}, 'b': {3, 4}}
>>> target_to_source(target_graph, embedding)
{'a': {'b'}, 'b': {'a'}}