finding the shortest cycle in a graph

2 次查看（过去 30 天）
R yan
R yan 2015-7-23
评论： FWDekker 2024-10-9
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

请先登录，再回答此问题。

回答（1 个）

Jaynik
Jaynik 2024-9-5
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!
  1 个评论
FWDekker
FWDekker 2024-10-9
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

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by