[SciPy-User] cs_graph_componets returning wrong results?

Gael Varoquaux gael.varoquaux@normalesup....
Wed Jan 11 00:27:06 CST 2012


On Tue, Jan 10, 2012 at 11:46:07PM -0500, Joohwi Lee wrote:
>    To identify connected components of a graph, I am trying to use
>    'scipy.sparse.cs_graph_components()' function.
>    The adjacency graph looks like
>    array([[1, 0, 0, 0, 1],
>           [0, 1, 1, 1, 1],
>           [0, 0, 1, 1, 1],
>           [0, 0, 0, 1, 1],
>           [0, 0, 0, 0, 1]])
>    The graph is actually consisting of (1 -> (5 = 2 = 3 = 4) ), where
>    (2,3,4,5) are connected each other and 1 is only connected to 5.
>    I expect cs_graph_components(x) should return (1, [0,0,0,0,0]) which means
>    that there is only one component, but it returns (2, array([0, 1, 1, 1,
>    0], dtype=int32)).

Indeed, the answer that you are getting is wrong. That said, you are
giving it a non symmetric matrix. If you give it a symmetric version of
this graph it works as it should:

In [12]: sparse.cs_graph_components(a + a.T - np.eye(5))
Out[12]: (1, array([0, 0, 0, 0, 0]))

Now the docstring says that only the upper triangular part of the matrix
is used. This docstring is clearly wrong in the current state. I'll try
and fix that.

HTH,

Gael


More information about the SciPy-User mailing list