Resolve issue #1029

[gluonhiggs]

In fact, I do not want to merge my code straightforwardly, because I need some advice!

1. I added the function minimum_cycle_basis and some tests. It works, but I believe it it need some modifications to be more well programmed, including the choice of having error handler or not.
2. With the assumption that the Rust core of minimum_cycle_basis is working fine, we need to add a Python layer to wrap around it. And there are some errors in src/connectivity/mod.rs where we use #[pyfunction] annotation. I have no idea to fix this. Perhaps, to fix it, I need to modify even the minimum_cycle_basis.rs core in rustworkx-core/src/connectivity/.
3. [for fun] By the way, I don't feel like this is a good first issue from 0 knowledge about Rust to 7 months developing this :D Link to the issue https://github.com/Qiskit/rustworkx/issues/1029

[CLAassistant]

All committers have signed the CLA.

[gluonhiggs]

For convenience, I think I need to explain my idea why I perform the subgraph creation and the lifted graph construction as in the minimum_cycle_basis.rs so that you can find it easier to review. Our ultimate goal is to return a (minimal) cycle basis which contains the information of the input graph nodes (i.e NodeIndex(n) for node n). Because in Rust, if we create a new graph which preserves some structure of another graph, we would have the NodeIndex() reset (this phenomenon doesn't happen in Python, and I can't think of any other way to overcome). Therefore, I have to use the name of the original nodes and pass them across the flow to track the node order. We manipulate the subgraphs, the lifted graphs and get the data, using the names to map afterwards to obtain the NodeIndex.

[gluonhiggs]

I have added some modifications based on your advice. However, I don't think my approach using the new trait EdgeWeightToNumber is a good idea. I will try to generalize the edge weight type instead of forcefully using i32.

[IvanIsCoding]

I think the code is looking better now, the compiler is complaining about some unused variables + trait missing for Python but overall this was a big improvement! Thanks

[gluonhiggs]

I have modified the functions in minimum_cycle_basis.rs so that they are able to take weight_fn that returns Result<K,E>. By this, I guess we can deal with more general weights (e.g not only i32). The thing is I also want to and the python wrapper for this core, but I don't quite understand how precisely to implement this. It would be wonderful if you provide some keywords or document that I can search to read and learn, I think I can also do this (it will take a while). Thank you!

[IvanIsCoding]

I have modified the functions in minimum_cycle_basis.rs so that they are able to take weight_fn that returns Result<K,E>. By this, I guess we can deal with more general weights (e.g not only i32). The thing is I also want to and the python wrapper for this core, but I don't quite understand how precisely to implement this. It would be wonderful if you provide some keywords or document that I can search to read and learn, I think I can also do this (it will take a while). Thank you!

If you know that you need to access the weights multiple times I recommend following this pattern: https://github.com/Qiskit/rustworkx/blob/e4dae8c495cb04aae276a12b76b2005eafa265df/src/shortest_path/all_pairs_dijkstra.rs#L69.

If you only need to call this once you can wrap this pattern https://github.com/Qiskit/rustworkx/blob/e4dae8c495cb04aae276a12b76b2005eafa265df/src/shortest_path/floyd_warshall.rs#L90 into a function that you pass to the Rust code.

[gluonhiggs]

I've added what I think necessary. Thank you a lot!

[coveralls]

Pull Request Test Coverage Report for Build 9597606406

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

• For more information on this, see Tracking coverage changes with pull request builds.
• To avoid this issue with future PRs, see these Recommended CI Configurations.
• For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

• 0 of 290 (0.0%) changed or added relevant lines in 1 file are covered.
• 16 unchanged lines in 1 file lost coverage.
• Overall coverage decreased (-1.5%) to 94.354%

---

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
rustworkx-core/src/connectivity/minimal_cycle_basis.rs	0	290	0.0%
<!--	Total:	0	290

Files with Coverage Reduction	New Missed Lines	%
src/connectivity/mod.rs	16	96.75%
<!--	Total:	16

Totals
Change from base Build 9473947759:	-1.5%
Covered Lines:	17413
Relevant Lines:	18455

---

💛 - Coveralls