# Finding number of independent pathways in a graph

20 views (last 30 days)
Hari on 15 Jul 2021
Answered: Christine Tobler on 15 Jul 2021
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

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.

### Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

### Community Treasure Hunt

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

Start Hunting!

Translated by