Add support to `hexagonal_lattice_graph` for periodcity and position coordinates

[javabster]

What is the expected enhancement?

networkx's hexagonal_lattice_graph function provides support for periodicity and setting position coordinates, and it would be great if rustworkx's hexagonal_lattice_graph did the same.

Definition of done:

• a periodic bool argument added to hexagonal_lattice_graph
• a with_positions bool argument added to hexagonal_lattice_graph

cc @mrossinek

[mrossinek]

You can assign this issue to @javabster and myself :+1:

[mtreinish]

One small wrinkle you'll face implementing this is the actual code generating the hexagonal lattice graph was recently migrated from the python side of the library to rustworkx-core which is an inner pure rust library to enable Rust consumers to leverage the functionality we've written: https://github.com/Qiskit/rustworkx/blob/main/rustworkx-core/src/generators/hexagonal_lattice_graph.rs

The python side of the library is now just calling that generic rust function: https://github.com/Qiskit/rustworkx/blob/main/src/generators.rs#L1112-L1158 so to implement this periodic will be straightforward, but for with_positions on the rustworkx-core side you'll need to be a bit more general/generic in how to handle that because the input graphs because for rustworkx-core we don't make any assumptions on what the types are for node and edge payloads. I think the easiest way to do this is basically to add a new argument with_positions of type Option<F> where F is constrained to FnMut([usize; 2]) -> T or something like that. This will let users define how to go from a position to whatever type their graph contains.

For example, for the python side this is simple because you can just do:

let pos_to_py = |pos| -> PyObject {
    pos.to_object(py)
}

in the python side and set Some(pos_to_py) as the argument on the inner call if the boolean flag is true.

[javabster]

An update on our investigation:

We've compared how networkx handles periodicity for it's hexagonal lattices and other lattice types. Some lattice types add an extra edge between nodes, but the hexagonal lattice method actually combines nodes together (using a contracted_nodes function). This node contraction method seems to be the best option in the hexagonal lattice case as it enables users to maintain the rows and columns format as input arguments, and using that method here in rustworkx will keep feature parity with networkx. However the contracted_nodes logic in networkx is a bit difficult to follow so our next step is to investigate if there is a simpler way to implement this functionality. Additionally, we think it would be beneficial for users to be able to specify which direction to implement the periodicity. Networkx implements periodicity in all directions only, however we think there are potential use cases where a user might want to generate a hexagonal lattice which is periodic in just the x or just the y direction, so we will be looking into this implementation further.

cc @mrossinek

[javabster]

hi @mtreinish we've been looking into how to best implement the periodic part of this and are first looking to mimic the logic used in networkx in rustworkx-core/src/generators/hexagonal_lattice. We see that rustworkx has a contract_nodes function (similar to the networkx contracted_nodes) that we were considering using, but it seems like that method is only accessible from the python layer of rustworkx, not in rustworkx core? Do you have a recommendation for how best to proceed? We were considering options like only implementing periodicity from the python layer, or somehow refactoring contract_nodes to be usable in rustworkx-core. Not sure what would be the best option and would appreciate your input 😄

[mtreinish]

Yeah, that's correct the contract_nodes function only exists as a method on PyDiGraph and PyGraph. The best path forward would probably be to implement contract_nodes as a generic graph function in rustworkx-core. It shouldn't be too terrible to port over and update the method to call rustworkx-core internally. That would also let us deduplicate the function between the two graph classes. In general I tend to favor putting more functionality in rustworkx-core, if feasible, because that's expands the usability of the functionality to both rust and python.

That being said looking at the networkx logic the one complexity you'll have following that as a model is node remove (either directly or via contraction) will result in index holes in the output graph. This can be confusing for the generator functions as you basically can get a graph out that has the node indices [0, 1, 3, 4]. It's not a deal breaker (and IIRC the lattice generators used to do this until #397) but it is something to watch out for and document when you do implement it the algorithm.

[jpacold]

Commenting so that this can be assigned to me (see #1213)