Appending objects based on link array

I'm having a bit of trouble figuring out the logic for a problem related to particle tracking. Briefly, the particle trajectories have gaps. I've identified which incomplete tracks should be appended to other tracks, and have this information stored in an array like the following:

links = [1 6;
         3 9;
         4 8;
         5 7;
         9 10
         8 12;
         10 11];

What this means is that track 6 should follow track 1, track 9 should follow track 3, and so on. The number of tracks in a "chain" that need to be connected is at minimum 2 but can be longer (it depends on how many gaps there are in the tracks). The output I want is something like this:

t1 = [1,6];
t2 = [3,9,10,11];
t3 = [4,8,12];
t4 = [5,7];

The actual items I want to append are structures, but the details of the appending isn't the problem. What's giving me trouble is how to set up the logic to loop through the links array and append things together, since I need to "follow the chains" to the end and link things from the end backwards to get the complete chain.

I haven't had much luck getting anything to work, but I'll include include a rough idea. Another problem is that I'm not sure what this kind of problem is called, so I haven't had much luck searching for similar questions. If there's a better title for the question that more accurately describes this problem please let me know.

for i = 1:size(links,1)
    child = links(i,2);
    idx = find(links(:,1) == child); % is the child a parent to another track?
    while ~isempty(idx)
        child = links(idx,2); % the next child
        idx = find(links(:,1) == child); % update idx, is there another child in the chain?
    end
    % I'm not sure where to do the appending and how to keep track of
    % what's been appended so far
end

% I have a similar function to append one track structure to another
function c = append(a,b)
    c = [a,b];
end

[Walter Roberson]

have you considered using digraph() and extract connected components?

[Walter Roberson]

Is it possible to have a situation such as

[1 6
 6 9
 6 7
 7 8
 9 10]

which has the chains 1 6 9 10 and 1 6 7 8 both? If so then what output would you want ?

Are the links directional or bidirectional? If the input were

links = [1 6;
         9 3;
         4 8;
         5 7;
         9 10
         8 12;
         10 11];

then would you still have t2 = [3,9,10,11]; or would you instead have [9 3] and [9 10 11] ?

[Zak]

I looked at using digraph() and it looks promising. Running

G = digraph(links(:,1), links(:,2));
plot(G)

gave me this, which is the correct ordering of paths. How would I extract vectors like t1, t2, etc? I think if I could extract those, I might be able to figure out how to loop through them and connect the links.

I've narrowed it down in the processing before this point so that each link can only match to one other link, no forks. The chains are directional. They're positions of particles in time, so a downstream or child track has to come later in time. The first column is always the starting link, and the second on the link that comes next.

Answer 1

[Voss]

links = [1 6;
         3 9;
         4 8;
         5 7;
         9 10;
         8 12;
         10 11];

% make a copy of links, to keep the links variable unchanged.
% C contains the start- and end-point of each link, and it will be updated
% as new links are assimilated
C = links;

% t is a cell array of link vectors, and it will contain the complete links
% (not only start- and end-points)
t = num2cell(C,2);

while true
    
    % find which elements of the second column of C exist in the first 
    % column (match), and where they are in the first column (row)
    [match,row] = ismember(C(:,2),C(:,1));
    
    % if no matches, exit the loop (done)
    if ~any(match)
        break
    end
    
    % take the first match only
    match = find(match,1); % index of first match in 2nd column of C
    row = row(match);      % index of first match in 1st column of C
    
    % append the new end-point, C(row,2), to the end of the link at index
    % 'match' in t
    t{match}(end+1) = C(row,2);
    
    % also update the end-point of the link at index 'match' in C
    C(match,2) = C(row,2);
    
    % remove the now-redundant row from C and corresponding element from t
    C(row,:) = [];
    t(row) = [];
    
    % continue with the next match
    
end

disp(t);

    {[      1 6]}
    {[3 9 10 11]}
    {[   4 8 12]}
    {[      5 7]}

[Zak]

This works, thanks! Makes sense once I see it, but was having trouble figuring it out myself.

For future reference, I did the actual linking using t with something like this:

for i = 1:size(t,1)
    for j = size(t{i},2):-1:2
        fprintf('\tAppend %d to end of %d\n', t{i}(j), t{i}(j-1))
        finalTracks = appendTracks(finalTracks, t{i}(j-1), t{i}(j));
    end
end

[Voss]

You're welcome!