Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- NB. I've been slowly going through the spectral graph theory course
- NB. at http://www.cs.yale.edu/homes/spielman/561/lect02-12.pdf.
- NB. In section 2.6 graph multiplication is defined and here is my
- NB. go at graph generation and multiplication in J.
- NB.
- NB. 2013-03-16 Michal Dobrogost
- NB. Generate a complete graph on the given number of vertices.
- NB. Note the nice property that '0 0 = $ K 0'.
- K=: ($&1) @: (2&#)
- NB. Generate a path graph on the given number of vertices.
- P=: (1 = |@:-)"0 1~ @: i.
- P 5
- NB. Q - is there a way to find the ranks of a verb?
- NB. A - yes, use verb b. 0
- NB.
- NB. Q - why doesn't (1=|@-)/~ work?
- NB. A - because the left rank is _ (infinity) so it applies the whole left argument
- NB. to the whole right argument.
- NB.
- NB. Q - why have / when you have "0 1?
- NB.
- NB. Generate a star graph on the given number of vertices.
- S=: (1 = +&(0&=))"0 1~ @: i.
- S 5
- NB. Repeat matrix on diagonal
- NB. Q - ways to make this shorter?
- rep_stride=.((*$){.])"0 1
- rep_ravel=.(,@:rep_stride),(#&0 @: (1&{) @: $ @: ])
- rep=: (*$)$rep_ravel
- 3 rep (K 2)
- NB. Graph permutation (keep the structure of the graph but relabel the vertices).
- NB. Q - Astonishingly short, no?
- permG=: [ {"1 {
- 2 0 1 permG S 3
- NB. Splice 4 sets of 3 indicees each.
- NB. Version 1: spliceIxs=: ] %~ (i. @: *) + (_1 + *) * ] | (i. @: *)
- NB. Version 2: derived from visualizing the results of version 1
- spliceIxs=: , @: |: @: i. @: ,~
- 4 3 $ 4 spliceIxs 3
- NB. Graph multiplication
- multG=: (rep~#)~ + (spliceIxs&# permG (rep~#))
- (P 2) multG (S 3)
Advertisement
Add Comment
Please, Sign In to add comment