Find all the possibles paths between 2 nodes in undirected graph
5 views (last 30 days)
Show older comments
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 Comments
Walter Roberson
on 28 Jul 2020
Are you trying to calculate Centrality ? There is available code for that.
Accepted Answer
Bruno Luong
on 27 Jul 2020
Edited: Bruno Luong
on 28 Jul 2020
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 Comments
Bruno Luong
on 28 Jul 2020
Edited: Bruno Luong
on 28 Jul 2020
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
size(M)
size(S1)
size(S2)
?
It actually doesn't matter, you need to replace G and A by your graph then run the rest of the code.
More Answers (0)
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!