Expanded grid_graph functionality

[awstasiuk]

What is the expected enhancement?

grid_graph in rustworkx only reproduces the functionality of grid_2d_graph from networkx. It would be convenient to extend grid_graph to higher dimensions in rustworkx, as I find graph generation is a significant bottleneck for my code.

Additionally, it would be very nice to see an extension of grid_graph to more lattice types, such as fcc, bcc, hexagonal 3d. This should also come with a flag to auto-label nodes with a tuple/vector containing spatial information.

[awstasiuk]

Looks like this is a specific request related to Issue #150

[IvanIsCoding]

I don't think we have anyone working on adding those specific generators now. But if you submitted them I'd me happy to review.

For the special case of grid graphs, I think you can achieve a somewhat similar result with https://www.rustworkx.org/apiref/rustworkx.cartesian_product.html#rustworkx.cartesian_product and taking the product of https://www.rustworkx.org/dev/apiref/rustworkx.graph_line_graph.html in the meantime. Of course the intermediary graphs are not very useful, but it shouldn't be hard to beat Python for loops performance wise.

[awstasiuk]

Thanks for the suggestion. I know that networkx uses cartesian_product to generate their grid_graphs, I will try this out myself. I was able to get a 10x speedup in rustworkx over the networkx code simply using add_edges_from a few list expressions, but this is still an order of magnitude slower that the rustworkx built in grid_graph solution. My solution includes labelling nodes with a tuple of spatial information.

3D example:

def grid_graph_3d(L):
    G = rx.PyGraph()
    G.add_nodes_from([(i,j,k) for k in range(L) for j in range(L) for i in range(L)])
    G.add_edges_from([(i+j*L+k*L**2,(i+1)+j*L+k*L**2,None) for k in range(L) for j in range(L) for i in range(L-1)])
    G.add_edges_from([(i+j*L+k*L**2,i+(j+1)*L+k*L**2,None) for k in range(L) for j in range(L-1) for i in range(L)])
    G.add_edges_from([(i+j*L+k*L**2,i+j*L+(k+1)*L**2,None) for k in range(L-1) for j in range(L) for i in range(L)])
    return G

[IvanIsCoding]

That makes sense. By the way, once #1292 is released in 0.16 I think your code will also run faster if you switch to the iterators

[awstasiuk]

Yes! Fantastic, I initially started with a generator expression and was disappointed to see it wasn't supported. I assumed it was a quirk related to rust, but glad to see it'll be supported soon.

If I submit a PR with pythonic solutions will that be acceptable for the code base? I'm happy to generalize and clean up my code, but I don't want to mess with rust.

[IvanIsCoding]

Yes! Fantastic, I initially started with a generator expression and was disappointed to see it wasn't supported. I assumed it was a quirk related to rust, but glad to see it'll be supported soon.

If I submit a PR with pythonic solutions will that be acceptable for the code base? I'm happy to generalize and clean up my code, but I don't want to mess with rust.

I’d say as a draft it would be welcome. At the very least it would be useful for the unit tests as they are written in Python. We could test the final Rust implementation using your Python implementation as a reference