File Exchange

image thumbnail

CyclePathCount(A,L0​)

version 1.0.0.0 (7.86 KB) by Pierre-Louis Giscard
Algorithm for counting simple paths & cycles of any length on any (weighted directed) network.

2 Downloads

Updated 24 Jul 2017

View License

This is a Matlab implementation of the general purpose algorithm for counting simple cycles and simple paths 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. Simple cycles, a.k.a elementary circuits, self-avoiding walks, are cycles that do not visit any vertex more than once. Simple paths, a.k.a self-avoiding walks, are open walks that do not visit any vertex more than once.
The algorithm, a combinatorial sieve, counts simple cycles (self-loops, backtracks, triangles, squares, pentagons, etc.) & simple paths of any length on both directed and undirected networks, returning a cell array, Primes, where Primes{i} is a matrix whose kl entry is the number of simple paths of length 1<=i<=L0 from vertex k to vertex l. Entry kk is the number of simple cycles of length 0<=i<=L0 from k to itself. The algorithm also works on weighted graphs, where it returns the sum of the weights of the simple paths/cycles of any given length.

Use as follows:
[Primes,elapsedTime] = CyclePathCount(A,L0)
with Primes the cell-array with the number of simple paths/cycles, A the graph adjacency matrix and L0 the maximum length up to which to count the simple paths/cycles.

Cite As

Pierre-Louis Giscard (2021). CyclePathCount(A,L0) (https://www.mathworks.com/matlabcentral/fileexchange/63849-cyclepathcount-a-l0), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (0)

MATLAB Release Compatibility
Created with R2017a
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!