MATLAB: How to find all possible routes with a given node matrix

all possible routepath planningroute

Hello,
I am trying to write a function to find all possible routes from the Start node, 6, to the Goal node, 21, with the given node matrix, A, as shown in the below.
A =
     1     6
     1    23
     2     3
     2     4
     2     5
     3     2
     4     2
     4     7
     5     2
     5    11
     6     1
     6    26
     7     4
     7     8
     8     7
     8     9
     8    24
     9     8
     9    23
    10    11
    10    13
    10    15
    10    16
    11     5
    11    10
    12    13
    12    14
    13    10
    13    12
    13    24
    14    12
    14    19
    15    10
    15    17
    16    10
    16    17
    16    18
    17    15
    17    16
    17    25
    18    16
    18    19
    18    22
    19    14
    19    18
    19    20
    20    19
    21    22
    21    27
    22    18
    22    21
    22    25
    23     1
    23     9
    24     8
    24    13
    25    17
    25    22
    26     6
    27    21
I would like to build a function which results the following outputs.
[6,1,23,9,8,7,4,2,5,11,10,15,17,25,22,21]
[6,1,23,9,8,7,4,2,5,11,10,15,17,16,18,22,21]
[6,1,23,9,8,7,4,2,5,11,10,16,17,25,22,21]
[6,1,23,9,8,7,4,2,5,11,10,16,18,22,21]
[6,1,23,9,8,24,13,10,15,17,25,22,21]
[6,1,23,9,8,24,13,10,16,17,25,22,21]
[6,1,23,9,8,24,13,10,16,18,22,21]
[6,1,23,9,8,24,13,12,14,19,18,16,10,15,17,25,22,21]
[6,1,23,9,8,24,13,12,14,19,18,16,17,25,22,21]
[6,1,23,9,8,24,13,12,14,19,18,22,21]
Thank you very much for your invaluable time to help on this problem.
Best regards,
Sunghun Jung

Best Answer

I found actually 13 paths, more than the 10 you have listed:
[6 1 23 9 8 7 4 2 5 11 10 13 12 14 19 18 16 17 25 22 21]
[6 1 23 9 8 7 4 2 5 11 10 13 12 14 19 18 22 21]
[6 1 23 9 8 7 4 2 5 11 10 15 17 16 18 22 21]
[6 1 23 9 8 7 4 2 5 11 10 15 17 25 22 21]
[6 1 23 9 8 7 4 2 5 11 10 16 17 25 22 21]
[6 1 23 9 8 7 4 2 5 11 10 16 18 22 21]
[6 1 23 9 8 24 13 10 15 17 16 18 22 21]
[6 1 23 9 8 24 13 10 15 17 25 22 21]
[6 1 23 9 8 24 13 10 16 17 25 22 21]
[6 1 23 9 8 24 13 10 16 18 22 21]
[6 1 23 9 8 24 13 12 14 19 18 16 10 15 17 25 22 21]
[6 1 23 9 8 24 13 12 14 19 18 16 17 25 22 21]
[6 1 23 9 8 24 13 12 14 19 18 22 21]
Test code:
A =[ 1     6
     1    23
     2     3
     2     4
     2     5
     3     2
     4     2
     4     7
     5     2
     5    11
     6     1
     6    26
     7     4
     7     8
     8     7
     8     9
     8    24
     9     8
     9    23
    10    11
    10    13
    10    15
    10    16
    11     5
    11    10
    12    13
    12    14
    13    10
    13    12
    13    24
    14    12
    14    19
    15    10
    15    17
    16    10
    16    17
    16    18
    17    15
    17    16
    17    25
    18    16
    18    19
    18    22
    19    14
    19    18
    19    20
    20    19
    21    22
    21    27
    22    18
    22    21
    22    25
    23     1
    23     9
    24     8
    24    13
    25    17
    25    22
    26     6
    27    21];
p = gallpaths(A,6,21);
for k=1:length(p)
    fprintf('%s\n', mat2str(p{k}));
end
Using this function GALLPATHS I made
function p = gallpaths(A,start,last)
% find all direct paths from start to last
% A is (n x 2) each row is an edges
A = sortrows(A);
b = true(size(A,1),1);
p = gapengine(A,b,start,last);
end
function p = gapengine(A,b,start,last)
% recursive engine
if start==last
    p = {last};
else
    bs = A(:,1) == start;
    next = A(bs & b,2);
    p = {};
    b(bs) = false;
    for k=1:length(next)
        i = next(k);
        pk = gapengine(A,b,i,last);
        pk = cellfun(@(p) [start, p], pk, 'unif', 0);
        p = [p, pk];
    end
end
end
Related Question