is_cyclic for undirected graphs

[samwycherley]

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]

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]

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

[jpfairbanks]

@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]

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

[pgrepds]

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]

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

[etiennedeg]

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]

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]

closed by #168