CycleCount(A,L0)

Algorithm for counting simple cycles of any length on any (weighted directed) network.

369 Downloads

Updated 2 Oct 2017

View License

This is a Matlab implementation of the general purpose algorithm for counting simple cycles presented in the article "A general purpose algorithm for counting simple cycles and simple paths of any length" available at https://arxiv.org/abs/1612.05531 (to appear in Algorithmica). Simple cycles, a.k.a elementary circuits, self-avoiding walks, are cycles that do not visit any vertex more than once.
The algorithm, a combinatorial sieve, counts simple cycles (self-loops, backtracks, triangles, squares, pentagons, etc.) of any length on both directed and undirected networks, returning a list with the number of simple cycles up to some desired length L. The algorithm also works on weighted graphs, where it returns the sum of the weights of all the simple cycles of any given length.
Use as follows:
[Primes,elapsedTime] = CycleCount(A,L0)
with Primes the list with the number of simple cycles, A the graph adjacency matrix and L0 the maximum length up to which to count the simple cycles.
PYTHON version available at: https://github.com/milani/cycleindex

Cite As

Pierre-Louis Giscard (2023). CycleCount(A,L0) (https://www.mathworks.com/matlabcentral/fileexchange/60814-cyclecount-a-l0), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2016a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.2.0.0

Now detects automatically if the graph is weighted or not and works accordingly in both situations without having to deactivate line 54.

1.1.0.0

Fixed a minor error in the published code causing the output for the number of simple cycles on some directed graphs to be faulty. Thanks to Evangelos Evangelou for pointing the error out. Publications based on CycleCount are not affected.

1.0.0.0