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 like X vs Y
will behave in kdb+ starting from 3.4t 2015.12.13: http://code.kx.com/q/ref/lists/#vs:
Since 3.4t 2015.12.13: For integer types, computes the base representation of Y in the radices X.
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.
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}
or
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
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)
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 ,''
.
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:
0 0 1 1
0 2 0 2
I think this is much more readable:
0 0
0 2
1 0
1 2
But it's up to you of course.