The issue tracker is reserved for bug reports and feature requests. I'll edit this issue and mark it as a feature request. For finding cycles with existing functionality, please post on the support forum instead: https://igraph.discourse.group/

This can be done with Johnson's algorithm, see https://epubs.siam.org/doi/abs/10.1137/0204007

Other discussions on the topic:

• https://igraph.discourse.group/t/enumerating-all-the-elementary-circuits-of-a-directed-graph/532
• Add function to find all cycles. #379

It might be that I misunderstand something, but isn't igraph_fundamental_cycles() merged with #1957 exactly this feature (at least, if called as often as many cycles are searched)?

No. That function finds a cycle basis. This feature request is for enumerating all cycles, of which there are many, many more than what is contained in a basis.

I see, then I misunderstood your code, thanks for the response.

I therefore implemented a somewhat naïve approach to the problem in C++ and attached the resulting class. If you think the code lives up to the standards of this awesome library, I will gladly try to convert the C++ functionality used to "raw C" and submit a PR.

SimpleCycleFinder.hpp.txt

It would be nice to have a cycle finder in igraph, so if you'd like to work on it, that'd be very welcome. I took a very cursory look at the code, and it seems convertible to pure-C igraph. A few changes will be necessary, but nothing too difficult. I have not yet tried to understand how the code works.

Can you let us know:

• Which algorithm does this implement?
• Does it generalize to directed graphs?
• Have you thought about whether it supports self-loops and multigraphs? This is not critical, but it's good to keep in mind.

If you use igraph for your own projects, it's good to be aware that version 0.10 will be released very soon, and will bring lots of breaking changes. I would recommend to start using it ASAP, and not to write any new code with 0.9. There are tarballs for release candidates in GitHub's releases section, and the very latest version is accessible in this repo's develop branch.

Take a look at CHANGELOG.md on the develop branch to see the major changes.

Something that caught my eye was that edges are deleted and re-added. This is currently extremely inefficient. This would need to be replaced by a different approach, such as marking some edges as "non-existent" without removing them. This might require using an adapted version of the shortest path finding code just for the cycle finder, but this is easy enough. A quick solution for your own project is to use the weighted shortest path finder, and temporarily set some edge weights to infinity.

Thank you for this comprehensive answer and the hints and tips!

• Which algorithm does this implement?

I have not put any research into algorithms as I needed this only for moderately sized graphs; the algorithm I implemented can be summarized with the following pseudo-code:

• find "junctions" (vertices with degree > 2, as well as a random vertex from every cluster without any vertex with degree > 2)
• for each junction:
• find neighbours of this junction
• for each neighbour:
• find shortest path from the neighbour back to junction (without the direct edge)
• if found, and this path has not been returned before, return it now

As you see, this is a naïve implementation.
I only finds the simple cycles, rather than all, though by replacing the "find shortest path" with "find simple path", this could be generalised to all cycles (with exponential memory useage, etc.).

• Does it generalize to directed graphs?

I guess by only finding directed neighbours and directed paths, this algortihm can be generalised "easily".

• Have you thought about whether it supports self-loops and multigraphs? This is not critical, but it's good to keep in mind.

Yes, I did, though I have not come to a decisive answer. For the self loops, I guess it will end with a flag to decide whether to allow the direct edge if it is there twice. For the multigraphs, currently, the algorithm only returns the vertices anyway; by finding all shortest paths instead of just one, I would suppose the multigraphs would be supported automatically.

I will see what I can do, though it might take some time.

The usual meaning of "simple cycle" is a cycle with no repeating vertices. You seem to be using the term in a different sense here, though unclear to me how.

This approach will not find all simple cycles, and will find some cycles more than once.

Do you have a precise formulation of the problem that this algorithm actually solves?

It seems to me that if we are looking to find all simple cycles, it may be more productive to look at published algorithms, such as Johnson's.

Thank you for your patience. You might be right, my understanding of a simple cylce also includes that it cannot be broken down into smaller cycles, as shown in the first figure here.

This approach will find some cycles more than once, that is correct and part of why I call it naïve; my approach includes hashing each and every cycle, and skipping those where the hash has been found before, such that every cycle is only returned once.
I am not yet aware of any scenario where a simple cycle with the definition above would not be found.

Still, I agree that published alogrithms are probably a better fit for igraph. I will see how accessible they are to me, what I can do.

That article gives two incompatible definitions of "simple cycle". I would not consider it a trustworthy resource.

The second definition, "if a cycle can’t be broken down to two or more cycles, then it is a simple cycle", appears to be based on a misunderstanding. The cycles (1, 3, 4) and (1, 2, 3, 4) do form a cycle basis of the example graph in the article, and adding them together obtains (1, 2, 3). So (1, 2, 3) can in fact be "broken down" into two other cycles.

As you say, we could talk about cycles that cannot be decomposed into smaller cycles, but is this a useful concept? Consider a tetrahedron. Which are the "simple cycles" in it? All four faces? Now consider a pyramid, which has four triangular faces and a square face. According to your definition, we now have to exclude the square face as it is the sum of the triangle faces. So the result is markedly different from the case of the tetrahedron. Is this what you were looking to achieve, is this distinction useful?

More useful concepts are the cycle basis (including minimum weight cycle bases), or the idea of faces (which is really a property of an embedding of a graph, not merely the graph itself).

Thank you very much for these useful insights and examples. I will go back to the drawing board for a more generally interesting implementation then, starting with the literature. I hope to come back some day with a corresponding implementation.

I think this is also an instructive example:

Every edge in this graph is part of some 3-cycle. Thus the method you described will not generate the 4-cycle 1-2-3-4-1. Yet this 4-cycle cannot be decomposed into smaller cycles.

The naïve way to generalize my approach to all simple cycles is by replacing the step "find shortest path from the neighbour back to junction (without the direct edge)" with "find all simple paths from the neighbour back to junction (without the direct edge)".

This is achieved by replacing one call to igraph_get_shortest_path with igraph_get_all_simple_paths (and then iterating over those).

While for my purpose the current implementation is (with my current understanding of my problem and graphs) actually indeed sufficient, my curiosity is aroused.

But yes, I am still reading literature, as my naïve proposition is certainly not acceptable and I have not as much time to spend as I would like to. I will also have to read into the internals of igraph, if I want to implement the algorithm as efficient and close to the source as reasonable.

I expect it to take ca. > 1 month looking at my calendar, but will keep you updated here.

It is of course entirely up to you to decide whether you would like to (or have time to) work on this.

If yes, I would suggest first searching the literature for algorithms. I have not done this myself either yet, so all I can say at this point is that most seem to use Johnson's algorithm for this. If you decide that you would like to start coding, do let us know before you begin, so we can give you some igraph-specific guidance.

I would conclude my literature study confirming that Johnson's algorithm is indeed the way to go.

I will refer to https://github.com/igraph/igraph/blob/master/CONTRIBUTING.md and https://github.com/igraph/igraph/wiki/Tips-on-writing-igraph-code for a first overview of what to pay attention to in terms of writing igraph code.
Any suggestions what the file and function name structure could look like?

Here's a quickstart guide: https://github.com/igraph/igraph/wiki/Quickstart-for-new-contributors

I suggest you open a PR as early as possible so you can ask for feedback on the way. You can create a new file for this function and propose an interface.

The typical interface for functions that potentially produce a very large number of results use a callback function: it is invoked for each result. See igraph_cliques_callback() or igraph_get_isomorphisms_vf2_callback() for examples. We can then use the callback interface to implement a simpler interface that produces all cycles at once, similar to how igraph_cliques() produces all cliques.

Iterators, similar to what you have in your code, are planned for later, but we're not there yet. Thus, if you prefer an interface like that, it's fine to do it, but there should also be a callback interface.

One small comment based on the code you showed is that the most efficient way to get/set vector elements is the VECTOR macro: VECTOR(vec)[i] is the ith element of vec.

Note that we already have an implementation of Johnson's algorithm in src/paths/johnson.c for all-pairs shortest paths. I wonder whether that implementation could be repurposed for finding the cycles as well. (Haven't checked the actual implementation so I could be wrong).

That is an unrelated algorithm for a different purpose (shortest paths).