igraph-help
[Top][All Lists]

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

 From: Szabolcs Horvát Subject: Re: [igraph] Calculating total number of paths between two specific nodes Date: Wed, 16 May 2018 23:58:27 +0200

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