finding the shortest cycle in a graph

hi I am trying to implement the following to find the length of a smallest cycle in a graph G. Please suggest which functions/toolbox are useful for this. I will also be computing how many cycles are there of a particular length. thanks

girth = 1000;
for each edge e(u,v) in G(V,E)
        new_girth = shortestpathlength(G\{e}, u, v) + 1 
                     % shortest distance between u and v
             if (new_girth < = girth)
                girth= new_girth
          G= G U {e}
    end

Answer 1

[Jaynik]

Hi @R yan,

You can use the allcycles function on a graph object to find all the cycles in a graph. Once you obtain all the cycles, you can count the number of elements in each cycle and increment a counter variable if they match the required count. Here is a sample code to do the same:

function cycleCount = countCyclesOfLength(G, length)
    % Find all cycles in the graph
    cycles = allcycles(G);
    
    % Count cycles of the specified length
    cycleCount = 0;
    for i = 1:numel(cycles)
        if numel(cycles{i}) == length
            cycleCount = cycleCount + 1;
        end
    end
end

You can refer the following documentation to read more about allcycles: https://www.mathworks.com/help/matlab/ref/graph.allcycles.html

I hope this helps!

[FWDekker]

For large or non-sparse graphs, allcycles will be way too expensive. I've adapted your idea of using allcycles as follows: Starting at girth g = 3 until g = numnodes(G), check if there exists a cycle of length g. If it does, you've found the girth; otherwise, increment g.

This method runs in 0.002 seconds on the fully-connected 1000-node graph, and in 0.15 seconds on a 1000-node graph with girth 50.

My code is as follows (previously also published in the source code for one of my papers):

function girth = girth(G)
    % GIRTH  Returns the length of the shortest cycle in [G], or `Inf` if [G] has no
    % cycles.

    arguments (Input)
        G (1, 1) graph;
    end
    arguments (Output)
        girth (1, 1) {isNumeric, mustBeNonnegative};
    end

    if ~hascycles(G)
        girth = Inf;
        return;
    end

    for girth = 3:numnodes(G)
        [~, found_cycles] = allcycles(G, MaxCycleLength = girth, MaxNumCycles = 1);

        if ~isempty(found_cycles); return; end
    end
end