StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I believe this will work:</p> <pre><code>reachable_matrix = adj_matrix length_of_path = 1 while(length_of_path < (N - 1)) { for(i = 0; i < N; ++i) { for(j = 0; j < N; ++j) { tmp_matrix[i][j] = 0; for(k = 0; k < N; ++k) { tmp_matrix[i][j] ||= reachable_matrix[i][k] && reachable_matrix[k][j]; // Can I reach from i to j through k? } } } reachable_matrix = tmp_matrix; length_of_path *= 2; } </code></pre> <p>As Richard commented, this is equivalent to calculating traversability of graph.</p> <p>You can think of <code>adj_matrix[i][j]</code> as about a number saying how many paths of length 1 lead from from <code>i</code> to <code>j</code>. Then <code>adj_matrix ** l</code> (thats adjancency matrix to the power of <code>l</code>) tells you how many paths of length at least <code>l</code> there are between any two two nodes.</p> <p>The inner loops in my code (looping with variables i, j and k) are basically multiplication of <code>reachable_matrix</code> by <code>reachable_matrix</code> and storing it in <code>tmp_matrix</code>, only instead of addition and multiplication I use logical or and and, because we're not interested in the exact number, only in its truth value.</p> <p>Outer loop keeps squaring <code>reachable_matrix</code> while power to which it is raised (length of paths that we checked) is smaller than <code>N - 1</code>. Stopping at <code>N - 1</code> is enough, because if you have a path of this length, it means that you are visiting all nodes in the graph. Paths with more steps necessarily must contain cycles. On the other hand I don't perform binary exponentiation exactly to keep things simple (I think it would be a little less efficient, but I'm not sure about that) and because trying longer paths doesn't do any harm.</p> <p>Overall this algorithm has complexity O(log(N) * N**3).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload