Finding number of independent pathways in a graph
20 views (last 30 days)
I want to find the number of independent pathways between each node pair in a graph. 2 pathways between a node pair is said to be independent if they do not share a common road link. For this we take a node pair, find the shortest path between the nodes, remove all the edges in the shortest path, and find the path again till all paths are found. The maximum number of independent pathways possible between a node pair is equal to the minimum of the degree of the nodes.
I have developed a program for this but this seems to be working slow. Can somebody help me optimse the code.
Graph= graph(O_Node,D_Node,Length); %making graph from nodes and length
Degree=degree(Graph);%degree of nodes as matrix
N_Nodes=size(Graph.Nodes,1);% No of nodes in the graph
Links = nchoosek(1:N_Nodes,2); % All node pairs possible
N_Pass=zeros(size(Links,1),1); %Number of pathways between each node pair
for i=1: size(Links,1) %iterating through each node pair
Graph_Temp=Graph;%creating a temporary graph whose edges will be removed in the subsequent steps
N_Pass(i,1)= min(Degree(Links(i,1),1),Degree(Links(i,2),1)); % maximum number of pathways possible is equal to the minimum of the degree of 2 nodes
for k = 1 : N_Pass(i,1)
Pass= shortestpath(Graph_Temp,Links(i,1),Links(i,2)); %finding the shortest path
else m=m+1;%counting number of pathways
Graph_Temp= rmedge(Graph_Temp,Pass(1:(size(Pass,2)-1)),Pass(2:(size(Pass,2))));% removing all edges inclued in the first shortest path
Christine Tobler on 15 Jul 2021
I'd expect the call to rmedge is the most expensive here. You could instead add edge weights for every edge in the graph, and then instead of modifying the graph, just set the weights of the edges you want to remove to Inf instead.
Sorry I probably won't be able to follow up on this answer, I'm just about to head off on vacation.