[kdb +/q]: Convertir la matrice d'adjacence en liste d'adjacence

Question

Étant donné la matrice d'adjacence (rectangulaire) m, comment construire une liste d'adjacence en langage q?

En QIdioms wiki j'ai trouvé la solution dans la langue k qui, lorsqu'il est exécuté par la console q avec la commande k) me donne 'vs erreur:

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

Résultat devrait être:

0 0 1 1 
0 2 0 2 

C'est ce que J'ai été en mesure de reproduire dans q:

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

k « s ^ aka shape verbe est manquant dans q donc je viens de le faire:

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

Maintenant, depuis:

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

J'ai essayé, sans succès, à la fois:

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

Notez que QIdioms wiki a q solution pour le problème inverse: de adj.list à adj.matrix.

Answer 1

Vous avez des erreurs car les idiomes Q d'origine sont écrits en k2 - une ancienne version de k que les versions modernes de kdb + ne supportent pas. Une version actuelle de k est k4 et elle n'est pas rétrocompatible avec k2.

Par exemple, X _vs Y où X et Y sont des atomes entiers ou des listes dans le vieux se comportaient comme X vs Y k2 sera + KDB se comportent à partir de 3.4t 13/12/2015: 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.

Un autre exemple. En effet, ^ dans k2 était un opérateur de forme, mais ce n'est plus le cas. En k2 ^m aurait retourné 2 3 pour une matrice m de votre exemple alors que l'implémentation actuelle se comporte comme qnot null autant que je comprends.

Maintenant, revenons à votre question initiale, "comment construire une liste d'adjacence en q". Une façon de le faire est la suivante:

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

ou

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

MISE À JOUR: Voici comment cela fonctionne. Si nous devions construire une liste de contiguïté en utilisant une langue « verbose » nous faisons quelque chose comme ceci:

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 

Dans un langage de tableau comme q (1) peut être « traduit » en til count M parce count retournera le nombre d'éléments au niveau supérieur, c'est-à-dire le nombre de lignes.(2) et (3) combinés peuvent être représentés par where each M. En effet, pour chaque ligne, nous renvoyons des positions d'éléments non nuls. Étant donné une matrice originale m, nous obtiendrons:

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

Tout ce que nous devons faire est de joindre des index de ligne et de colonne. Nous ne pouvons pas utiliser seulement ,' car il va rejoindre 0 avec le premier 0 2 et 1 avec le second 0 2 résultant en (0 0 2; 1 0 2). Nous devons aller un niveau plus profond, en rejoignant chaque élément de la gauche avec chaque élément de chaque élément d'une liste imbriquée (0 2; 0 2) à partir de la droite, donc double apostrophes en ,''.

J'espère que c'est logique maintenant.

---

Personnellement, je ne voudrais pas utiliser flip (ou + en k), je ne peux pas lire une matrice de contiguïté sous cette forme:

0 0 1 1 
0 2 0 2 

Je pense que cela est beaucoup plus facile à lire:

0 0 
0 2 
1 0 
1 2 

Mais c'est à vous de décider, bien sûr.