[kdb +/q]:将邻接矩阵转换为邻接列表

Question

给定(矩形)邻接矩阵m,如何在q语言中构造邻接表？

在QIdioms wiki中,我找到了k一种语言解决方案,当通过qconsole with k)command 运行时会给出'vs错误:

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

结果应该是:

0 0 1 1
0 2 0 2

这是我能够复制的q:

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

k的^又名shape动词用的是失踪q,所以我只是做:

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有针对反问题的q解决方案:从adj.list到adj.matrix.

Answer 1

你有错误,因为原始的Q成语是用k2写的 - 现代kdb +版本不支持的旧版本的k.当前版本的k是k4,它与k2不向后兼容.

例如,X _vs Y其中X和Y是整数原子或列表中旧K2表现得像X vs Y 将:在表现KDB +从3.4吨2015年12月13日开始http://code.kx.com/q/ref/lists/#vs:

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

另一个例子.实际上^在k2中是一个形状算子,但它不再存在.在K2 ^m将返回2 3一个矩阵m,而当前实施的行为就像从你的例子q的not null,据我了解.

现在,回到你原来的问题,"如何用q语言构建邻接列表".一种方法是:

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

要么

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

更新:这是它的工作原理.如果我们使用任何"详细"语言构建邻接列表,我们将执行以下操作:

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,我们将得到:

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)与右边的嵌套列表的每个元素的每个元素连接起来,因此需要双撇号,''.

我希望它现在有意义.

就个人而言,我不会使用flip(或+在k中),我不能以这种形式阅读邻接矩阵:

0 0 1 1
0 2 0 2

我认为这更具可读性:

0 0
0 2
1 0
1 2

但这当然取决于你.