Given (rectangular) adjacency matrix m
, how to construct adjacency list in q
language?
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
Result should be:
0 0 1 1
0 2 0 2
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
's^
a.k.a. shape
verb is missing in q
so I just did:
k) (^m)
000b
000b
q) 2 3#0b
000b
000b
Now, since:
q) parse "vs"
k) {x\:y}
I tried unsuccessfully both:
q) (2 3#0b) _vs where raze m
'
q) (2 3#0b) _\: where raze m
'type
Note that QIdioms wiki has q solution for inverse problem: from adj.list to adj.matrix.
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.
For instance,
X _vs Y
where X and Y are integer atoms or lists in old k2 behaved likeX vs Y
will behave in kdb+ starting from 3.4t 2015.12.13: http://code.kx.com/q/ref/lists/#vs:Another example. Indeed
^
in k2 was a shape operator, but it is not any longer. In k2^m
would have returned2 3
for a matrixm
from your example whereas current implementation behaves likeq
'snot null
as far as I understand.Now, back to your original question, "how to construct adjacency list in
q
language". One way to do it is this:or
UPDATE: Here's how it works. If we were to build an adjacency list using any "verbose" language we would do something like this:
In an array language like q
(1)
can be "translated" intotil count M
becausecount
will return the number of elements at top level, i.e. the number of rows.(2)
and(3)
combined can be represented bywhere each M
. Indeed, for every row we return positions of non-zero elements. Given an original matrix m we will get:All we need to do is join row and column indexes. We can't use just
,'
because it will join0
with the first0 2
and1
with the second0 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,''
.I hope it makes sense now.
Personally, I would not use
flip
(or+
in k), I can't read an adjacency matrix in this form:I think this is much more readable:
But it's up to you of course.