rustworkx
rustworkx copied to clipboard
Qiskit
Add Johnson's algorithm for cycles in directed graph
This commit adds a new function, simple_cycles(), which is an implementation of Johnson's algorithm [1] for finding all the simple cycles in a directed graph. The implementation is based on the non-recursive implementation from NetworkX. [2]
[1] https://doi.org/10.1137/0204007 [2] https://github.com/networkx/networkx/blob/networkx-2.8.4/networkx/algorithms/cycles.py#L98-L222
Closes: #622
TODO:
- [x] Add more tests
Pull Request Test Coverage Report for Build 2566000039
- 156 of 157 (99.36%) changed or added relevant lines in 3 files are covered.
- No unchanged relevant lines lost coverage.
- Overall coverage increased (+0.03%) to 97.183%
| Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
|---|---|---|---|
| src/connectivity/johnson_simple_cycles.rs | 151 | 152 | 99.34% |
| <!-- | Total: | 156 | 157 |
| Totals | |
|---|---|
| Change from base Build 2494694599: | 0.03% |
| Covered Lines: | 12798 |
| Relevant Lines: | 13169 |
💛 - Coveralls
Pull Request Test Coverage Report for Build 3114398726
- 224 of 236 (94.92%) changed or added relevant lines in 3 files are covered.
- 10 unchanged lines in 2 files lost coverage.
- Overall coverage decreased (-0.07%) to 97.029%
| Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
|---|---|---|---|
| src/connectivity/johnson_simple_cycles.rs | 219 | 231 | 94.81% |
| <!-- | Total: | 224 | 236 |
| Files with Coverage Reduction | New Missed Lines | % |
|---|---|---|
| src/shortest_path/all_pairs_bellman_ford.rs | 1 | 99.44% |
| rustworkx-core/src/min_scored.rs | 9 | 59.09% |
| <!-- | Total: | 10 |
| Totals | |
|---|---|
| Change from base Build 3113781859: | -0.07% |
| Covered Lines: | 12899 |
| Relevant Lines: | 13294 |
💛 - Coveralls
I've also refactored the function to return a py iterator to compute a cycle on each iteration instead of doing a full computation and returning the whole output at once.