Find paths in graph that satisfy specific condition
7 views (last 30 days)
Show older comments
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:
- Define two extremal nodes and find a path between them that passes through a specific edge;
- 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?
2 Comments
Dyuman Joshi
on 19 Feb 2024
Edited: Dyuman Joshi
on 22 Feb 2024
Please show what you have you tried yet.
Accepted Answer
Matt J
on 19 Feb 2024
Edited: Matt J
on 19 Feb 2024
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)'
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]
Condition 2 would use a similar loop.
More Answers (0)
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!