graph representation, paths, path length

[ag1]

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

[sa1]

http://nsl.com/k/tarjan.q

http://nsl.com/k/loop.q

[newstudent2017]

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

[Alexander_Belop]

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

[P_Bukowinski]

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:`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>:

[sa1]

treetable: a better implementation, in q:

https://github.com/stevanapter/hypertree

graphs are harder than trees, and more interesting.