Re: [igraph] Calculating total number of paths between two specific nodes

[Szabolcs Horvát]

Your graph is a DAG, so you can use the kth power of the adjacency matrix to count paths of length k between nodes. Furthermore, since the graph is a DAG, the adjacency matrix is nilpotent, i.e. some big enough power is zero.

You basically need to compute A + A^2 + A^3 + ..., until the power becomes zero. This matrix gives you the number of paths between any two points.

On Wed, 16 May 2018 at 23:03, Xu, Yanjie <address@hidden> wrote:

Dear developers of igraph,

 

I am currently using igraph in r to analyse directed acyclic graphs. One of my task is calculating number of all possible paths between the “start” and “end” nodes. With igraph, I can get a list of all possible paths (e.g., from node 1 to node 81) with the code below:

 

>>all_simple_paths(net, 1, 81)

 

Then I summarize how many paths (n) we have:

 

>>n<-length(all_simple_paths(net, 1, 81))

 

This works we my network has around 15 nodes, but we the number of nodes increase, it takes days to calculate “n” for a single network. I have hundreds of networks waiting for calculation. Do you have an idea whether there is a quicker way to get the number of possible paths between two specific nodes? Many many thanks!

 

Best regards,

Yanjie

 

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help