Find all the possibles paths between 2 nodes in undirected graph

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.

[John D'Errico]

Anytime I see someone asking a question like finding ALL possible paths in a graph (given this is a problem that will grow exponentially large) makes me wonder if the correct question is really being asked. Actually, it will grow factorially fast.

While I know that is what you think you want, you might want to consider if there is a better solution. Very often such requests for all paths are a way to use brute force to solve for an optimal solution to some problem. In those cases, optimixatino in some form is often a better choice.

[Bruno Luong]

What happens to you guys lately, I have impression half of the world is working on graph.

[Walter Roberson]

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

[Sara]

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]

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

[Sara]

Thank you so much but i have this problem how can i solve it

Error using max

Matrix dimensions must agree.

Error in path_ex (line 9)

T=max(S1(maxDeg,:),S2(:,maxDeg));

[Bruno Luong]

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.

[Sara]

Sir, Thank you very much it works.