Access to graph created by pegasus_graph not consistent with networkx results

[schnorea]

Description When attempting to create and then access a graph created by pegasus_graph got strange key errors inconsistent with graphs created in networkx alone. Even though the class types appeared to be the same.

To Reproduce I have only run this in one place which is a jovyan notebook. I had just this morning done a pip install dwave-ocean-sdk --upgrade and I restarted the kernel.

Here is the code that I run.

import networkx as nx
import dwave_networkx as dnx
from dwave_networkx.generators.pegasus import pegasus_graph

print ('dwave_networkx',dnx.__version__)
print ('networkx',nx.__version__)

print('Make graph using dwave_networkx pegasus_graph')
G = dnx.pegasus_graph(16, fabric_only=True)

print('graph type =>',type(G))
print('Attempt to access a node')
try:
    print(G[1])
except:
    print("ERROR: caught key error when trying to access node in graph using G[1] format")

print('Create a new networkx graph')
EG = nx.Graph()
print('graph type =>',type(EG))
EG.add_edge(0,1)
print(EG[1])
print("SUCCESS: get expected result when trying to access node in graph using EG[1] format")

Expected behavior I would have expected that when i ran the line print(G[1]) I would have gotten something like this. {0: {},2:{},3:{},...}

Instead when I run I get this.

dwave_networkx 0.8.1
networkx 2.3
Make graph using dwave_networkx pegasus_graph
graph type => <class 'networkx.classes.graph.Graph'>
Attempt to access a node
ERROR: caught key error when trying to access node in graph using G[1] format
Create a new networkx graph
graph type => <class 'networkx.classes.graph.Graph'>
{0: {}}
SUCCESS: get expected result when trying to access node in graph using EG[1] 
format

Environment:

• OS: Docker container of jovyan notebook
• Python version: 3.6.3

Additional context Add any other context about the problem here.

[arcondello]

Hi @schnorea , the problem you're running into comes from the way that we index the Pegasus graph. If you take a look at https://www.dwavesys.com/sites/default/files/14-1026A-C_Next-Generation-Topology-of-DW-Quantum-Processors.pdf, you'll see that there are some nodes on the edges of the graph that are part of disconnected cycles. This includes the node that would be labelled 1. Because in most cases only the main connected body of the graph is useful for computation, we only include that part of the graph by default. You can get that full graph by setting fabric_only=False

>>> G = dnx.pegasus_graph(16, fabric_only=False)
>>> print(1 in G.nodes)
True

However, for that same graph

>>> len(list(nx.connected_components(P16)))
5

Hope this helps!

[arcondello]

Worth noting that NetworkX graphs in general are not necessarily labelled [0,n), e.g.

>>> G = nx.complete_graph(['a', 'b', 'c'])
>>> 0 in G
False
>>> 'a' in G
True

[schnorea]

Yes, i fully understand the labeling thing.

So, I was just unlucky enough to select a node number that didn't exist? Why have indexing that doesn't start at 0 or 1?

Will fabric_only=False and m = 16 faithfully represent a full yield pegasus based machine?

If fabric_only=False and m=16 is the machine of the future it would be useful to have that documented somewhere in the code/docs more explicitly.

[arcondello]

There was a lot of internal debate about the indexing scheme that would make sense. Ultimately we settled on the current scheme because it gives some nice mathematical information and allows easy transformation between the linear index and the "pegasus" and "nice" indexing schemes, see https://github.com/dwavesystems/dwave_networkx/blob/5fba354e8fdd8b7538b747b5367964fab1c9a22a/dwave_networkx/generators/pegasus.py#L447 though also bear in mind that we are in the process of rethinking that part of the API, see #113 .

It is always impossible to guarantee future products, which is why we haven't put strong language in the documentation. That said, m=16 will faithfully generate what, pending an unexpected change, will be our next generation product.

[schnorea]

Thank you. As i have been playing with it I catch glimpses of the method behind the madness. You guys continue to impress.

[ivanksinggih]

Thanks @arcondello. I could not find how to generate a complete Pegasus graph, but your code resolves my issue. Great one! (Hopefully this complete graph code could be included in D-Wave's online documentation somehow.)