[BUG] is_cyclic not correctly working on undirected graphs

[simonschoelly]

Description of bug
is_cyclic does not behave as one would expect on undirected graphs, it seems as soon as there is an edge u -- v it thinks there is a cycle u -> v -> u. This behavior makes sense for directed graphs but for undirected graphs this makes this function useless.

How to reproduce
Create an undirected graph with at least one edge and run is_directed on it.

Expected behavior
The function should only return true if there is a cycle that does not use the reverse of an edge.

Actual behavior
The function seems returns true as soon as there is at least one edge.

Code demonstrating bug

julia> gd = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph

julia> add_edge!(gd, 1, 2)
true

julia> is_cyclic(gd)
false

julia> add_edge!(gd, 2, 1)
true

julia> is_cyclic(gd)
true

Version information

julia> versioninfo()
Julia Version 1.6.0-beta1
Commit b84990e1ac (2021-01-08 12:42 UTC)
Platform Info:
 OS: Linux (x86_64-pc-linux-gnu)
 CPU: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
 WORD_SIZE: 64
 LIBM: libopenlibm
 LLVM: libLLVM-11.0.0 (ORCJIT, skylake)
Environment:
 JULIA_EDITOR = gvim

(@v1.6) pkg> st LightGraphs
Status `~/.julia/environments/v1.6/Project.toml`
 [093fc24a] LightGraphs v1.3.5

[simonschoelly]

Ok, I just realized that this was done on purpose in the past: #603, but I would still say, that we should either forbid this function on undirected graphs or change how it works.

[sbromberger]

@simonschoelly I don't know whether this is really a bug as opposed to a trivial result. Are you aware of literature that handles cycles in undirected graphs differently?

[simonschoelly]

I think one definition of a cyclic undirected graph is a graph that has an edge that is not a bridge. I.e. a cycle in an undirected graph can not contain repeated edges.

In the current form, as soon as a graph has an edge 1--2, then we say that there is a cycle 1-->2-->1 but that information is not of use to anyone.

I would prefer if we would either change it to this definition or just restrict the function to directed graphs, as I think otherwise people will just be confused.

[sbromberger]

I agree:

In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge....

We should fix it so that it works for undirected graphs.