adding graph relabeling and sublattice mappings.

[boothby]

I'm making two significant additions in this PR, and I don't expect it to be merged as-is. Happy to make them separate issues (also todo; documentation is incomplete, there are no tests, ~I haven't even checked for obvious typos/omitted imports~). Both are additions to the pegasus_coordinates class. My plan is to repeat this work for Chimera and Zephyr, but I'm pausing here to get some feedback on the interface, and what I'm calling things. Yes please bikeshed this

Graph Converters: I've added three functions to convert graphs from one labeling to another. For example, if you've made a pegasus_graph p with integer labels, but you'd prefer to work with coordinate labels, this saves on boilerplate. What was previously

p = pegasus_graph(m, ...)
coords = pegasus_coordinates(m)
nodes = coords.iter_linear_to_pegasus(p.nodes())
edges = coords.iter_linear_to_pegasus_pairs(p.edges())
p_coord = pegasus_graph(m, node_list = nodes, edge_list = edges)

is now

p = pegasus_graph(m, ...)
coords = pegasus_coordinates(m)
p_coord = coords.graph_to_pegasus(p)

Sublattice Mappings: This adds functionality to make homomorphisms from small Pegasus graphs into large Pegasus graphs. This is broken into two steps: (step 1) generating "offsets" which are used to produce (step 2) mappings from a pegasus_graph(m_small) to pegasus_graph(m_large). We show a barely-contrived use case below; searching for fully-yielded P3 subgraphs:

host_graph = pegasus_graph(m, ...)
host_coords = pegasus_coordinates(m)
mask_graph = pegasus_graph(3)
for offset in host_coords.sublattice_offsets(3):
    mapping = host_coords.sublattice_linear_mapping(3, offset)
    subgraph = host_graph.subgraph(mapping(q) for q in mask_graph)
    if subgraph.number_of_edges() == mask_graph.number_of_edges():
       print("found a fully-yielded P3 graph with offset", offset)

[boothby]

@pau557 @hhtong @jackraymond I think you'll interact with the sublattice mappings the most; @arcondello @randomir I expect you'll have opinions about that and the graph relabeling interface.

[codecov-commenter]

Codecov Report

Merging #211 (9f8611c) into main (e988c71) will increase coverage by 3.79%. The diff coverage is 97.23%.

:exclamation: Current head 9f8611c differs from pull request most recent head eac4b29. Consider uploading reports for the commit eac4b29 to get more accurate results

@@            Coverage Diff             @@
##             main     #211      +/-   ##
==========================================
+ Coverage   71.15%   74.95%   +3.79%     
==========================================
  Files          29       29              
  Lines        1751     2036     +285     
==========================================
+ Hits         1246     1526     +280     
- Misses        505      510       +5     

Impacted Files	Coverage Δ
dwave_networkx/drawing/pegasus_layout.py	17.39% <0.00%> (-0.52%)	:arrow_down:
dwave_networkx/drawing/zephyr_layout.py	19.29% <0.00%> (-1.08%)	:arrow_down:
dwave_networkx/generators/chimera.py	87.43% <100.00%> (+3.86%)	:arrow_up:
dwave_networkx/generators/pegasus.py	90.11% <100.00%> (+2.99%)	:arrow_up:
dwave_networkx/generators/zephyr.py	100.00% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update e988c71...eac4b29. Read the comment docs.

[boothby]

I've been asked to do nice_coordinates for Zephyr, and since I already had this branch going and my head was already deep in coordinate spaces, added that to the scope of this PR and finished the whole thing off. I'm still open to bikeshedding, as long as it's roughly search-and-replace-able.

[jackraymond]

A couple of superficial problems with nice coordinates, might be worth thinking about. How nice do we want nice to be? There are other ways to organize chimera subgraphs without these issues.

Having negative coordinate values in the nice scheme is a little bit awkward to me. This could be addressed by a modification of the cell definition (i.e. having a few x, y values of m, rather than a few x,y values of -1 - pushing awkward boundary conditions to high integers rather than near the origin). Some documentation describes nice_coordinates x and y as limited to the range [0,m), which is inaccurate without greater context.

The nice coordinate scheme indices don't play nice with the visualization tools (draw_zephyr). Variables ordered in x (or y) are not ordered vertically and horizontally in standard visualization. e.g. x=-1 variables are on the interior rather than the boundary. Lots of other nice features that could be ruined in trying to workaround these two issues of course.. Z(m=2,t=1) shows features.

import dwave_networkx as dnx
m = 2
t = 1
graph = dnx.zephyr_graph(m=m,t=t)
graph = coords.graph_to_nice(graph)
dnx.draw_zephyr(graph,with_labels=True)

[boothby]

@jackraymond and I had a sidebar; the outcome is to drop the current proposal for nice_coordinates and use a 4-coordinate Chimera addressing scheme as depicted below (a C_2n embeds directly in to a Z_n, mapping external couplers to odd couplers). I'll take a crack at implementing the interface tomorrow.

[boothby]

After time to digest, I came up with a much simpler interface for sublattice mappings. On a D-Wave internal slack channel, this proved to be a popular option.

def pegasus_sublattice_mappings(source, target):
    """yields mappings from Chimera or Pegasus graphs into Pegasus graphs"""

def chimera_sublattice_mappings(source, target):
    """yields mappings from Chimera graphs into Chimera graphs"""

def zephyr_sublattice_mappings(source, target):
    """yields mappings from Chimera or Zephyr graphs into Zephyr graphs"""

Unable to decide between my original definition of nice_coordinates and the one(s) proposed by Jack, I decided that neither deserves the name "nice". Instead, I've made it easy, through the interface sketched above, to simply generate all sublattice mappings from chimera_graph(m, m, 8) or chimera_graph(2*m, 2*m, 4) to zephyr_graph(m, 8) through the same unified interface:

import dwave_networkx as dnx
from matplotlib import pyplot as plt
c2 = dnx.chimera_graph(2)
z2 = dnx.zephyr_graph(2)
for f in dnx.zephyr_sublattice_mappings(c2, z2):
    plt.figure(figsize=(10,10))
    dnx.draw_zephyr_embedding(z2, {0:[f(v) for v in c2]})
    plt.savefig(f"single{''.join(map(str,f.offset))}.png")
    plt.close()
c28 = dnx.chimera_graph(2, t=8)
z4 = dnx.zephyr_graph(4)
for f in dnx.zephyr_sublattice_mappings(c28, z4):
    plt.figure(figsize=(10,10))
    dnx.draw_zephyr_embedding(z4, {0:[f(v) for v in c28]})
    plt.savefig(f"double{''.join(map(str,f.offset))}.png")
    plt.close()

[boothby]

@arcondello I've rebased & rearranged the deltas to be more cogent

[arcondello]

@boothby , can you rebase one more time to fix the CI issues?

[arcondello]

@jackraymond , are you finished reviewing?