Code covered by the BSD License  

Highlights from
Count Loops in a Graph

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

Count Loops in a Graph

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

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)

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.

Contact us