ag12
1
1. Is there a better way to represent the graph as a Q object? (see picture below)
q)bgn:123345
q)end:344566
q)distance:1 1 1 1 1 1
q)flip srcdst`dist!(bgn;end;distance)
src dst dist
------------
1 3 1
2 4 1
3 4 1
3 5 1
4 6 1
5 6 1
2. what is a good way to enumerate the paths through the graph? and the path length?
eg.
(1346);3
(1356);3
(24`6);2
3. Is there a tutorial of Q graph exercises (from simple to advanced) that shows options on how to represent graphs and traverse them?
Thanks,
-AG
![]()
sa12
2
Just do it as a matrix. Then you can run all the graph theory algorithms on it.
On Saturday, April 28, 2018 at 1:53:16 PM UTC-4, ag wrote:
3. Is there a tutorial of Q graph exercises (from simple to advanced) that shows options on how to represent graphs and traverse them?
Take a look at <https://github.com/JohnEarnest/ok/blob/gh-pages/docs/Trees.md\>.
There’s also very good paper on treetable by Stevan
http://archive.vector.org.uk/art10500340
Some more k graphs stuff from Arthur:
https://a.kx.com/a/k/examples/graph.k
Below some naive implementation of biparitite graphs matching problem(q3.3),
things would get more interesting when other side ranks as well, anyone ?
p:ABCDEfghij
t:((0;7 8);(1; 5 6 8);(2;(,) 5);(3;6 8 9);(4; 7 8)) // Caps preferences
// matrix conversion
// mm: ./[em:count[t[;0]]#(,)count[ppl]#0b;;:;1b] t
// flip[mm,em]|mm,em
// matching problem for bipariate graphs
mtch:{[P;x] $[null r:first where `=P p:v x; P:apath[P;x];P[p r]:x];P}
// swap augmenting paths (assuming it meets Hall’s theorem conditions)
apath:{[P;x] sel:first (where max each v in v x) inter where max each v in opts:where P=`;
P[P?sel]:x;
P[first opts]:sel;P
}
v:(!). p flip t
R:(!). flip (p except key v),'`
q)v
A| hi
B| fg`i
C| ,`f
D| gi`j
E| hi
q)mtch/[R;key v]
f| C
g| B
h| A
i| E
j| D
Pat
2018-04-30 21:55 GMT+01:00 Alexander Belopolsky <alexander.belopolsky@gmail.com>:
sa12
6
treetable: a better implementation, in q:
https://github.com/stevanapter/hypertree
graphs are harder than trees, and more interesting.