| Note that the graph is a DAG (directed acyclic graph), if it weren't for
the edges that connect a node to itself.
Let there be N nodes, and form the NxN matrix A, where A(i,j) = 1
if there is an edge connecting node i to node j, and zero otherwise.
Now, the matrix product AxA = B represents the two-step paths:
B(i,j) is the number of two-step paths from node i to node j.
In general, the elements in the m-th power of the matrix (i.e., A^m)
represent the number of m-step paths from node i to node j.
Thus, A+A^2+A^3+...+A^N gives the total number of paths between nodes.
Usually, the matrix multiplication is done over the field (OR,AND) --
instead of (+,*) -- so that the above formulation would yield boolean
elements that just indicate whether there is such a path. And the
matrix multiplications and additions can be stopped after it no longer
affects the sum.
Because the algorithm must allow for the insertion and removal of nodes
(and presumably edges), an alternative approach is warranted. The problem
is roughly equivalent to a topological sort. If the determination of
whether one node follows another need not be very fast, a depth-first
search (over the graph) could be used.
Other ideas, anyone?
|
| It seems to me that it's feasible to count all possible paths. Keep
track of
n(X,Y) = number of paths from node X to node Y
for all nodes X and Y.
If a node N is added, create n(Q,N) and n(N,Q) for all existing nodes Q,
and set them all to zero. Then,
whenever the paths in this diagram exist:
W -------> X -------> N -------> Y -------> Z
n(W,X) n(X,N) n(N,Y) n(Y,Z)
set n(X,N) = 1
set n(N,Y) = 1
increase n(W,N) by n(W,X)
increase n(N,Z) by n(Y,Z)
increase n(W,Y) by n(W,X)
increase n(X,Z) by n(Y,Z)
increase n(W,Z) by n(W,X)*n(Y,Z)
Deletion of node N: reverse the increases, and throw away all n(X,N)'s
and n(N,Y)'s.
Possible implementation: for each node N, keep lists of:
all the nodes X for which n(X,N) > 0, and all the values n(X,N)
all the nodes Y for which n(N,Y) > 0, and all the values n(N,Y)
John
[ Note the similarity of "increase n(W,Z) by n(W,X)*n(Y,Z)" to matrix
multiplication (see 530.1). ]
|
| [for those still following this after the small hiatus...]
re: .4 - Haven't tried this, but it looks as though it has an
advantage in space, if not time, over matrix
multiplication.
re: .1 - Assuming that we'd wish to stop the multiplication
(using (OR, AND)) as quickly as possible, are there
any *quick* algorithms that can tell:
. whether two boolean matrices are identical,
i.e. does A^n = A^(n+1), or
. whether the next multiplication won't change
the matrix, i.e. given A^n, can we tell quickly
whether A^(n+1) will equal A^n?
|