Finding number of independent pathways in a graph

8 次查看（过去 30 天）
Hari
Hari 2021-7-15
回答： Christine Tobler 2021-7-15
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
z=0;
m=0;
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
z=z+1;
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
if isempty(Pass)
break
else m=m+1;%counting number of pathways
end
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
Pass=[];
end
N_Pass_Cal(z,1)= m;
m=0;
end

请先登录，再回答此问题。

回答（1 个）

Christine Tobler
Christine Tobler 2021-7-15
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.

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by