Is this graph algorithm more efficient?

Question

Suppose we are given a digraph A. We need to calculate its connectivity digraph B.

I conceived two algorithms:

1.

• Set X = A.

• Loop

• Set Y = X*A united with identity

• Stop the loop if Y = X

• Set X = Y

• End loop

• B = X

2.

• Set X = A. [Or instead "X = A united with identity" and remove "united with identity" in the third step?]

• Loop

• Set Y = X*X united with identity [or should it be Y = (X united with identity)*(X united with identity)?]

• Stop the loop if Y = X

• Set X = Y

• End loop

• B = X

I think that the algorithms are equivalent but the second one is faster.

Are they really calculating connectivity and are really equivalent?

Is the second algorithm faster not only for incidence matrix representation but also for hash-map or like this representation of digraphs?

Is there an even more efficient algorithm?

Answer 1

You are asking a lot of questions. Let me answer some of them.

Let us denote the contents of the Boolean matrix $X$ after $t$ iterations by $X^{(t)}$. The first algorithm uses the recurrence $$ \begin{align*} &X^{(0)}(i,j) = A(i,j), \\ &X^{(t+1)}(i,j) = X^{(t)}(i,j) \lor \bigvee_k \bigl(X^{(t)}(i,k) \land A(k,j)\bigr). \end{align*} $$ You can prove by induction that $X^{(t)}(i,j)$ is true iff there is a directed path from $i$ to $j$ of length at most $t+1$.

The second algorithm uses the recurrence $$ \begin{align*} &X^{(0)}(i,j) = A(i,j), \\ &X^{(t+1)}(i,j) = X^{(t)}(i,j) \lor \bigvee_k \bigl(X^{(t)}(i,k) \land X^{(t)}(k,j)\bigr). \end{align*} $$ You can prove by induction that $X^{(t)}(i,j)$ is true iff there is a directed path from $i$ to $j$ of length at most $2^t$.

Since $2^t$ grows much faster than $t+1$, the second algorithm will use less iterations. The worst case number of iterations in the first algorithm is $n$, whereas in the second algorithm this goes down to $O(\log n)$.