Strongly Connected Components

Question

Two distinct vertices in a directed graph are strongly connected if there is path in the graph from each to the other. A strongly connected component of the graph is a subset of the graph such that each pair of distinct vertices in the subset are strongly connected, and adding any more vertices to the subset would break this property.

Your challenge is to separate a graph into its strongly connected components. Specifically, you must output all of the SCCs in the graph.

I/O:

As input, you may use a list of directed edges, an adjacency list, an adjacency matrix, or any other reasonable input format. Ask if you're not sure. You may assume the graph has no totally disconnected vertices, and that there are no self edges, but you may not make any further assumptions. You may also optionally take the list of vertices as input, as well as the number of vertices.

As output, you must either give a partitioning of the vertices, such as a list of lists of vertices, where each sublist is a strongly connected component, or a labeling of vertices, where each label corresponds to a different component.

If you use a labeling, the labels must either be vertices, or a consecutive sequence of integers. This is to prevent offloafing the computation into the labels.

Examples:

These examples take lists of edges, where each edge is directed from the 1st entry to the second entry, and output partitions. You are free to use this format or another.

The input is on the first line, the output is on the second line.

[[1, 2], [2, 3], [3, 1], [1, 4]]
[[1, 2, 3], [4]]

[[1, 2], [2, 3], [3, 4]]
[[1], [2], [3], [4]]

[[1, 2], [2, 1], [1, 3], [2, 4], [4, 2], [4, 3]]
[[1, 2, 4], [3]]

[[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]
[[1, 2, 5], [3, 4, 8], [6, 7]]

Scoring and restrictions:

Standard loopholes are banned, as always. Also, built-ins which specifically deal with strongly connected components are banned.

Solutions should run in no more than an hour on the examples provided. (This is intended to prevent slow exponential solutions, and nothing else.)

This is code golf. Fewest bytes wins.

Answer 1

Pyth, 13 bytes

.gu+Gs@LQG.{k

Demonstration, Test suite

Input is an adjacency list, represented as a dictionary which maps vertices to the list of vertices it has edges to (its directed neighbors). Output is a partition.

The essence of the program is that we find the set of vertices that are reachable from each vertex, and then group the vertices by those sets. Any two vertices in the same SCC have the same set of vertices reachable from them, because each is reachable from the other, and reachability is transitive. Any vertices in different components have different reachable sets, because neither's set contains the other.

Code explanation:

.gu+Gs@LQG.{k
                  Implicit: Q is the input adjacency list.
.g           Q    Group the vertices of Q by (Q is implicit at EOF)
  u       .{k     The fixed point of the following function, 
                  starting at the set containing just that vertex
   +G             Add to the set
     s            The concatenation of
      @LQG        Map each prior vertex to its directed neighbors

Answer 2

Python 2 using numpy, 71 62 bytes

import numpy
def g(M,n):R=(M+M**0)**n>0;print(R&R.T).argmax(0)

Takes input as a numpy matrix representing adjacency and the number of nodes. Produces output as a numpy row matrix that labels each vertex by the lowest vertex number in its component.

For an adjacency matrix M, the matrix power M**n counts the number of n-step paths from each start vertex to each end vertex. Adding the identity to M via M+M**0 modifies the adjacency matrix to add a self-loop to every edge. So, (M+M**0)**n counts paths of length at most n (with redundancy).

Since any path has length at most n, the number of nodes, any (i,j) where vertex j can be reached from i corresponds to a positive entry of (M+M**0)**n. The reachability matrix is thenR=(M+M**0)**n>0, where the >0 works entrywise.

Computing the entrywise and as R&R.T, where R.T is the transpose, then gives a matrix indicating the pairs of mutually reachable vertices. It's ith row is an indicator vector for vertices in the same strongly connected component as it. Taking its argmax of each row gives the index of the first True in it, which is the index of the smallest vertex in its component.

Answer 3

JavaScript (ES6), 125 bytes

a=>a.map(([m,n])=>(e[m]|=1<<n|e[n],e.map((o,i)=>o&1<<m?e[i]|=e[m]:0)),e=[])&&e.map((m,i)=>e.findIndex((n,j)=>n&1<<i&&m&1<<j))

Takes a list of directed pairs as an argument, while the result is a array for each vertex giving the first vertex strongly connected to it, which I believe counts as a valid labelling. For example, with the input [[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]] it returns [, 1, 1, 3, 3, 1, 6, 6, 3] (there is no vertex 0; vertexes 1, 2 and 5 have label 1; 3, 4 and 8 have label 3 while 6 and 7 have label 6).

Answer 4

MATL, 26 22 bytes

tnX^Xy+HMY^gt!*Xu!"@f!

This uses the same approach as @xnor's answer.

Works in current version (15.0.0) of the language.

Input is the adjacency matrix of the graph, with rows separated by semicolons. The first and last test cases are

[0 1 0 1; 0 0 1 0; 1 0 0 0; 0 0 0 0]

[0 1 0 0 0 0 0 0; 0 0 1 0 1 1 0 0; 0 0 0 1 0 0 1 0; 0 0 1 0 0 0 0 1; 1 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 1 0 0; 0 0 0 1 0 0 1 0]

Try it online!

t     % implicitly input adjacency matrix. Duplicate
n     % number of elements
X^    % square root
Xy    % identity matrix of that size
+     % add to adjacency matrix
HM    % push size again
Y^    % matrix power
g     % convert to logical values (0 and 1)
t!*   % multiply element-wise by transpose matrix
Xu    % unique rows. Each row is a connected component
!     % transpose
"     % for each column
  @   %   push that column
  f!  %   indices of nonzero elements, as a row
      % end for each. Implicitly display stack contents