File Exchange

image thumbnail

Count all cycles in simple undirected graph

version 1.2.0.0 (5.43 KB) by Jeff Howbert
Counts all cycles in a simple undirected graph up to specified size limit, using backtracking.

5 Downloads

Updated 29 Aug 2011

View License

Counts all cycles in input graph up to (optional) specified size limit, using a backtracking algorithm. Designed for undirected graphs with no self-loops or multiple edges. Returns count of each size cycle from 3 up to size limit, and elapsed time.

Algorithm is guaranteed to find each cycle exactly once. It is essentially equivalent to Johnson (SIAM J. Comput. (1975), 4, 77), but for undirected graphs, and without the look-ahead feature. The lack of look-ahead is expected to have negligible performance impact on dense random graphs.

Reads input graph using separate m-file readGraph(), which supports reading a graph from a file or workspace array in four different formats. A test file for each format is included.

In practice this algorithm is much faster than the ILCA cycle counting algorithm posted by Joe Kirk (run_loops.m).

Cite As

Jeff Howbert (2020). Count all cycles in simple undirected graph (https://www.mathworks.com/matlabcentral/fileexchange/29438-count-all-cycles-in-simple-undirected-graph), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (3)

Rishika Sen

The test file does not look like it has 183 cycles of size 10. Yet the output says so.

varjak

is there a code for directed graphs?

Updates

1.2.0.0

Wrong .zip file uploaded on previous submission.

1.1.0.0

Function cycleCountBacktrack now returns a vector containing counts of cycles, and elapsed time. (In previous version, counts and time were only output to console.)

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

Inspired: PM Architectures Project