# How to find all possible routes with a given node matrix?

6 views (last 30 days)
Jung Sunghun on 25 Apr 2018
Commented: Jung Sunghun on 20 Oct 2018
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
Jung Sunghun on 15 Oct 2018
Dear Sir,
The constraint is that the node could only be used once in the path.

Bruno Luong on 15 Oct 2018
Edited: Bruno Luong on 15 Oct 2018
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
Jung Sunghun on 15 Oct 2018
I got it. Thank you very much for your invaluable time. Have a great day!

Walter Roberson on 15 Oct 2018
##### 2 CommentsShowHide 1 older comment
Jung Sunghun on 20 Oct 2018
Thank you very much for the kind supporting.