如何使用Julia在矩阵中查找连接的组件 [英] How to find connected components in a matrix using Julia

问题描述

假设我有下面的矩阵（这里用Julia语言定义）：

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

考虑作为一个分量 1'，如何识别这个矩阵有2个分量和哪个顶点组成每个？ strong> above我想查找下面的结果：

组件1由矩阵（行，列）的以下元素组成：

$ b （1,1）
（1,2）
（2,1）
（2,2）
$ b

组件2由以下元素组成：

 （3,5）
（4,4）
（4,5）
  

我可以使用图形算法，如这个来标识矩形矩阵中的组件。然而，这样的算法不能用于像我在这里展示的非矩形矩阵。

任何想法都将非常感谢。

如果您的建议涉及使用Python库+ PyCall，则我已打开。虽然我宁愿使用纯粹的朱莉娅解决方案。

Regards

解决方案使用图片。 jl 的 label_components 确实是解决核心问题的最简单方法。但是，循环 1：maximum（labels）可能效率不高：它是 O（N * n），其中 N 是标签和 n 中元素的数量，因为您访问了标签 n 次的每个元素。

只需访问 labels 中的每个元素两次：一次确定最大值，一次将每个非零元素分配给它适当的组：

 使用图片
 
函数collect_groups（标签）
 groups = [Int如果l！= 0 
 push！（groups [l]，i），则枚举（标签）
中的（i，l）对于i = 1：最大（标签）] 
 
 end 
 end 
 groups 
 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）
 groups = collect_groups（labels）
  

输出到您的测试矩阵：

  2元素Array {Array {Int64,1} ，1}：
 [1,2,5,6] 
 [16,19,20] 
  

调用库函数（如 find ）有时可能会有用，但它也是一种习惯于较慢语言的值得留下的习惯。在茱莉亚，你可以编写自己的循环，它们会很快;更好的是，通常所得到的算法更易于理解。 collect（zip（ind2sub（size（mat），find（x - > x == value，mat））...））并没有完全脱离舌头。

Assume I have the following matrix (defined here in Julia language):

    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. Although I would prefer to use a pure Julia solution.

Regards

解决方案

Using Image.jl's label_components is indeed the easiest way to solve the core problem. However, your loop over 1:maximum(labels) may not be efficient: it's O(N*n), where N is the number of elements in labels and n the maximum, because you visit each element of labels n times.

You'd be much better off just visiting each element of labels just twice: once to determine the maximum, and once to assign each non-zero element to its proper group:

using Images

function collect_groups(labels)
    groups = [Int[] for i = 1:maximum(labels)]
    for (i,l) in enumerate(labels)
        if l != 0
            push!(groups[l], i)
        end
    end
    groups
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)
groups = collect_groups(labels)

Output on your test matrix:

2-element Array{Array{Int64,1},1}:
 [1,2,5,6] 
 [16,19,20]

Calling library functions like find can occasionally be useful, but it's also a habit from slower languages that's worth leaving behind. In julia, you can write your own loops and they will be fast; better yet, often the resulting algorithm is much easier to understand. collect(zip(ind2sub(size(mat),find( x -> x == value, mat))...)) does not exactly roll off the tongue.

这篇关于如何使用Julia在矩阵中查找连接的组件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！