# amount of chordless cycles **URL:** \ **Category:** Usage\ **Tags:** C\ **Created:** [11 December 2021 12:17 UTC](https://igraph.discourse.group/t/amount-of-chordless-cycles/1032 "2021-12-11T12:17:42Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![jgmbenoit](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/jgmbenoit/32/417_2.png) [@jgmbenoit](https://igraph.discourse.group/u/jgmbenoit)\ **Post date:** [11 December 2021 12:17 UTC](https://igraph.discourse.group/t/amount-of-chordless-cycles/1032/1 "2021-12-11T12:17:42Z")
Is there a way to compute the number of chordless cycles in a given graph with `igraph` (in particular with the C library) ? ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [11 December 2021 15:18 UTC](https://igraph.discourse.group/t/amount-of-chordless-cycles/1032/2 "2021-12-11T15:18:21Z")
There are ways you can use, but they will be slow. Take a look at `igraph_subisomorphic_lad()`. It has an option to find only _induced_ subgraphs. You can then look for induced (i.e. chordless) cycles for each size one by one. Note that this function computes subgraph isomorphsms, not subgraphs. There are 2n ways to map an n-cycle onto itself (n rotations and a reversal). Thus, the counts for n-cycles need to be divided by 2n. Also look at `igraph_motifs_randesu()`. This functions counts “motifs”, i.e. connected induced subgraphs of a given size. It is implemented only for size-3 and size-4 motifs, but it will be the fastest way to count size-4 induced cycles. I don’t recall any other simple way using existing functions. If you are aware of good algorithms for solving this problem, please open a feature request and provide referenced along with a brief summary of the topic. ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [11 December 2021 15:33 UTC](https://igraph.discourse.group/t/amount-of-chordless-cycles/1032/3 "2021-12-11T15:33:31Z")
Some relevant links: > **[An Efficient Algorithm for Enumerating Chordless Cycles and Chordless Paths](https://arxiv.org/abs/1404.7610)** > > A chordless cycle (induced cycle) $C$ of a graph is a cycle without any > chord, meaning that there is no edge outside the cycle connecting two vertices > of the cycle. A chordless path is defined similarly. In this paper, we consider > the problems of... [https://link.springer.com/chapter/10.1007/978-3-319-11812-3\_27](https://link.springer.com/chapter/10.1007/978-3-319-11812-3_27) (Peer reviewed version of the above.) > **[Efficient Enumeration of Chordless Cycles](https://arxiv.org/abs/1309.1051)** > > In a finite undirected simple graph, a {\\it chordless cycle} is an induced > subgraph which is a cycle. We propose two algorithms to enumerate all chordless > cycles of such a graph. Compared to other similar algorithms, the proposed > algorithms have the... (Did not find a peer-reviewed version.) > (It might be good to look at, but do not trust StackOverflow on topics like this one.) ---
**Author:** ![jgmbenoit](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/jgmbenoit/32/417_2.png) [@jgmbenoit](https://igraph.discourse.group/u/jgmbenoit)\ **Post date:** [11 December 2021 19:06 UTC](https://igraph.discourse.group/t/amount-of-chordless-cycles/1032/4 "2021-12-11T19:06:36Z")
For now it sounds heavy indeed. ---
**Author:** ![jgmbenoit](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/jgmbenoit/32/417_2.png) [@jgmbenoit](https://igraph.discourse.group/u/jgmbenoit)\ **Post date:** [11 December 2021 19:34 UTC](https://igraph.discourse.group/t/amount-of-chordless-cycles/1032/5 "2021-12-11T19:34:04Z")
[EFFICIENT PARALLEL ALGORITHMS FOR FINDING CHORDLESS CYCLES IN GRAPHS](https://www.worldscientific.com/doi/abs/10.1142/S0129626493000204) [http://research.nii.ac.jp/~uno/code/cypath.html](http://research.nii.ac.jp/~uno/code/cypath.html) [http://research.nii.ac.jp/~uno/codes.htm](http://research.nii.ac.jp/~uno/codes.htm) ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [12 December 2021 09:51 UTC](https://igraph.discourse.group/t/amount-of-chordless-cycles/1032/6 "2021-12-12T09:51:13Z")
Are you feeling up to implementing an algorithm for this? ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [12 December 2021 10:18 UTC](https://igraph.discourse.group/t/amount-of-chordless-cycles/1032/7 "2021-12-12T10:18:32Z")
> > > \*\*What is the feature or improvement you would like to see?\*\* > > Find all chordl…ess cycles in an undirected graph. A chordless cycles, also called an induced cycle, is a cycle in which only consecutive vertices are connected. In other words, it is a an induced subgraph that is a cycle. > > In the following example, the cycle 1, 2, 3, 4, 5, 6 is chordless in the first two graphs, but not in the third where 1-4 are connected with an edge. > > \image > > This is a good candidate for iterator-based enumeration. Until the iterator infrastructure is added, the function should take a callback that handles each detected chordless cycle one-by-one. > > \_Theory contribution requested: Which algorithm should we try to implement and why? What is the complexity of the algorithms in the papers from the reference list and which looks reasonably easy to implement?\_ > > \*\*Use cases for the feature\*\* > > Can you fill this section out @jgmbenoit ? > > \*\*Related igraph functions\*\* > > - \`igraph\_is\_chordal()\` returns "false" is chordless cycles exist > - \`igraph\_subisomorphic\_lad()\` can find \_induced\_ subgraphs, and can thus find chordless cycles. This method is very slow. > > \*\*Related issues\*\* > > - #1886 > > \*\*References\*\* > > - Original feature request: https://igraph.discourse.group/t/amount-of-chordless-cycles/1032 > - Takeaki Uno, Hiroko Satoh: An Efficient Algorithm for Enumerating Chordless Cycles and Chordless Paths (2014) > \* arXiv: https://arxiv.org/abs/1404.7610 > \* peer-reviewed: https://doi.org/10.1007/978-3-319-11812-3\_27 > \* description: http://research.nii.ac.jp/~uno/code/cypath.html and software: http://research.nii.ac.jp/~uno/codes.htm > - \[Elisângela Silva Dias, Diane Castonguay, Humberto Longo, Walid Abdala Rfaei Jradi: Efficient Enumeration of Chordless Cycles\](https://arxiv.org/abs/1309.1051) (2013) (There seems to be no peer-reviewed version?) > - N. CHANDRASEKHARAN, V.S. LAKSHMANAN and MURALIDHAR MEDIDI: \[EFFICIENT PARALLEL ALGORITHMS FOR FINDING CHORDLESS CYCLES IN GRAPHS\](https://www.worldscientific.com/doi/abs/10.1142/S0129626493000204) (1993) > - Proposal on StackOverflow: https://stackoverflow.com/questions/4022662/find-all-chordless-cycles-in-an-undirected-graph ---
**Author:** ![jgmbenoit](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/jgmbenoit/32/417_2.png) [@jgmbenoit](https://igraph.discourse.group/u/jgmbenoit)\ **Post date:** [15 December 2021 19:57 UTC](https://igraph.discourse.group/t/amount-of-chordless-cycles/1032/8 "2021-12-15T19:57:12Z")
[Amortized Õ(|V|)-Delay Algorithm for Listing Chordless Cycles in Undirected Graph](https://hal.inria.fr/hal-01081031/document) ---
**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\ **Post date:** [16 December 2021 07:34 UTC](https://igraph.discourse.group/t/amount-of-chordless-cycles/1032/9 "2021-12-16T07:34:43Z")
Thanks, I added it to the feature request issue. Can you comment on the use cases, so we can fill that section out as well (see issue on GitHub)?