strongcomp

sksparse.btf.strongcomp(A, q=None)[source]

Compute the strongly connected components of a directed graph.

This function finds a symmetric permutation of a sparse matrix so that A[p][:, p] is block upper triangular form [1].

Parameters:

  • A ((N, N) {array-like, sparse array}) – An array convertible to a sparse matrix in Compressed Sparse Column (CSC) format. Must be square.

  • q ((N,) ndarray of int, optional) – A permutation vector. If provided, find the strongly connected components of A[:, qin].

Returns:

  • p ((N,) ndarray of int) – The permutation vector such that A[p][:, p] is in block upper triangular form, unless q is provided (see below).

  • q ((N,) ndarray of int, optional) – If q is provided on input, A[p][:, q] is in block upper triangular form.

  • r ((Nb+1,) ndarray of int) – The array of indices of the start of each block in the permuted matrix. Block b is in rows/columns r[b] to r[b+1] - 1. The number of blocks is len(r) - 1.

Added in version 0.5.0.

References

Examples

>>> import numpy as np
>>> from scipy.sparse import random_array, block_diag
>>> from sksparse.btf import strongcomp
>>> # Create a matrix with at least 2 strongly connected components
>>> M, N = 4, 7
>>> rng = np.random.default_rng(56)
>>> A0 = random_array((M, M), density=0.5, rng=rng)
>>> A1 = random_array((N, N), density=0.5, rng=rng)
>>> A = block_diag((A0, A1), format='csc')
>>> # The first M rows/columns are ordered together, then the last N
>>> p, r = strongcomp(A)
array([ 0,  1,  3,  2, 10,  4,  5,  6,  7,  8,  9], dtype=int32)
>>> r
array([ 0,  3,  4,  5, 11], dtype=int32)