matlab 简化图表,保持连通性

c0vxltue  于 2023-10-23  发布在  Matlab
关注(0)|答案(1)|浏览(168)

我有一些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

问题是这个代码非常缓慢和原始。

你知道如何改进我的代码或一些现成的算法吗?

zc0qhyus

zc0qhyus1#

感谢Matt Timmermans的评论。我只需要:

G = graph(1-R.^2,'omitselfloops');
G = minspantree(G);

相关问题