Improve documentation of `all_pairs_all_simple_paths` with example on how to consume all paths

[dcmckayibm]

Information

• rustworkx version: 0.15.1
• Python version: 3.10
• Rust version: Pip installed rustworkx (N/A)
• Operating system: MacOS

What is the current behavior?

When comparison all_pairs_all_simple_paths to a brute force search of paths there is a discrepancy

What is the expected behavior?

Steps to reproduce the problem

Code from Oliver (I'll ask him to post)

[dcmckayibm]

Some code to test

This builds the graphs

import networkx as nx
import rustworkx as rx

path_len = 10
path_cnt = 0
path_cnt2 = 0
cutoff=30
if True: # pre-stored coupling map so we don't have to use Qiskit
    cpling = [[0, 1], [0, 15], [1, 0], [1, 2], [2, 1], [2, 3], [3, 2], [3, 4], [4, 3],
             [4, 5], [4, 16], [5, 4], [5, 6], [6, 5], [6, 7], [7, 6], [7, 8], [8, 7],
             [8, 9], [8, 17], [9, 8], [9, 10], [10, 9], [10, 11], [11, 10], [11, 12],
             [12, 11], [12, 13], [12, 18], [13, 12], [13, 14], [14, 13], [15, 0],
             [15, 19], [16, 4], [16, 23], [17, 8], [17, 27], [18, 12], [19, 15],
             [19, 20], [20, 19], [20, 21], [21, 20], [21, 22], [22, 21], [22, 23],
             [23, 16], [23, 22], [23, 24], [24, 23], [24, 25], [25, 24], [25, 26],
             [26, 25], [26, 27], [27, 17], [27, 26], [27, 28], [28, 27], [28, 29], [29, 28]]
else:
    import qiskit
    from qiskit.transpiler import CouplingMap
    from qiskit_ibm_runtime import QiskitRuntimeService
    service = QiskitRuntimeService()
    backend = service.backend("ibm_torino")
    cpling = backend.configuration().coupling_map
    cpling = [c for c in cpling if c[0] < 30 and c[1] < 30]
cpling = list(set([tuple(sorted(c)) for c in cpling]))

my_graph_nx = nx.DiGraph()
my_graph_rx = rx.PyGraph()
nodes = set()
nodes = [e[0] for e in cpling] + [e[1] for e in cpling]
nodes = list(set(nodes))
nodes.sort()
#print(len(nodes))
node_map={} # in practice this map is an identity map because of sorting
for node in nodes:
    my_graph_nx.add_node(node)
    node_map[node] = my_graph_rx.add_node(node)
    
for edge in cpling:
    my_graph_nx.add_edge(edge[0],edge[1],weight=1.0)
    my_graph_rx.add_edge(node_map[edge[0]],node_map[edge[1]],1.0)
    my_graph_nx.add_edge(edge[1],edge[0],weight=1.0)
    my_graph_rx.add_edge(node_map[edge[1]],node_map[edge[0]],1.0)  

This shows that the networkx implementation and rustworkx implementation give different results

def path_iterator(paths):
    """
    Turn paths into an iterator
    This actually doesn't help with the paths.values returned by
    rx.all_pairs_all_simple_paths. It simplifies the logic of
    calculate_best_paths
    """
    for node_path in paths.values():
        for path in node_path.values():
            yield path[0]
paths = rx.all_pairs_all_simple_paths(my_graph_rx, min_depth=path_len, cutoff=path_len) 

paths_rx=list(path_iterator(paths))
paths_nx=[]
for i in nodes:
    for j in nodes:
        if i==j:
            continue
        paths_gen = nx.all_simple_paths(my_graph_nx,i,j,path_len)
        for path in paths_gen:
            if len(path)==path_len:
                paths_nx.append(path)
                path_cnt2+=1
        
paths_rx = [list(p) for p in paths_rx]
print(f'RWX: {len(paths_rx)}, NWX:{len(paths_nx)}')

[IvanIsCoding]

I'll stop you right at:

my_graph_nx = nx.DiGraph()
my_graph_rx = rx.PyGraph()

For Networkx, you are creating a directed graph. For rustworkx, you are creating an undirected graph. So you are comparing the simple paths of two very different graphs!

Try swaping my_graph_rx = rx.PyDiGraph() and report back if the paths are different

[dcmckayibm]

I guess I should have put more of the code down

# Compare the graphs...
for edge in my_graph_nx.edges():
    if not my_graph_rx.has_edge(node_map[edge[0]],node_map[edge[1]]):
        print('Missing edge in rustworkx: ', edge)
# Compare the graphs...
for edge in my_graph_rx.edge_list():
    if not my_graph_nx.has_edge(node_map[edge[0]],node_map[edge[1]]):
        print('Missing edge in networkx: ', edge)
if len(list(my_graph_nx.edges())) != len(my_graph_rx.edge_list()):
    print("Graphs have different numbers of edges")
    print(len(list(my_graph_nx.edges())),len(my_graph_rx.edge_list()))

for path in paths_rx:
    if path not in paths_nx:
        print(f"Not in networkx: {path}")
for ind, path in enumerate(paths_nx):
    path = list(path)
    if path not in paths_rx:
        print(f"Not in rustworkx #{ind}: {path}")
        if list(reversed(path)) not in paths_rx:
            print("Reversed path not present")

[dcmckayibm]

but I did just try it replacing with your suggestion and it was the same. For example the last block of code spits out this

Not in rustworkx 5: [0, 1, 2, 3, 4, 16, 23, 24, 25, 26] Not in rustworkx 11: [1, 2, 3, 4, 5, 6, 7, 8, 17, 27] Not in rustworkx 19: [2, 3, 4, 5, 6, 7, 8, 17, 27, 28] Not in rustworkx 26: [3, 4, 5, 6, 7, 8, 17, 27, 28, 29] Not in rustworkx 48: [7, 6, 5, 4, 3, 2, 1, 0, 15, 19] Not in rustworkx 55: [8, 17, 27, 26, 25, 24, 23, 22, 21, 20] Reversed path not present Not in rustworkx 60: [9, 8, 17, 27, 26, 25, 24, 23, 22, 21] Reversed path not present Not in rustworkx 65: [10, 9, 8, 17, 27, 26, 25, 24, 23, 22] Reversed path not present Not in rustworkx 69: [11, 10, 9, 8, 17, 27, 26, 25, 24, 23] Reversed path not present Not in rustworkx 103: [19, 20, 21, 22, 23, 16, 4, 5, 6, 7] Not in rustworkx 111: [20, 21, 22, 23, 24, 25, 26, 27, 17, 8] Reversed path not present Not in rustworkx 117: [21, 22, 23, 24, 25, 26, 27, 17, 8, 9] Reversed path not present Not in rustworkx 124: [22, 23, 24, 25, 26, 27, 17, 8, 9, 10] Reversed path not present Not in rustworkx 130: [23, 24, 25, 26, 27, 17, 8, 9, 10, 11] Reversed path not present Not in rustworkx 149: [26, 25, 24, 23, 22, 21, 20, 19, 15, 0] Not in rustworkx 155: [27, 26, 25, 24, 23, 16, 4, 3, 2, 1] Not in rustworkx 161: [28, 27, 26, 25, 24, 23, 16, 4, 3, 2] Not in rustworkx 167: [29, 28, 27, 26, 25, 24, 23, 16, 4, 3]

[oliverdial]

It's worth noting I added the edges in both directions on the DiGraph because yes, I'm aware it's directional (I was trying to minimally change some other code which is how it ended up in this odd state)

[IvanIsCoding]

So, I found the issue in the code with the reported bug. There is a big assumption yield path[0] that the path list only contains one element. I added an assert len(path) == 1 and it failed, which prompted me to tweak the code to.

I tweaked the first part just to match the graph type. Both NetworkX and rustworkx are using undirected graphs for simplicity:

import networkx as nx
import rustworkx as rx

path_len = 10
path_cnt = 0
path_cnt2 = 0
cutoff=30
if True: # pre-stored coupling map so we don't have to use Qiskit
    cpling = [[0, 1], [0, 15], [1, 0], [1, 2], [2, 1], [2, 3], [3, 2], [3, 4], [4, 3],
             [4, 5], [4, 16], [5, 4], [5, 6], [6, 5], [6, 7], [7, 6], [7, 8], [8, 7],
             [8, 9], [8, 17], [9, 8], [9, 10], [10, 9], [10, 11], [11, 10], [11, 12],
             [12, 11], [12, 13], [12, 18], [13, 12], [13, 14], [14, 13], [15, 0],
             [15, 19], [16, 4], [16, 23], [17, 8], [17, 27], [18, 12], [19, 15],
             [19, 20], [20, 19], [20, 21], [21, 20], [21, 22], [22, 21], [22, 23],
             [23, 16], [23, 22], [23, 24], [24, 23], [24, 25], [25, 24], [25, 26],
             [26, 25], [26, 27], [27, 17], [27, 26], [27, 28], [28, 27], [28, 29], [29, 28]]
cpling = list(set([tuple(sorted(c)) for c in cpling]))

my_graph_nx = nx.Graph()
my_graph_rx = rx.PyGraph()
nodes = set()
nodes = [e[0] for e in cpling] + [e[1] for e in cpling]
nodes = list(set(nodes))
nodes.sort()

node_map={} # in practice this map is an identity map because of sorting
for node in nodes:
    my_graph_nx.add_node(node)
    node_map[node] = my_graph_rx.add_node(node)
    
for edge in cpling:
    my_graph_nx.add_edge(edge[0],edge[1],weight=1.0)
    my_graph_rx.add_edge(node_map[edge[0]],node_map[edge[1]],1.0)

Then, we have the tweaked path iterator:

def path_iterator(paths):
    """
    Turn paths into an iterator
    This actually doesn't help with the paths.values returned by
    rx.all_pairs_all_simple_paths. It simplifies the logic of
    calculate_best_paths
    """
    for node_path in paths.values():
        for path in node_path.values():
            for v in path:
              yield v
paths = rx.all_pairs_all_simple_paths(my_graph_rx, min_depth=path_len, cutoff=path_len) 

paths_rx=list(path_iterator(paths))
paths_nx=[]
for i in nodes:
    for j in nodes:
        if i==j:
            continue
        paths_gen = nx.all_simple_paths(my_graph_nx,i,j,path_len)
        for path in paths_gen:
            if len(path)==path_len:
                paths_nx.append(path)
                path_cnt2+=1
        
paths_rx = [list(p) for p in paths_rx]
print(f'RWX: {len(paths_rx)}, NWX:{len(paths_nx)}')

That version of the code outputs:

RWX: 174, NWX:174

[IvanIsCoding]

I also ran the additional snippet:

for path in paths_rx:
    if path not in paths_nx:
        print(f"Not in networkx: {path}")
for ind, path in enumerate(paths_nx):
    path = list(path)
    if path not in paths_rx:
        print(f"Not in rustworkx #{ind}: {path}")
        if list(reversed(path)) not in paths_rx:
            print("Reversed path not present")

And it printed nothing. I think we can profit from this to improve the documentation on how to consume the API. The all_simple_paths for a single node already returns a lot of data, this method is even worse that it returns a lot of data for all pairs of the graph.

[oliverdial]

Thank you for figuring this out -- I suspect this'll let David use Rustworkx in his code :)

[dcmckayibm]

Much appreciated @IvanIsCoding !

[matthewware]

Just to make sure I'm not missing something obvious, the comments in #1088 still apply right? I still call rx.all_pairs_all_simple_paths() which will return all the paths on a graph that fit the specifications?

[IvanIsCoding]

Just to make sure I'm not missing something obvious, the comments in #1088 still apply right? I still call rx.all_pairs_all_simple_paths() which will return all the paths on a graph that fit the specifications?

That is correct. The method will materialize all paths