Matrix operations to enumerate all paths through n-partite graph

Question

I have an n-partite (undirected) graph, given as an adjacency matrix, for instance this one here:

  a b c d
a 0 1 1 0
b 0 0 0 1
c 0 0 0 1
d 0 0 0 0

I would like to know if there is a set of matrix operations that I can apply to this matrix, which will result in a matrix that "lists" all paths (of length n, i.e. through all the partitions) in this graph. For the above example, there are paths a->b->d and a->c->d. Hence, I would like to get the following matrix as a result:

a b c d
1 1 0 1
1 0 1 1

The first path contains nodes a,b,d and the second one nodes a,c,d. If necessary, the result matrix may have some all-0 lines, as here:

a b c d
1 1 0 1
0 0 0 0
1 0 1 1
0 0 0 0

Thanks!

P.S. I have looked at algorithms for computing the transitive closure, but these usually only tell if there is a path between two nodes, and not directly which nodes are on that path.

Answer 1

One thing you can do is to compute the nth power of you matrix A. The result will tell you how many paths there of length n from any one vertex to any other.

Now if you're interested in knowing all of the vertices along the path, I don't think that using purely matrix operations is the way to go. Bearing in mind that you have an n-partite graph, I would set up a data structure as follows: (Bear in mind that space costs will be expensive for all but small values.)

Each column will have one entry of each of the nodes in our graph. The n-th column will contain 1 in if this node is reachable on the n-th iteration from our designated start vertex or start set, and zero otherwise. Each column entry will also contain a list of back pointers to the vertices in the n-1 column which led to this vertex in the nth column. (This is like the viterbi algorithm, except that we have to maintain a list of backpointers for each entry rather than just one.) The complexity of doing this is (m^2)*n, where m is the number of vertices in the graph, and n is the length of the desired path.

I'm a little bit confused by your top matrix: with an undidrected graph, I would expect the adjacency matrix to be symmetric.

Answer 2

No, There is no pure matrix way to generate all paths. Please use pure combinatorial algorithms.

'One thing you can do is to compute the nth power of you matrix A. The result will tell you how many paths there of length n from any one vertex to any other.'

The power of matriax generates walks not paths.