[kdb +/q]:将邻接矩阵转换为邻接列表 [英] [kdb+/q]: Convert adjacency matrix to adjacency list

问题描述

给出(矩形)邻接矩阵m，如何用q语言构造邻接表?

Given (rectangular) adjacency matrix m, how to construct adjacency list in q language?

在 QIdioms Wiki 中，我找到了k语言的解决方案，该解决方案通过q控制台通过q控制台运行时，出现'vs错误:

In QIdioms wiki I've found solution in the k language which when run through q console with k) command gives me 'vs error:

m:(1 0 1;1 0 1)
k) (^m)_vs &,/m
'vs

结果应为:

0 0 1 1
0 2 0 2

这就是我能够在q中复制的内容:

This is what I was able to replicate in q:

k) &,/m
0 2 3 5
q) where raze m
0 2 3 5

k的^ a.k.a. shape动词在q中丢失，所以我这样做了:

k's^ a.k.a. shape verb is missing in q so I just did:

k) (^m)
000b
000b
q) 2 3#0b
000b
000b

现在，因为:

q) parse "vs"
k) {x\:y}

我都尝试失败了:

q) (2 3#0b) _vs where raze m
'
q) (2 3#0b) _\: where raze m
'type

请注意， QIdioms Wiki 具有

Note that QIdioms wiki has q solution for inverse problem: from adj.list to adj.matrix.

推荐答案

您会遇到错误，因为原始Q习惯用k2编写了，k是现代kdb +版本不支持的k的旧版本. k的当前版本为k4，并且与k2向后不兼容.

You've got errors because original Q idioms are written in k2 - an old version of k which modern kdb+ version don't support. A current version of k is k4 and it's not backwards-compatible with k2.

例如，X _vs Y其中X和Y是整数原子或旧k2中的列表的行为类似于X vs Y 将在kdb +中的行为始于3.4t 2015.12.13:

For instance, X _vs Y where X and Y are integer atoms or lists in old k2 behaved like X vs Y will behave in kdb+ starting from 3.4t 2015.12.13: http://code.kx.com/q/ref/lists/#vs:

从3.4t开始，2015.12.13:对于整数类型，计算基数X中Y的基本表示形式.

Since 3.4t 2015.12.13: For integer types, computes the base representation of Y in the radices X.

另一个例子.确实，k2中的^是形状算子，但现在已经不复存在了.在k2中，^m将为您示例中的矩阵m返回2 3，而据我所知，当前实现的行为类似于q的not null.

Another example. Indeed ^ in k2 was a shape operator, but it is not any longer. In k2 ^m would have returned 2 3 for a matrix m from your example whereas current implementation behaves like q's not null as far as I understand.

现在，回到您的原始问题，如何以q语言构造邻接表".一种方法是这样:

Now, back to your original question, "how to construct adjacency list in q language". One way to do it is this:

q)lm:{flip raze(til count x),''where each x}

或

k)lm:{+,/(!#x),''&:'x}

更新:这是它的工作方式.如果我们要使用任何冗长的"语言来构建邻接表，我们将执行以下操作:

UPDATE: Here's how it works. If we were to build an adjacency list using any "verbose" language we would do something like this:

for i = 0 to <number of rows> - 1            <---- (1)
    for j = 0 to <number of columns> - 1     <---- (2)
        if M[i;j] <> 0                       <---- (3)
            print i, j

在类似q的数组语言中，(1)可以翻译"为til count M，因为count将返回顶层的元素数，即行数.组合的(2)和(3)可以用where each M表示.实际上，对于每一行，我们都返回非零元素的位置.给定原始矩阵m，我们将得到:

In an array language like q (1) can be "translated" into til count M because count will return the number of elements at top level, i.e. the number of rows. (2) and (3) combined can be represented by where each M. Indeed, for every row we return positions of non-zero elements. Given an original matrix m we will get:

til count m -> 0 1
where each m -> (0 2; 0 2)

我们要做的就是联接行和列索引.我们不能只使用,'，因为它会将0与第一个0 2结合在一起，并将1与第二个0 2结合在一起，从而导致(0 0 2; 1 0 2).我们需要更深入一层，将左侧的每个元素与右侧的嵌套列表(0 2; 0 2)的每个元素的每个元素连接起来，因此在,''中使用双撇号.

All we need to do is join row and column indexes. We can't use just ,' because it will join 0 with the first 0 2 and 1 with the second 0 2 resulting in (0 0 2; 1 0 2). We need to go one level deeper, joining every element from the left with every element of every element of a nested list (0 2; 0 2) from the right, hence double apostrophes in ,''.

我希望现在有道理.

我个人不会使用flip(或k中的+)，我无法读取这种形式的邻接矩阵:

Personally, I would not use flip (or + in k), I can't read an adjacency matrix in this form:

0 0 1 1
0 2 0 2

我认为这更具可读性:

0 0
0 2
1 0
1 2

但是，这完全取决于您.

But it's up to you of course.

这篇关于[kdb +/q]:将邻接矩阵转换为邻接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！