# Finding number of independent pathways in a graph

조회 수: 6(최근 30일)
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)
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 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.

댓글을 달려면 로그인하십시오.

### Community Treasure Hunt

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

Start Hunting!

Translated by