How to find connected components in a matrix using Julia

[Charles Novaes de Santana]

Assume I have the following matrix:

    mat = [1 1 0 0 0 ; 1 1 0 0 0 ; 0 0 0 0 1 ; 0 0 0 1 1]

Considering as a "component" a group of neighbour elements that have value '1', how to identify that this matrix has 2 components and which vertices compose each one?

For the matrix mat above I would like to find the following result:

Component 1 is composed by the following elements of the matrix (row,column):

    (1,1)
    (1,2)
    (2,1)
    (2,2)

Component 2 is composed by the following elements:

    (3,5)
    (4,4)
    (4,5)

I can use Graph algorithms like this to identify components in square matrices. However such algorithms can not be used for non-square matrices like the one I present here.

Any idea will be much appreciated.

I am open if your suggestion involves the use of a Python library + PyCall for example. Although I would prefer to use a pure Julia solution.

Regards

Charles

P.S.: Just asked the same question in Stackoverflow: https://stackoverflow.com/questions/32772190/how-to-find-connected-components-in-a-matrix-using-julia

--

Um axé! :)

--
Charles Novaes de Santana, PhD
http://www.imedea.uib-csic.es/~charles

[Valentin Churavy]

Hej Charles,

in the future please only post in one place. A lot of the people who answer on SO are also here.

You can use the label_components function in Images.jl https://github.com/timholy/Images.jl/blob/master/doc/function_reference.md#label_components

To get the the list of coordinates for each components you then would have to do something along the line of.

for c in 1:maximum(labels)
   find(x-> x == c, labels)
end

Not very efficient but that should get you started.

[Charles Novaes de Santana]

Hi Valentin,

Thanks a lot for your suggestion! It makes exactly what I need, with a clear code. I still don't know if efficiency will be an issue for my problems, but I hope it won't.

Just don't agree with your advice to only post in one place. Is there any special reason for it besides the overlap of users?

I see some differences between asking in the mailing-list or in stackoverflow, even if there is an overlap between of users of both forums. In stackoverflow there is kind of a competition of the best responses that I think is interesting, we can learn a lot from everyone there. And I think it is not the focus of this list. Just my opinion.

By the way, the final solution for my problem is the following piece of code:

using Images

function findMat(mat,value)
    return(collect(zip(ind2sub(size(mat),find( x -> x == value, mat))...)));
end

mat = [1 1 0 0 0 ; 1 1 0 0 0 ; 0 0 0 0 1 ; 0 0 0 1 1]

labels = label_components(mat);

 
for c in 1:maximum(labels)

    comp = findMat(labels,c);
    println("Component $c is composed by the following elements (row,col)");      
    println("$comp\n");
end

Thanks again for your help!

Best,

Charles

[Tim Holy]

See also http://stackoverflow.com/a/32778103/1939814

--Tim

> > #label_components To get the the list of coordinates for each components

> > you then would have to do something along the line of.
> >
> > for c in 1:maximum(labels)
> >
> > find(x-> x == c, labels)
> >
> > end
> >
> > Not very efficient but that should get you started.
> >
> > On Friday, 25 September 2015 07:56:20 UTC+9, Charles Santana wrote:
> >> Assume I have the following matrix:
> >> mat = [1 1 0 0 0 ; 1 1 0 0 0 ; 0 0 0 0 1 ; 0 0 0 1 1]
> >>
> >> Considering as a "component" a group of neighbour elements that have
> >> value '1', how to identify that this matrix has 2 components and which
> >> vertices compose each one?
> >>

> >> For the matrix *mat* above I would like to find the following result:

> >>
> >> Component 1 is composed by the following elements of the matrix
> >>
> >> (row,column):
> >> (1,1)
> >> (1,2)
> >> (2,1)
> >> (2,2)
> >>
> >> Component 2 is composed by the following elements:
> >> (3,5)
> >> (4,4)
> >> (4,5)
> >>
> >> I can use Graph algorithms like this

> >> <http://graphsjl-docs.readthedocs.org/en/latest/algorithms.html#connected
> >> -components> to identify components in square matrices. However such

[Charles Novaes de Santana]

Yes, it is my post in Stackoverflow :)

Thanks,

Charles

[Charles Novaes de Santana]

Actually, Thanks, a LOT! :)

Great increase in performance indeed!! :)

Charles