Code covered by the BSD License

Highlights from Count Loops in a Graph

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

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

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)
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

Ben Petschel (view profile)

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

Comment only
06 Jun 2007 Simone Severini

Excellent!

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

Updated to include an App file for R2012b