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


Updated 24 Jul 2017

View License

This is a Matlab implementation of the general purpose algorithm for counting simple paths presented in the article "A general purpose algorithm for counting simple cycles and simple paths of any length" available at 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 paths of any length between any two vertices 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. The algorithm also works on weighted graphs, where it returns the sum of the weights of the simple paths of any given length.
This algorithm does not count the simple cycles, for these use CycleCount. If you want to count both simple cycles and simple paths use CyclePathCount. Both of these functions are on the Matlab File Exchange

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

Cite As

Pierre-Louis Giscard (2023). PathCount(A,L0) (, MATLAB Central File Exchange. Retrieved .

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!
Version Published Release Notes