File Exchange

image thumbnail

Count Loops in a Graph

version 1.1 (167 KB) by

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

21 Downloads

Updated

View License

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.

Comments and Ratings (8)

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.

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

Zi Sue

Zi Sue (view profile)

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

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?

zahra shahbazi

it is awesome!

hamza drid

Added more example
i want know some detail about this work

Simone Severini

Excellent!

ed churchill

this is really neat!

Updates

1.1

Updated to include an App file for R2012b

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

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

MATLAB Release
MATLAB 8.0 (R2012b)

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

» Watch video