Guest User

Graph Multiplication in J

a guest
Apr 16th, 2013
212
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
J 1.54 KB | None | 0 0
  1. NB. I've been slowly going through the spectral graph theory course
  2. NB. at http://www.cs.yale.edu/homes/spielman/561/lect02-12.pdf.
  3. NB. In section 2.6 graph multiplication is defined and here is my
  4. NB. go at graph generation and multiplication in J.
  5. NB.
  6. NB. 2013-03-16 Michal Dobrogost
  7.  
  8. NB. Generate a complete graph on the given number of vertices.
  9. NB. Note the nice property that '0 0 = $ K 0'.
  10. K=: ($&1) @: (2&#)
  11.  
  12. NB. Generate a path graph on the given number of vertices.
  13. P=: (1 = |@:-)"0 1~ @: i.
  14. P 5
  15.  
  16. NB. Q - is there a way to find the ranks of a verb?
  17. NB. A - yes, use verb b. 0
  18. NB.
  19. NB. Q - why doesn't (1=|@-)/~ work?
  20. NB. A - because the left rank is _ (infinity) so it applies the whole left argument
  21. NB.     to the whole right argument.
  22. NB.
  23. NB. Q - why have / when you have "0 1?
  24. NB.
  25.  
  26. NB. Generate a star graph on the given number of vertices.
  27. S=: (1 = +&(0&=))"0 1~ @: i.
  28. S 5
  29.  
  30. NB. Repeat matrix on diagonal
  31. NB. Q - ways to make this shorter?
  32. rep_stride=.((*$){.])"0 1
  33. rep_ravel=.(,@:rep_stride),(#&0 @: (1&{) @: $ @: ])
  34. rep=: (*$)$rep_ravel
  35. 3 rep (K 2)
  36.  
  37. NB. Graph permutation (keep the structure of the graph but relabel the vertices).
  38. NB. Q - Astonishingly short, no?
  39. permG=: [ {"1 {
  40. 2 0 1 permG S 3
  41.  
  42. NB. Splice 4 sets of 3 indicees each.
  43. NB. Version 1: spliceIxs=: ] %~ (i. @: *) + (_1 + *) * ] | (i. @: *)
  44. NB. Version 2: derived from visualizing the results of version 1
  45. spliceIxs=: , @: |: @: i. @: ,~
  46. 4 3 $ 4 spliceIxs 3
  47.  
  48. NB. Graph multiplication
  49. multG=: (rep~#)~ + (spliceIxs&# permG (rep~#))
  50. (P 2) multG (S 3)
Advertisement
Add Comment
Please, Sign In to add comment