So, cyclicity doesn’t really mean much for undirected graphs. We’ve made a decision in LightGraphs to allow cyclicity tests on undirected graphs (this merely checks to see whether ne(g) > 0), but the cycle enumeration algorithms (simple_cycles_hadwick_james and simple_cycles_iter) only work on directed graphs.
Your response might be interpreted as being a little bit condescending.
That wasn’t my intention. We actually had an extensive discussion about this on Gitter and in the LightGraphs issues where my original view was changed. The fact remains that an edge in an undirected graph from u to v can imply bidirectional connectivity, which creates a cycle. If you don’t want that behavior in LightGraphs (which is the specific package to which the original question referred) then you must use a directed graph.
A better answer would be that any undirected graph can be seen as a directed graph where the existence of edge from vertex i to vertex j , implies the existence of an edge from vertex j to I
Except that’s potentially misleading in the context of LightGraphs, since we treat directed graphs as completely separate types from undirected graphs, with different backend storage. Your definition works in the abstract, but it does not reflect the design decisions we made in LightGraphs that might argue for a different approach to the problem.
If you have a meaningful definition of cyclicity that applies to undirected graphs, I’m all ears and would absolutely be willing to reopen the LightGraphs issue (above) in which we came to the conclusion that, in fact, cyclicity doesn’t mean much in the context of undirected graphs.
How about a concept of cycles with no repeated edges? i.e. a sequence of edges where each shares a vertex with the previous and the next edge (and the last shares a vertex with the first). Also called a circuit in graph theory. Reference: https://en.wikipedia.org/wiki/Cycle_(graph_theory)
(Thinking about this a bit more, if one restricts the problem to “cycles of exactly length N”, we might be able to gain some efficiencies by not having to consider a substantial set of possible cycles. For example,
If we take the DAG of the graph, initialize “head = root” and then start at the head and follow the tree down N vertices across all branches to a target vertex “targ”, and then check to see whether there’s a (targ, head) edge in the original graph, we can determine whether there’s a cycle of length N that involves the head, and we get the set of vertices involved in that cycle (in cyclic order). We can then set “head” iteratively to root’s children, doing the same thing, until there no more paths of length “N” exist in the DAG. There may be bugs in this approach, and there may be another commonly accepted way of doing this.)
It seems this feature is till not implemented in LightGraphs. I found it both intuitive and useful to detect whether there is a simple cycle in an undirected graph.
Edit: A really useful observation by reading the StackOverflow is: when the graph is connected (happenly to be my usecase), it is a tree if there is no cycle in it. But it is really easy to check whether the connected graph is a tree: the number of edges of a tree is n-1 where n being the number of nodes of the graph.