| In the usual matrix multiplication of A[i=1,...,n by j=1,...,p]
and B[i=1,...,p by j=1,...,m] you get the result
C[i,j] = sum over k=1,...,p of (product of A[i,k] and B[k,j])
You can generalize this by substituting other operations instead
of "sum" and "product".
For the square adjacency matrix A, let C represent adjacency in
exactly two steps. Then you want C[i,j] to be 1 if and only if
at least one of the pairs A[i,k] and A[k,j] (for k=1,...,n) are
both 1. I.e.,
C[i,j] = logical or over k=1,...,n of (logical and of A[i,k] and A[k,j])
Now the logical and you actually get by regular multiplication, i.e.,
"logical and of" and "product of" are the same for values of 0,1.
However, "logical or" and "sum" don't quite match up. They do if you
consider {0,any positive} instead of {0,1}. So in terms of regular
matrix multiplication, if C = A^2 then the nonzero elements C[i,j]
are precisely where you can get from i to j in exactly two steps.
Then A + A^2 represents whether you can get from i to j in one or
two steps. If you repeat this, you get a sequence of matrices
A<0> = A, A<1>, A<2>, ..., where A<n+1> = A<n> + (A<n> * A<n>),
such that a nonzero A<0>[i,j] represents an edge (directly adjacent),
a nonzero A<1>[i,j] represents reachability along one or two consecutive
edges, a nonzero A<2>[i,j] represents reachability along one, two,
three, of four consecutive edges, ..., in general a nonzero A<s>[i,j]
represents reachability along one, two, ..., 2^s consecutive edges.
When 2^s >= n (or is it n-1?) you stop, and the nonzero entries
represent reachability.
Of course, you can do the above with Boolean arithmetic instead of
integer arithmetic; then nonzero elements will always be 1.
Check the literature for efficient implementations. Is this
Worshall's [sp?] method?
Note the above does not require the graph to be acyclic. Perhaps
"acyclicy" can be exploited to gain efficiency.
To topologically sort given the reachability matrix for a directed
acyclic graph, at each step just choose any node which either has
no predecessors, or all of whose predecessors have already been
chosen. Repeat until every node has been selected; the sequence
of choices will do.
Dan
|