0
$\begingroup$

First of all I did find similar questions here on Computer Science but nothing what would provide real answer for this problem.

I have a graph which i condense into SSC (strongly connected components) by Kosaraju's algorithm. Now what I need is to find connections between those SSCs. The best would be to somehow inject this process into Kosaraju's runtime but I did not come up with tangible solution there. My algorithm is logically similar to the one on wikipedia: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm (I can't provide my code because it is a school assignment)

I would very much appreciate any tip from smarter folk than me. :D


More information/What I came up with: I thought about it and did not come up with better solution then after finishing Kosaraju I will go through each vertex, check his in/out edges and if the edge's other side is not part of this SSC than add this edge as connecting edge to my SSC. But this process is very expensive as i need to:

  1. For each vertex go over its all edges
  2. Compare every edge end with vertexes in SSC.

Computation would be something like edges X [vertexes in its SSC]. If my graph would be one huge SSC than I would basically get V*E. There is no way this is best approach, I bet it is actually one of the worst.

$\endgroup$
  • $\begingroup$ Welcome to the site. It would be better if you could also link to the relevant questions that you already found and read. $\endgroup$ – Dean Gurvitz Oct 24 '18 at 19:24
2
$\begingroup$

Your complexity calculation is incorrect. If for each vertex you go over all of its out edges, in a directed graph you'd only get a $O(|V|+|E|)$ complexity and not $O(|V|*|E|)$. A complexity of $O(|V|*|E|)$ would be the case if for each vertex you performed an operation on all of the edges in the graph, which you have no reason to do.

$O(|V|+|E|)$ complexity is actually the same complexity as calculating the SCCs in the first place, and therefore your general idea can, in-fact, be used (be careful with the details).

$\endgroup$
  • $\begingroup$ You are right, I was way too tired and my brain farted :D. Its V+E even in undirected graph I believe. I believe that exact number is 2*E for both directed and undirected graph, since edges have always two ends. The problem is tho, that if my graph would be one big SSC than I do really compare each edge with each vertex (in the SSC) resolving in VE (2*VE) which is bad and I believe that scenario cannot happen in SSC search using Kosaraju. So I think my solution (eventhough it is faster than I initially expected) is very bad. $\endgroup$ – eXPRESS Oct 26 '18 at 17:29
0
$\begingroup$

This should be more tangible solution.

What I can do (and I will get guaranteed speed of 2E) is in each vertex make note in which SSC it ended (during Kosaraju). Then just iterate over edges and compare if both ends have same SSC and if not, just add the connection into vector of SSCs (which is basically new graph but vertex = SSC). Also all necessary accesses are O(1).

Question solution detailed (optimalizations below can be also used in solution above).

In certain scenarios solution above will performe way better than what I proposed in question. Even if we (in question solution)

1) Check if there is only one SSC and in that case did nothing

2) Order all SSCs from smallest to biggest SSC -> so we would not have to go over the biggest ones vectors, because it would be already connected

The question solution would still get serious performance hit on big graphs with almost no certainties and very variable performance.

$\endgroup$

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.