我有一些Matlab中的全连通图。我想迭代地去除小边缘。如果删除某条边会破坏图的连通性,那么我想保留这条边并尝试删除下一条边。我有一个Matlab代码,它完美地做到了:
close all
clear all
clc
rng(2023)
%% generate fake data
X = rand(100,10);
R = corr(X);
R = (R+R')./2; % remove numerical problems. Make matrix symmetric
G = graph(R.^2,'omitselfloops');
%% simplify the graph
G.Edges.isChecked(:)=0;
G.Edges.edgeID=[1:size(G.Edges,1)]';
while true
% find minimal edge, which is not checked already
notCheckedEdges = G.Edges(G.Edges.isChecked==0,:);
[~,minID] = min(notCheckedEdges.Weight);
minID = notCheckedEdges.edgeID(minID); % substitute to original ID
% remove minimal edges
G1 = rmedge(G,find(G.Edges.edgeID==minID));
% check if graph is still connected
isConnected = numel(unique(conncomp(G1)))==1;
if isConnected
G = G1; % remove edge
else
G.Edges.isChecked(G.Edges.edgeID==minID)=1; % mark edges as checked and keep it for next iterations
end
if all(G.Edges.isChecked==1), break; end % terminate loop when all edges were checked
end
问题是这个代码非常缓慢和原始。
你知道如何改进我的代码或一些现成的算法吗?
1条答案
按热度按时间zc0qhyus1#
感谢Matt Timmermans的评论。我只需要: