Find paths in graph that satisfy specific condition

I have the following graph:

s=[17,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30];
t=[18,19,20,21,22,23,24,25,26,27,28,29,30,8,7,6,5,4,3,2,1,9,10,11,12,13,14,15,16];
x_pos=[-4,-4,-4,-4,-4,-4,-4,-4,4,4,4,4,4,4,4,4,-1,1,-2,-2,2,2,-3,-3,-3,-3,3,3,3,3];
y_pos=[-7,-5,-3,-1,1,3,5,7,7,5,3,1,-1,-3,-5,-7,0,0,4,-4,4,-4,6,2,-2,-6,6,2,-2,-6];

names={'P','Q','O','N','R','S','T','U','C1','B1','A1','Z','Y','X','V','W','A','C','B','E','D','I','H','F','G','M','L','K','J'};
G=graph(s,t);
h=plot(G,'EdgeLabel',names,'XData',x_pos,'YData',y_pos);

and I want to automate finding specific paths in pairs. I explain the workflow:

1. Define two extremal nodes and find a path between them that passes through a specific edge;
2. Find all other paths that start and end in extremal nodes and cross the first path ONLY in the specified edge.

So for example, I want a path that starts from node 8 and ends in node 5 that passes by edge H (should only be one path); THEN I want to find all paths that start and end in extremal nodes and pass through H but do not cross the first path in any other edges (so it cannot be the same path going from node 7 to node 6, T-I-H-S because it crosses the path in both I and H).

If it is possible to implement such solution, I need it as generic as possible since I would need to iterate it for all edges (not the focus of the question at the moment). Is it possible to have this kind of "conditional pathfinding" in matlab?

[Dyuman Joshi]

Please show what you have you tried yet.

[Kakey Linmart]

I have tried allpath, shortestpathtree and shortestpath, but all of these do not allow for the conditions I want. I looked through the documentation but I cannot find anything that helps my case

Answer 1

[Matt J]

s=[17,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30];
t=[18,19,20,21,22,23,24,25,26,27,28,29,30,8,7,6,5,4,3,2,1,9,10,11,12,13,14,15,16];
x_pos=[-4,-4,-4,-4,-4,-4,-4,-4,4,4,4,4,4,4,4,4,-1,1,-2,-2,2,2,-3,-3,-3,-3,3,3,3,3];
y_pos=[-7,-5,-3,-1,1,3,5,7,7,5,3,1,-1,-3,-5,-7,0,0,4,-4,4,-4,6,2,-2,-6,6,2,-2,-6];

names={'P','Q','O','N','R','S','T','U','C1','B1','A1','Z','Y','X','V','W','A','C','B','E','D','I','H','F','G','M','L','K','J'};
G=graph(s,t);

I have tried allpath, shortestpathtree and shortestpath, but all of these do not allow for the conditions I want.

I don't know why allpath wouldn't work. Once you have a list of all the extremal nodes,

exnodes=find(degree(G)==1)'

exnodes = 1×16

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

it should be a simple matter to loop through all the pairs and find a path containing the given edge H,

pairs=nchoosek(exnodes,2);
H=sort([19,24]);

foundPath=[];
for i=1:height(pairs)
    
   P = allpaths(G,pairs(i,1),pairs(i,2)); 
   P=P{1}(:); %This graph will always have numel(P)=1
   
   if ismember(H, sort([P(1:end-1), P(2:end)],2)  ,'rows' )
     foundPath=P; break
   end
end

foundPath  %contains H=[19,24]

foundPath = 7×1

1 26 20 17 19 24 5

Condition 2 would use a similar loop.

[Kakey Linmart]

Thank you! This did it. I definitely misunderstood what allpath did and thought I could find an out-of-the-box command that would do what I asked. I have modified your suggestion a bit to fit my usecase but I will add it to my question, maybe it will be useful to someone else. Thank you again for your help!