MATLAB Answers

How to find all possible paths from point A to B in any direction in a matrix?

40 views (last 30 days)
Mohammed Aasim Shaikh
Mohammed Aasim Shaikh on 27 Sep 2020
Edited: Bruno Luong on 20 Nov 2020 at 18:40
I have a MXN matrix and I select two given points A and B. How do I find and store all the possible unique paths form A to B? There are no constraint on which direction I can go from the current point, it can be up, down, left, right, or diagonal (in all four directions).

  14 Comments

Walter Roberson
Walter Roberson on 27 Sep 2020
MATLAB permits recursive functions, using the same syntax as most other programming languages -- which is to say that you just place a call to the function you are in the middle of defining.
The limitation on recursion in MATLAB is that by default only 500 levels of recursion are permitted. However, you can change that by using
set(0,'Rec​ursionLimi​t',N)
where N is your new depth limit. Be warned that if you do this, then there is a risk of crashing the computation by running out of stack space, as each call takes up memory (a copy of all local variables must be saved.)
John D'Errico
John D'Errico on 29 Sep 2020
The important point to reconize is just the sheer enormity of the number of all possilbe paths, even for a small matrix.
Almost always there are better ways to solve a problem than a complete sampling of the space you wish to investigate. This is why optimization methods exist, to help you to avoid brute force sampling schemes.

Sign in to comment.

Accepted Answer

Bruno Luong
Bruno Luong on 29 Sep 2020
Edited: Bruno Luong on 20 Nov 2020 at 8:00
Tiny matrix of size 4 x 3.
All paths of two opposite corners:
  • 38 paths for 4-connectivity,
  • 2922 paths for 8-connectivity
clear
close all
m=4; n=3;
% Adjacent matrix of a graph of 4-connected grid of size m x n
[X,Y] = meshgrid(1:n,1:m);
mxn = numel(X);
I = sub2ind(size(X),Y(1:end-1,:),X(1:end-1,:));
J = I+1;
A = sparse(I,J,1,mxn,mxn);
I = sub2ind(size(X),Y(:,1:end-1),X(:,1:end-1));
J = I+size(X,1);
A = A + sparse(I,J,1,mxn,mxn);
A4 = A + A';
% Adjacent matrix of a graph of 8-connected grid of size m x n
I = sub2ind(size(X),Y(1:end-1,1:end-1),X(1:end-1,1:end-1));
J = I+size(X,1)+1;
A = A + sparse(I,J,1,mxn,mxn);
I = sub2ind(size(X),Y(2:end,1:end-1),X(2:end,1:end-1));
J = I+size(X,1)-1;
A = A + sparse(I,J,1,mxn,mxn);
A8 = A + A';
% source and destination
is = 1; js = 1;
id = m; jd = n;
s = sub2ind([m,n],is,js);
d = sub2ind([m,n],id,jd);
allp4 = AllPath(A4, s, d);
PlotandAnimation(4, A4, allp4, [m,n]);
allp8 = AllPath(A8, s, d);
PlotandAnimation(8, A8, allp8, [m,n]);
%%
function PlotandAnimation(nc, A, allp, sz)
fprintf('%d-connected %d x %d\n', nc, sz);
% Plot and animation
figure
[i,j] = ind2sub(sz,1:prod(sz));
nodenames = arrayfun(@(i,j) sprintf('(%d,%d)', i, j), i, j, 'unif', 0);
G = graph(A);
h = plot(G);
labelnode(h, 1:prod(sz), nodenames)
th = title('');
colormap([0.6; 0]*[1 1 1]);
E = table2array(G.Edges);
E = sort(E(:,1:2),2);
np = length(allp);
for k=1:np
pk = allp{k};
pkstr = nodenames(pk);
s = sprintf('%s -> ',pkstr{:});
s(end-3:end) = [];
fprintf('%s\n', s);
Ek = sort([pk(1:end-1); pk(2:end)],1)';
b = ismember(E, Ek, 'rows');
set(h, 'EdgeCData', b, 'LineWidth', 0.5+1.5*b);
set(th, 'String', sprintf('%d-connected, path %d/%d', nc, k, np));
pause(0.1);
end
end
%%
% EDIT: better code available in the comment
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

  1 Comment

Bruno Luong
Bruno Luong on 19 Nov 2020 at 20:26
I update here the function Allpath to work on directgraph as well. For dirgraph, if t parameter is NaN this function returns all the path started from s and ended to leaf.
NOTE: It continues to work on undirect graph.
function p = AllPath(A, s, t)
% Find all paths from node #s to node #t
% INPUTS:
% A is (n x n) ajadcent matrix (preferable sparse)
% it can be symmetric (graph) or unsymmetric (digraph)
% s, t are node number, in (1:n)
% NOTE: for digraph, if t is NaN, all paths started from s and ended at a
% leaf are returned
% 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.
%
% Author: <Bruno Luong> surnamename@yahoo.xx
%
if isgraph(A)
% graph
G = graph(A);
[~, d] = shortestpath(G, s, t);
if isfinite(d)
p = AllPathHelper(A, s, t);
else
p = {};
end
else
% digraph
if nargin < 3 || isempty(t)
t = NaN;
end
tnotprovide = ~isfinite(t);
if tnotprovide
% connect the leaf to a single dummy node t
n = size(A,2);
[ss,tt] = find(A);
leaf = setdiff(tt,ss);
A(n+1,n+1) = 0;
A(:,n+1) = sparse(leaf, 1, 1, n+1, 1);
t = n+1;
end
G = digraph(A);
[~, d] = shortestpath(G, s, t);
if isfinite(d)
p = AllPathHelper(A.', s, t);
if tnotprovide
% remove the dummy node
for k=1:length(p)
p{k} = p{k}(1:end-1);
end
end
else
p = {};
end
end
end % AllPath
%%
function tf = isgraph(A)
A = spones(A);
tf = nnz(A-A')==0;
end % isgraph
%%
function p = AllPathHelper(AT, s, t)
% Find all paths from node #s to node #t
% INPUTS:
% AT is (n x n) transposed of the 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 = AT(:,s);
As(s) = 0;
if nnz(As)==0
return
end
neig = find(As);
AT(:,s) = 0;
AT(s,:) = 0;
neig = reshape(neig,1,[]);
for n=neig
p = [p; AllPathHelper(AT,n,t)]; %#ok
end
for k=1:length(p)
p{k} = [s, p{k}];
end
end % AllPathHelper

Sign in to comment.

More Answers (1)

Stijn Haenen
Stijn Haenen on 29 Sep 2020
With this script you got all possible paths, but it is very slow so you have to optimize it (shouldnt be that hard but dont have time for it anymore).
The script tries every path by going in any of the 8 directions at every step until it reaches its goal position.
clear
a=[1 2 3; 4 5 6];
start1=1;
start2=1;
goal1=2;
goal2=2;
abackup=a;
data=[];
for i=10^(numel(a)-1):10^numel(a)-1
pos1=start1;
pos2=start2;
route_i=num2str(a(pos1,pos2));
j=num2str(i);
abackup=a;
abackup(pos1,pos2)=NaN;
for n=1:numel(j)
if j(n)=='1'
try
if ~isnan(abackup(pos1-1,pos2))
pos1=pos1-1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='2'
try
if ~isnan(abackup(pos1-1,pos2+1))
pos1=pos1-1;
pos2=pos2+1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='3'
try
if ~isnan(abackup(pos1,pos2+1))
pos2=pos2+1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='4'
try
if ~isnan(abackup(pos1+1,pos2+1))
pos1=pos1+1;
pos2=pos2+1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='5'
try
if ~isnan(abackup(pos1+1,pos2))
pos1=pos1+1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='6'
try
if ~isnan(abackup(pos1+1,pos2-1))
pos1=pos1+1;
pos2=pos2-1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='7'
try
if ~isnan(abackup(pos1,pos2-1))
pos2=pos2-1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='8'
try
if ~isnan(abackup(pos1-1,pos2-1))
pos1=pos1-1;
pos2=pos2-1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
end
end
unique(data)

  0 Comments

Sign in to comment.

Products


Release

R2020a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!