Code covered by the BSD License  

Highlights from
Count Loops in a Graph

5.0

5.0 | 3 ratings Rate this file 28 Downloads (last 30 days) File Size: 167 KB File ID: #10722
image thumbnail

Count Loops in a Graph

by

 

12 Apr 2006 (Updated )

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

| Watch this File

File Information
Description

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 (6)
13 Mar 2012 Zi Sue

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?

30 Jun 2008 zahra shahbazi

it is awesome!

19 Aug 2007 hamza drid

Added more example
i want know some detail about this work

06 Jun 2007 Simone Severini

Excellent!

19 Apr 2006 ed churchill

this is really neat!

Updates
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

Updated to include an App file for R2012b

Contact us