Is there a way to find all unique cycles of length n using LightGraph
o / \ o - o | | o - o
e.g:
using LightGraphs
g = Graph()
add_vertices!(g,5)
add_edge!(g,1,2)
add_edge!(g,2,3)
add_edge!(g,3,4)
add_edge!(g,4,5)
add_edge!(g,5,1)
add_edge!(g,2,4)
cycles = ?
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.
That said, if you have a directed graph g,
filter(x->length(x)==N, simplecycles_hadwick.james(g))
should do what you want.
So, cyclicity doesn’t really mean much for undirected graphs
Maybe it doesn’t mean much to you…
Your response might be interpreted as being a little bit condescending.
There are real-world cases that can be represented as an undirected graph , where the question of the existence of cycles and n-cycles are of interest to the problem domain.
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
Does the question refer to cycles or simple cycles?
[ Simple cycles cannot repeat vertices ]. As the name implies, the simplecycles_hadwick_james function returns the simple cycles.
And if vertex repeats are allowed, are edge repeats allowed? edge repeats in opposite directions?
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: Cycle (graph theory) - Wikipedia
n-cycle for an undirected graph would be an ordered set of unique vertices of of size n : V1,V2,…Vn
such that edge(Vi,Vi+1) exists for I=1:n-1 and edge(Vn,V1) also exists.
since it is an undirected and there is no way of telling a cycle from its circularly shifted version,
we consider only the equivalence class.
if the vertices has weight associated with them(for example index) , then a lexicographical order can be imposed and the minimum can be taken as a representative of the equivalence class.
what do you think?
I don’t know if this is interesting or useful outside my problem domain , but it was a question I encountered.
That’s a good use case - it would be a good addition to the package, though I can’t think of a really efficient way to do this offhand. Finding all cycles in undirected graphs - Stack Overflow might give some inspiration if you’d like to code something up (perhaps as a future PR).
(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.)
I gather this implies that, for an undirected graph, Edge(i,j) is equivalent to Edge(j,i), at least as repetition is concerned? If so, I think this is equivalent to @TsurHerman’s proposal below.
Actually, it is not equivalent, when considered carefully (an exercise for you). But this is a bit moot, as the original poster seems to have lost interest in explaining what he is after.
I confess to being distracted by JuliaCon right now, but if you want to humor me with the counterexample, I promise to be sufficiently embarrassed that it didn’t occur to me at first read.
Edit: found the counterexample. 
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.