Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Implement simple_cycles() Johnson Algorithm #622

Closed
chikko80 opened this issue Jun 5, 2022 · 5 comments · Fixed by #633
Closed

Implement simple_cycles() Johnson Algorithm #622

chikko80 opened this issue Jun 5, 2022 · 5 comments · Fixed by #633
Assignees
@mtreinish
Labels
enhancement New feature or request

Comments

@chikko80
Copy link

chikko80 commented Jun 5, 2022

What is the expected enhancement?

Networkx has an algorithm for finding all cycles in a directed graph:

simple_cycles

it's based on the Research of D. B. Johnson in 1975

Would love to see a rust implementation of that!
@mtreinish mtreinish added the enhancement New feature or request label Jun 5, 2022
@mtreinish mtreinish self-assigned this Jun 6, 2022
mtreinish added a commit to mtreinish/retworkx that referenced this issue Jun 6, 2022
@mtreinish
WIP: Add johnson's algorithm for cycles in directed graph
e470f50 
Closes: Qiskit#622
@chikko80
Copy link
Author

chikko80 commented Jun 7, 2022 •
edited
Loading

@mtreinish
I appreciate the fast implementation!
I tested your code on my current graph in comparison to networkx.
Just want to let you know that there is probably a little bug in the code.
On my current graph, networkx returns about 7000 cycle.
The retworkx implementation returns only 1.

Maybe just a wrong condition

@mtreinish
Copy link
Member

It's still a work in progress (hence the WIP prefix), it's still failing one of the tests I wrote too. I pushed up the commit to my fork mostly for saving so I had the work backed up. But, yeah the implementation isn't working fully yet, when I finish it then I'll open a pull request.

@chikko80
Copy link
Author

Hi @mtreinish,
I just wanna kindly ask how your current workload is and when we could expect the algorithm to be finished.
I know, you are doing that in your free time so absolutely no pressure.
I am just curious and looking forward to the implementation because it would fit into my current university project perfectly.

mtreinish added a commit to mtreinish/retworkx that referenced this issue Jun 26, 2022
@mtreinish
Add Johnson's algorithm for cycles in directed graph
ae15f57 
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: Qiskit#622
@mtreinish mtreinish mentioned this issue Jun 26, 2022
Merged
1 task
@mtreinish
Copy link
Member

mtreinish commented Jun 26, 2022 •
edited
Loading

I think I've got it working now, see #633, let me know if you still have issues with it. I still need to do more testing and add more tests to the PR

@chikko80
Copy link
Author

Working as expected!

@mergify mergify bot closed this as completed in #633 Sep 23, 2022
mergify bot pushed a commit that referenced this issue Sep 23, 2022
@mtreinish @georgios-ts @IvanIsCoding
Add Johnson's algorithm for cycles in directed graph (#633)
676a7cd 
* 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

* Remove test debugging

* Fix lint

* Add more tests

* Apply suggestions from code review

Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com>

* Fix rustfmt

* Make return from simple_cycles a iterator

This commit converts the simple_cycles function to a Python class that
implements the iterator protocol. Each step of the the iterator will
compute the next cycle using Johnson's algorithm and return a
NodeIndices object representing the cycle.

* Use IndexSet::pop() instead of set_pop()

* Fix iterator behavior

* Fix MSRV support

* Use mem::take() instead of .drain(..).collect()

Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com>
Co-authored-by: Ivan Carvalho <8753214+IvanIsCoding@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@mtreinish mtreinish

Labels
enhancement New feature or request
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Add Johnson's algorithm for cycles in directed graph mtreinish/retworkx
2 participants
@mtreinish @chikko80