[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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,



igraph-help mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]