How to remove duplicate nodes from generated path and segments inbetween?

I really need help on this. Been at it for a week.

I have a randomly generated path between nodes 1 to 25.

Initial generation: 1 6 7 2 1 6 7 8 9 4 3 2 1 6 7 12 11 16 21 22 23 24 19 20 25

I want to remove all repeated segments and nodes so based on this, the final path I want is:

(1, 6, 7, 12, 11, 16, 21, 22, 23, 24, 19, 20, 25)

How should I do this? Pls help.

Answer 1

[Guillaume]

Seems like you want to delete everything between the first and last occurrence of any identical digit:

path = [1 6 7 2 1 6 7 8 9 4 3 2 1 6 7 12 11 16 21 22 23 24 19 20 25];
while true
   pathvalues = unique(path);
   pathhist = histcounts(path, [pathvalues, Inf]); 
   duplicate = pathvalues(find(pathhist > 1, 1)); %find identical digit     if isempty(duplicate)
      break; %nothing left to remove, exit loop
   end
   occurences = path == duplicate;
   path(find(occurences, 1) : find(occurences, 1, 'last')-1) = []; %delete 1st occurence and anything up to last occurence
end

[Xi Wen Lim]

OMG THANK YOU SO MUCH. THIS SEEMS TO DO EXACTLY WHAT I NEED IT TO DO.

[Xi Wen Lim]

Dear Guillaume,

I have tried this code with 100 nodes. So the path generated has about 400 or so entries at times. But the code seems to not work, by that I mean it never finishes running.

May I know what is wrong?

[Guillaume]

Can you attach an example of a path where it runs forever?

I can't see why that would happen.

[Xi Wen Lim]

Sorry I didn't see this message earlier.

Path = [1 2 3 4 5 6 16 26 27 17 16 26 36 46 56 57 58 59 69 79 78 77 67 57 47 46 45 55 54 64 65 75 85 84 83 93 94 95 85 84 94 93 83 82 81 91 92 82 72 73 83 84 74 64 65 75 76 66 65 55 45 46 36 26 27 17 18 8 9 19 18 17 27 28 38 39 40 50 60 59 58 48 38 37 47 48 58 57 56 66 67 77 87 86 76 75 85 86 87 97 98 99 89 88 78 79 80 70 60 50 40 30 29 39 38 37 36 35 45 46 47 37 36 26 16 15 14 24 23 22 12 2 3 4 5 15 14 4 3 2 12 22 23 13 14 15 25 26 36 46 56 57 67 77 78 68 69 70 60 59 69 70 80 90 89 88 98 97 87 88 78 77 76 66 67 77 78 68 67 57 47 48 49 59 69 70 80 90 100]

[Guillaume]

Oh, there was a big bug in the code where I found which value was duplicated. I've edited my answer to fix the bug.

The lines

     pathhist = histcounts(path, [unique(path), Inf]); 
     duplicate = path(find(pathhist > 1, 1)); %find identical digit

have been changed to

     pathvalues = unique(path);
     pathhist = histcounts(path, [pathvalues, Inf]); 
     duplicate = pathvalues(find(pathhist > 1, 1)); %find identical digit

Answer 2

[Teja Muppirala]

If you have R2015b or newer, there are built-in functions to do this. In particular, SHORTESTPATH.

path  = [1 6 7 2 1 6 7 8 9 4 3 2 1 6 7 12 11 16 21 22 23 24 19 20 25];

N = numel(path);
G = sparse(path(1:end-1),path(2:end),1,N,N); %Make adjacency matrix
G = digraph(G); 

pathOut = shortestpath(G, path(1), path(end),'Method','unweighted')

The answer is:

 pathOut =

     1     6     7    12    11    16    21    22    23    24    19    20    25