View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Count Loops in a Graph

5.0 | 4 ratings Rate this file 18 Downloads (last 30 days) File Size: 167 KB File ID: #10722 Version: 1.1
image thumbnail

Count Loops in a Graph


Joseph Kirk (view profile)


12 Apr 2006 (Updated )

Calculates the number of loops in a graph consisting of nodes and edges

| Watch this File

File Information

The code contained in these files counts the number of loops (cycles) in a network (graph) that consists of nodes and edges. The user can:
 - Obtain a network (from a file or randomly generated)
 - View the network (optional)
 - Reduce the network (optional)
 - View the reduced network (optional)
 - Start the counting algorithm
 - Save the network to a file (optional)
 - Save the loops to a file (optional)
 - View the loop length distribution (optional)

There are two ways to execute the code:
1. GUI (loops_gui.m) opens an interface with buttons
2. M-FILE (run_loops.m) runs all the code without the GUI interface

The algorithm used to count the loops is an iterative process I developed that I call the ILCA (Iterative Loop Counting Algorithm). It transforms the network into a tree and does a *depth first* search on the tree for loops. This is a *brute force* technique as there are no known (to my knowledge anyway) algorithms for providing a good estimation of the number of loops/cycles in a network/graph.

MATLAB release MATLAB 8.0 (R2012b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (8)
26 Jan 2017 Joseph Kirk

Joseph Kirk (view profile)

@Dragana, I have some code that counts cycles in directed graphs. Send me an email if you would like details.

Comment only
09 Jan 2017 Dragana Ristanovic

Very nice but is there any possibility to modify the code in order to use it for directed graphs?

13 Mar 2012 Zi Sue

Zi Sue (view profile)

It is very nice but is there anyone can solve any problems for me?

21 Mar 2009 Ben Petschel

Nice code and very well documented.

Another idea uses the theory of cycle subspaces (e.g. chapter 5 of Wallis's book on graph theory) - use a spanning tree to construct the (e-v+1) fundamental cycles and then check all 2^(e-v+1) combinations to eliminate disjoint unions and figure-8's. Does this algorithm compare favourably with your tree method?

Comment only
30 Jun 2008 zahra shahbazi

it is awesome!

19 Aug 2007 hamza drid

Added more example
i want know some detail about this work

Comment only
06 Jun 2007 Simone Severini


Comment only
19 Apr 2006 ed churchill

this is really neat!

13 Apr 2006

1) Minor bug fixes.
2) Added more example graph files in the 'nets/' folder.
3) Updated description.

13 Apr 2006

1. Enhancement: Added a SCRIPT in addition to the GUI, as well as HTML created using MATLAB Publisher

2. Change to file details: Updated the title and description

12 Sep 2012 1.1

Updated to include an App file for R2012b

Contact us