finding the shortest cycle in a graph
10 views (last 30 days)
Show older comments
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
0 Comments
Answers (1)
Jaynik
on 5 Sep 2024
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!
1 Comment
FWDekker
on 9 Oct 2024 at 12:39
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.
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
See Also
Categories
Find more on Graph and Network Algorithms in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!