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

Add equivalent of cycle_basis that returns an edge list #551

Open
IvanIsCoding opened this issue Jan 14, 2022 · 3 comments · May be fixed by #885
Open

Add equivalent of cycle_basis that returns an edge list #551

IvanIsCoding opened this issue Jan 14, 2022 · 3 comments · May be fixed by #885
Assignees
@raynelfss
Labels
enhancement New feature or request good first issue Good for newcomers

Comments

@IvanIsCoding
Copy link
Collaborator

What is the expected enhancement?

Create an equivalent of the retworkx.cycle_basis method but returning edges instead of nodes.

https://github.com/Qiskit/retworkx/blob/5b90ee7821398625b16aec2e4d782dd2ec26daf2/src/connectivity/mod.rs#L67-L135

The original paper (http://www.cs.kent.edu/~dragan/GraphAn/CycleBasis/p514-paton.pdf) which we implement returns a set of nodes instead a set of edges. #505 pointed out that returning a set of edges is more useful in many cases. The expected enhancement is to have a method for each such that users can get a cycle basis both with nodes and with edges.
@IvanIsCoding IvanIsCoding added enhancement New feature or request good first issue Good for newcomers labels Jan 14, 2022
@IvanIsCoding IvanIsCoding mentioned this issue Jan 14, 2022
Closed
@szhorvat
Copy link

This should be fairly straightforward to implement, without needing to refer to a paper for guidance. The idea is to create a spanning tree through graph traversal, then let each non-tree edge induce a cycle in the tree. The key is to do the graph traversal in terms of edges rather than vertices. Then multi-edges won't be a problem.

@raynelfss
Copy link
Contributor

I'd like to take a closer look into this issue. Can I be assigned?

@mtreinish
Copy link
Member

Sure thing, I've assigned you to this issue

@raynelfss raynelfss linked a pull request May 31, 2023 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@raynelfss raynelfss

Labels
enhancement New feature or request good first issue Good for newcomers
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Implementation of cycle_basis_edges raynelfss/rustworkx
4 participants
@szhorvat @mtreinish @IvanIsCoding @raynelfss