I have a bidirectional network, that is, a network where flow exists both from i->j and j->i. And I want to calculate the number of simple paths between each [i,j] and report in matrices according to the path length, that is, for each [i,j] pair there's a certain number of simple paths of length 2, 3, 4, etc, and I would like to calculate this and have the results being reported in: a reporting matrix of the number of simple paths of length 2 between i and j; a reporting matrix of the number of simple paths of length 3 between i and j, etc....
The solution I found was to create a code that would look to the original input matrix and search for paths of length x from i->n by looking to the connections of i with the other variables, then these with the other variables excluding i, and so on for x+1 variables until we got to x->n. E.g. for length two paths will look for i->x connection and any x->n connection. If this is true then there's a length two simple path between i and n. If the approach was left like this, when analysing bidirectional matrices or matrices with self-loops, the code would count self-loops has simple paths, and pass more than once by the same vertex. To solve this problem, in the conditions set in the code another parameter need to be verified. This parameter is a restriction on the assignment of the variables of the original matrix to our general variables, that is, when assigning a new general variable for the path search, the variable assigned cannot be one already assigned in that path search to another general variable: * when looking for a path of length 2 between iand n, the variable to be assigned to x cannot be the one already assigned to i (this eliminates the self-loops from counting in as paths), and in the same way n cannot be assigned a variable already used either by i or x (this eliminates de reporting of cases of i->x->i has paths of length 2 and also eliminates de reporting of paths passing more than once by the same variable [i->x->x2->i for 3length paths e.g.]). So the code I use is basically this:
#the adjacency matrix
> MM<-matrix(c(1,1,0,0,0,1,1,1,1,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,1), 5, byrow=T)
> colnames(MM)<-c("A", "B", "C", "D", "E")
> row.names(MM)=colnames(MM)
> MM
A B C D E
A 1 1 0 0 0
B 1 1 1 1 0
C 0 1 1 1 0
D 0 1 0 1 1
E 0 0 0 1 1
#this is the reporting matrix where the results will be reported
> MMres2<-matrix(rep(0,length(MM)), sqrt(length(MM)))
> colnames(MMres2)=colnames(MM)
> row.names(MMres2)=row.names(MM)
#this is the code for the calculation and report of simple paths of lenght 2
> for(i in 1:dim(MM)){
for(j in 1:dim(MM)){
for(k in 1:dim(MM)){
if(MM[i,j]==1 & MM[j,k]==1 & j!=i & k!=i & k!=j){
MMres2[i,k]=MMres2[i,k]+1
}
}
}
}
#the reported results
> MMres2
A B C D E
A 0 0 1 1 0
B 0 0 0 1 2
C 1 1 0 2 1
D 1 0 1 0 0
E 0 1 0 0 0
If I want to calculate the number of simple paths of length 3 between any i->n we just need to had the condition of [x2,n]==1 and make sure we restrict the new variable to not be equal to any of the previously assigned ones.
And here, at last, lays my problem. I don't want to simply calculate the number of paths of length 2 or three or four, but all the possible (maximum possible length of a path is the total number of variables minus 1). Obviously, having a code for each path of length x for each matrix would be cumbersome, and for matrices with ever higher N number of variables, the more cumbersome would it be to create such code. To simplify this, the ideal solution would be to develop a code that would look for all pairs i and j and and calculate the number of paths between each for all the possible number of links per path up to paths of tot.var-1 links (that is, the maximum number of links on a path between each pair of i and j).
Take again the M2 matrix, the ideal code would look for the existence of a link between i and a x variable and then between x variable and j, and in the case of the condition being reported, it would report the result each time a path was found:
[i,x]==1 & [x’,j]==1 -> Res.mat[i,j] + 1
Where, x and x’ are any (and any number) of variables between i and j. The point that differs this approach from the original above is that here x can be a multitude of variables, that is, in one iteration, when looking for a path of 2 links, x will be one variable, while one looking for a path of 3 links, x will be two variables and so forth.
E.g.:
For a path of length 2:
[i,xa]==1 & [xa,j]==1 -> Res.mat2[i,j] +1
For a path of length 3:
[i,xa]==1 & [xa,xb]==1 & [xb,j]==1 -> Res.mat3[i,j] +1
For a path of length 4:
[i,xa]==1 & [xa,xb]==1 & [xb,xc]==1 & [xc,j]==1 -> Res.mat4[i,j] +1
In this code, x would progressively assume all the other variables excluding i and j, and reporting each path for the respective reporting matrix, the ones of length two for the length2 reporting matrix, etc.
Sorry for the very, very long post, this is something I've been searching for long and talked with colleagues and no one seems to either understand or help me and that's why I made it in a long post to try and be the clearest possible.
So, anyone knows a how I can make this?