cancel
Showing results for 
Search instead for 
Did you mean: 

graph representation, paths, path length

ag1
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

sa1
New Contributor

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



Alexander_Belop
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>. 

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 <alexander.belopolsky@gmail.com>:

treetable: a better implementation, in q:


graphs are harder than trees, and more interesting.