cancel
Showing results for
Did you mean:

## graph representation, paths, path length

New Contributor
1. Is there a better way to represent the graph as a Q object? (see picture below)

q)bgn:`1`2`3`3`4`5
q)end:`3`4`4`5`6`6
q)distance:1 1 1 1 1 1
q)flip `src`dst`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.

(`1`3`4`6);3
(`1`3`5`6);3
(`2`4`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

5 REPLIES 5
New Contributor
New Contributor II
Just do it as a matrix. Then you can run all the graph theory algorithms on it.

New Contributor

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>.
New Contributor
There's also very good paper on treetable by Stevan

Some more k graphs stuff from Arthur:

Below some naive implementation of biparitite graphs matching problem(q3.3),
things would get more interesting when other side ranks as well, anyone ?

p:`A`B`C`D`E`f`g`h`i`j
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| `h`i
B| `f`g`i
C| ,`f
D| `g`i`j
E| `h`i

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 :
New Contributor
treetable: a better implementation, in q:

graphs are harder than trees, and more interesting.