Connected components from an adjacency matrix using Numpy or Scipy

Question

I've the following adjacency matrix:

array([[0, 1, 1, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 0, 0],
       [1, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 1, 0, 1, 0],
       [0, 0, 0, 0, 1, 0, 1],
       [0, 0, 0, 1, 0, 1, 0]])

Which can be drawn like that:

My goal is to identify the connected graph ABC and DEFG. It's seems that Depth-First Search algorithm is what I need and that Scipy implemented it. So here is my code:

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import depth_first_order
import numpy as np

test = np.asarray([
    [0, 1, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0, 1, 0]
])

graph = csr_matrix(test)
result = depth_first_order(graph, 0)

But I don't get the result:

>>> result
(array([0, 1, 2]), array([-9999,     0,     1, -9999, -9999, -9999, -9999]))

what's that array([-9999, 0, 1, -9999, -9999, -9999, -9999]) ? Also, in the documentation, they talk about a sparse matrix not about an adjacency one. But an adjacency matrix seems to be a sparse matrix by definition so it's not clear for me.

Answer 1

While you could indeed use DFS to find the connected components, SciPy makes it even easier with scipy.sparse.csgraph.connected_components. With your example:

In [3]: connected_components(test)                                                              
Out[3]: (2, array([0, 0, 0, 1, 1, 1, 1], dtype=int32))