Creating Strongly Connected Components from a DAG

Question

I am trying to create strongly connected components from a directed acyclic graph.

The input is a list of edges in form

1 2
3 5
etc

I need to create an outpoint of a minimal set of edges to be added to the given graph to make a graph of strongly connected components....

Any ideas?

Here's an example of what I'm looking for:

Given the input:

1 3
1 4
2 3
2 4
5 7
5 8
6 8
6 9

The output would be the minimum number of edges necessary for addition to create strongly connected components.

Output:

3 1
4 5
7 6
8 1
9 2

Answer 1

Assuming there are no isolated vertices in the graph you only need to add max(|sources|,|sinks|) edges to make it strongly connected.

Let T={t₁,…,t_n} be the sinks and {s₁,…,s_m} be the sources of the DAG. Assume that n <= m. (The other case is very similar). Consider a bipartite graph G(T,S) between the two sets defined as follows. G(T,S) has an edge (t_i,s_j) if and only if t_i can be reached from s_j.

Let M be a maximal matching in G(T,S). Without loss of generality assume that M consists of k edges: {(t₁,s₁),(t₂,s₂),…,(t_k,s_k)}. In the original graph DAG G, add directed-edges {(t₁->s₂),(t₂->s₃),…,(t_k−1->s_k),(t_k->s₁)}. It's easy to see that by adding these edges, the vertices induced by M are strongly connected in G.

Now consider the remaining vertices in G(T,S). Because M maximal, each vertex in S−M (resp. T−M)should be connected to a vertex in T (resp. S−M). So we pair up the remaining vertices arbitrarily, say {(t_k+1,s_k+1),…,(t_n,s_n)} and add the corresponding directed edges in G. For each remaining source vertex source s_i (i belongs to {n+1,…,m} we add the edge (t₁->s_i) in G. Thus the total number of edges added is max(|sources|,|sinks|).

EDIT: Adding a couple of Examples

For the example in your input. We fist compute a maximal matching, say:

3--1
4--2
7--5
8--6

So we add the edges:

3->2
4->5
7->6
8->1

The remaining (sink) vertex not present in the matching is 9 and so we add the arc from 9 to any source vertex in the matching, say 9->1.

Here's another example that illustrates all the steps of the algorithm:

Input Graph:

12 3   5    9 10  (sources)
\|/   /|\    \/
 4   6 7 8   11   (sinks)

Maximal Matching:

4--1
6--5
11--9

So we add the edges:

4->5
6->9
11->1

Now the remaining sinks are {7, 8} and the remaining sources are {2, 3, 10}. We arbitrary pair 7 with say 2 and 8 with say 3 and add:

7->2
8->3

Finally, the remaining (source) vertex is 10 and we add:

4->10

Answer 2

If I understood your question correctly, You should use an Adjacency Matrix representation of your graph. Initially, it will be a sparse matrix with 1s or something where your current edges are.

Using a simple traversal of the matrix, all 0 elements -> 1 that you require to create SCCs, and each of those transformations will be an edge you need to add.

There is also a good wiki page showing the possible popular algorithms used for this:

http://en.wikipedia.org/wiki/Strongly_connected_component

It recommends Tarjan's and Path-based algorithms as being the most practical.