1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The usual rule is one question per post. $\endgroup$ – Yuval Filmus Dec 28 '17 at 8:24
2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ It is obvious if we represent graphs as 0/1 matrix. But with graphs represented in another way, does decrease of the number of iterations lead to decreasing the actual number of operations? $\endgroup$ – porton Dec 28 '17 at 12:12
  • $\begingroup$ This issue isn't addressed in my answer. If you're interested specifically in this issue, please ask a new question. $\endgroup$ – Yuval Filmus Dec 28 '17 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.