Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Connected components from an adjacency matrix using Numpy or Scipy

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:

enter image description here

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.

like image 382
snoob dogg Avatar asked Dec 15 '19 19:12

snoob dogg


People also ask

What is strongly connected components in a graph?

A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. That is, a path exists from the first vertex in the pair to the second, and another path exists from the second vertex to the first.

What do you mean by adjacency matrix?

In graph theory, an adjacency matrix is nothing but a square matrix utilised to describe a finite graph. The components of the matrix express whether the pairs of a finite set of vertices (also called nodes) are adjacent in the graph or not.


1 Answers

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))
like image 67
fuglede Avatar answered Oct 11 '22 23:10

fuglede