search

JuliaGraphs / Graphs.jl

An optimized graphs package for the Julia programming language
http://juliagraphs.org/Graphs.jl/
Other
463 stars 92 forks source link

`is_cyclic` for undirected graphs #34

Closed samwycherley closed 2 years ago

samwycherley commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

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

jpfairbanks commented 2 years ago

@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 commented 2 years ago

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

pgrepds commented 2 years ago

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 commented 2 years ago

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

etiennedeg commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

closed by #168