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.

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

is_cyclic for undirected graphs #34

Closed
samwycherley opened this issue Nov 2, 2021 · 9 comments
Closed

is_cyclic for undirected graphs #34

samwycherley opened this issue Nov 2, 2021 · 9 comments
Labels
bug Something isn't working good first issue Good for newcomers

Comments

@samwycherley
Copy link
Contributor

Issue previously open at #1518 for LightGraphs.jl.

The is_cyclic function in LightGraphs.jl works well for directed graphs but for undirected graphs returns true for any nonempty graph. The usual definition for undirected graphs is that cycles don't contain repeated links, so 1->2->1 is not considered a cycle (absent multiple edges.)

Useful for me because I want a function that will test whether an (undirected) network is a tree and easiest way to check that is to confirm the graph is acyclic+connected

@mtfishman
Copy link
Contributor

My understanding was that for an undirected graph g you can check if it is a tree if ne(g) == nv(g) - 1 and it is connected (https://en.wikipedia.org/wiki/Tree_(graph_theory)#Tree).

Maybe there should also be a generic is_tree function that covers both directed and undirected graphs?

@samwycherley
Copy link
Contributor Author

Ah yes thanks, that's a more efficient route. Still, would be nice to have is_cyclic working for undirected graphs

@jpfairbanks
Copy link
Member

@samwycherley, Are you interested in finding an algorithm for this? If not I'll close since @mtfishman solved your direct problem. The non-backtracking part makes its a bit harder.

@samwycherley
Copy link
Contributor Author

When I have time, I'll try and work on it and put up a PR. Feel free to close in the meantime.

@gdalle gdalle added bug Something isn't working good first issue Good for newcomers labels Nov 11, 2021
@pgrepds
Copy link
Contributor

pgrepds commented Jan 19, 2022

Is someone working on this Issue? If not, I would like to implement it as a first issue. If we want to add a generic function is_tree as suggested, we might need to consider the disconnected case as well (a graph could have multiple trees as components -> forest).

@gdalle
Copy link
Member

gdalle commented Mar 10, 2022

@pgrepds feel free to contribute, it is a nice first issue to tackle!

@etiennedeg
Copy link
Member

Because of this that say the behavior was intended, wouldn't it be a breaking change ? To clear the confusion, maybe we could deprecate this function , and have a is_directed_acyclic that would work only for directed graphs, and a is_forest that would work only for undirected graphs ?

@natema
Copy link
Contributor

natema commented Sep 20, 2022

It seems that #168 is ready to be merged to close this.
The pull request is by a student in our team at INRIA UCA and we hope to contribute more now that more members of the team are starting to use Julia.

@etiennedeg
Copy link
Member

closed by #168

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working good first issue Good for newcomers
Projects
None yet
Development

No branches or pull requests

7 participants