graph representation, paths, path length

[ag]

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

[stevan apter]

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

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

--
You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbpl...@googlegroups.com.
To post to this group, send email to personal...@googlegroups.com.
Visit this group at https://groups.google.com/group/personal-kdbplus.
For more options, visit https://groups.google.com/d/optout.

[Science Student]

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

[Alexander Belopolsky]

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

[Patryk 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

--

You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.
To post to this group, send email to personal-kdbplus@googlegroups.com.

[stevan apter]

treetable: a better implementation, in q:

https://github.com/stevanapter/hypertree

graphs are harder than trees, and more interesting.

 

To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbpl...@googlegroups.com.
To post to this group, send email to personal...@googlegroups.com.