Find all the possibles paths between 2 nodes in undirected graph

Question

Sara 2020-7-27

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/571321-find-all-the-possibles-paths-between-2-nodes-in-undirected-graph

编辑： Bruno Luong 2020-7-28

Hello, I am trying to find all "possible" paths between two nodes, in an undirected graph, using an adjacency matrix(n*n), where n is the number of nodes.

This matrix (n*n) represents the connection between graph nodes, if its value equal to 1 there is an edge , and there isn't an edge if the value is zero.

The restriction of making a path "possible":

1) in each path, a node must not be visited more than once.

2) in each path, an edge must not be visited more than once.

4 个评论
显示 2更早的评论隐藏 2更早的评论

Walter Roberson 2020-7-28

Are you trying to calculate Centrality ? There is available code for that.

Sara 2020-7-28

I want to simulate a proposal that i found in a paper in this proposal the authors calculates all possible paths than find the best one (thier idea), i need to simulate that to compare its results with mine,

请先登录，再进行评论。

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

Answer 1

Bruno Luong 2020-7-27

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/571321-find-all-the-possibles-paths-between-2-nodes-in-undirected-graph#answer_471631

编辑：Bruno Luong 2020-7-28

在 MATLAB Online 中打开

Test script

% Generate random undirect graph
% https://www.mathworks.com/matlabcentral/answers/563732
n = 10; % number of nodes
maxDeg = 4;
M=rand(n);
M=0.5*(M+M');
S1=sort(M,1,'descend');
S2=sort(M,2,'descend');
T=max(S1(maxDeg,:),S2(:,maxDeg));
A=M>=T;
G=graph(A);
% Test
plot(G);
st = randperm(n,2); % pick a random pair of nodes
p = AllPath(A, st(1), st(2)); ; % function defined in mfile below 
fprintf('--- test ---\n');
for k=1:size(p,1)
    fprintf('path #%d: %s\n', k, mat2str(p{k}));
end

Result for this graph, s=1, and t=10:

path #1: [1 6 10]
path #2: [1 9 3 4 5 8 10]
path #3: [1 9 3 8 10]
path #4: [1 9 8 10]

The result is still managable for n<=30, I get about few thousand paths listed with such random generated graph. Hard to know how the number of path scaled up with N if the degree of the graphe is bounded. My intuition is the number of paths more or less the number of partitions of N, according to Maranujan, it's ~ exp(sqrt(N)).

Put this on the mfile AllPath.m or at end of the test script above

%%
function p = AllPath(A, s, t)
% Find all paths from node #s to node #t
% INPUTS:
%   A is (n x n) symmetric ajadcent matrix
%   s, t are node number, in (1:n)
% OUTPUT
%   p is M x 1 cell array, each contains array of
%   nodes of the path, (it starts with s ends with t)
%   nodes are visited at most once.
if s == t
    p =  {s};
    return
end
p = {};
As = A(:,s)';
As(s) = 0;
neig = find(As);
if isempty(neig)
    return
end
A(:,s) = [];
A(s,:) = [];
neig = neig-(neig>=s);
t = t-(t>=s); 
for n=neig
    p = [p; AllPath(A,n,t)]; %#ok
end
p = cellfun(@(a) [s, a+(a>=s)], p, 'unif', 0);
end %AllPath

3 个评论
显示 1更早的评论隐藏 1更早的评论

Bruno Luong 2020-7-28

编辑：Bruno Luong 2020-7-28

在 MATLAB Online 中打开

It's odd because you are the person who asked and accepted my answer in https://www.mathworks.com/matlabcentral/answers/563732 where the code is unchanged.

Can you show the result of these commands when the error occurs