I am interested in computing total number of simple paths(no node repeated) between two nodes in a graph(sparse, directed and contains cycles). The graph is a strongly connected component.
I initially tried using matrix multiplication, where I raised the adjacency matrix to all powers from 2 through n-1, n being the number of nodes. However this fails because of cycles in graph. For a DAG just computing all these powers and summing them up will do the job.
Unfortunately this question is highly non-trivial on arbitrary graphs. There is an analytical method but it requires explicit calculations and thus cannot provide generic answers. It consists in weighting each edge leaving a node by a variable x_node. Then consider these variables to be commute with one another and square to zero. Powers of the so-weighted adjacency matrix generate the simple paths. This adjacency matrix is known as the nilpotent adjacency matrix of the graph and the variables live in a Clifford algebra (see the litterature by R. Schott). As I mentioned earlier this method is unfortunately largely useless on sizeable graphs since it requires actual matrix powers to be analytically calculated. I hope to be proven wrong on this point though.
There is no efficient algorithm for this problem.
The problem of counting the number of simple paths from vertex s to t is #P-complete. Therefore, you cannot expect a polynomial-time algorithm that will work in general. See, e.g., https://cstheory.stackexchange.com/q/20246/5038, https://stackoverflow.com/a/5570751/781723, https://cs.stackexchange.com/q/423/755.
Time to try to find some way to avoid solving this problem, or making do with an approximation algorithm, or something.
