[Scipy-tickets] [SciPy] #1876: bug in csgraph.connected_components with connection='strong'
SciPy Trac
scipy-tickets@scipy....
Tue Mar 26 09:03:54 CDT 2013
#1876: bug in csgraph.connected_components with connection='strong'
----------------------------------+-----------------------------------------
Reporter: juh | Owner: jakevdp
Type: defect | Status: new
Priority: normal | Milestone: Unscheduled
Component: scipy.sparse.csgraph | Version: 0.11.0
Keywords: connected_components |
----------------------------------+-----------------------------------------
If I understood correctly, the function connected_components with
directed=True and connection='strong' labels the connected nodes iff the
graph contains the two directions of an edge: an edge (i,j) is taken into
account only if g[i,j] and g[j,i] exist.
It usually does that, but I found a case where it don't. A minimal example
is :
{{{
g = np.array([[0,1,1,0],[1,0,0,1],[0,0,0,1],[0,0,1,0]] )
}}}
The connected_component find only 1 component, while it should give 2:
[0,1] and [2,3]
This exemple is basically, [0,1] both pointing to each other, same for
[2,3], then if there is one edge from any of [0,1] to any of [2,3], and
one edge from any of [2,3] to any of [0,1], *even if not symmetric*, it
still connect the two components.
I hope I am clear enough
--
Ticket URL: <http://projects.scipy.org/scipy/ticket/1876>
SciPy <http://www.scipy.org>
SciPy is open-source software for mathematics, science, and engineering.
More information about the Scipy-tickets
mailing list