Thanks for your compliment. BTW, did you notice the efficiency improvement I achieved in generating partitions? http://www.jsoftware.com/pipermail/programming/2006-September/003209.html
R.E. BOSS. -----Oorspronkelijk bericht----- Van: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Namens Roger Hui Verzonden: dinsdag 12 september 2006 19:13 Aan: Programming forum Onderwerp: Re: [Jprogramming] FW: Components in graphs I studied your algorithm with much admiration. The following is essentially the same algorithm using different J tactics for improved speed. comp=: 3 : 0 y=. \:~ \:~"1 y NB. sort edges b=. (~: |.!.0) {."1 y NB. partition points g=. (b#{."1 y) ,&.> b <;.1 {:"1 y NB. partition vertices by edges c=. i.>:{.{.y NB. initial component numbers for_e. g do. c=. (<./i) (i=. {&c^:_ >e)}c end. NB. update component numbers (</. [EMAIL PROTECTED]) {~^:_ c NB. group by component numbers ) e=: edgs~ 5e4 (mcsg -: comp) e 1 ts 'mcsg e' 2.36518 3.97722e6 ts 'comp e' 0.452356 7.44883e6 ----- Original Message ----- From: "R.E. Boss" <[EMAIL PROTECTED]> Date: Monday, September 11, 2006 5:15 am Subject: [Jprogramming] FW: Components in graphs > In an undirected graph, a (...) component is a maximal connected > subgraphhttp://en.wikipedia.org/wiki/Connected_component_(graph_theory) > > How to determine these components if a graph on the points i.n is > given by > its edges? > > edgs=:,~@<:@], ([,2:) [EMAIL PROTECTED] ] > NB. generates [ edges on ] points and the highest numbered > point > 5 edgs 10 > 9 9 > 2 7 > 8 9 > 0 7 > 3 5 > 2 3 > > Then > prpr=:(<@i.@>:@(>./)@,),~ {."1 <@~.@,/. ] > NB. prepares edges, add points > cnct=:(~.@({~^:_ )~ ([:<./{)`[`]} ])&.>/ > NB. connects edges > mcsg=:[:(</[EMAIL PROTECTED]) [:{~^:_ >@cnct @ prpr > NB. maximal connected subgraphs represented by boxed points > > (mcsg ;]) 6 edgs 10 > +---------------------+---+ > |+---------+-+-+-----+|9 9| > ||0 2 4 7 9|1|3|5 6 8||6 5| > |+---------+-+-+-----+|9 2| > | |4 9| > | |0 7| > | |0 4| > | |6 8| > +---------------------+---+ > > ts'mcsg G'[ G=:edgs~ 10000 > 0.15011089 885504 > ts'mcsg G'[ G=:edgs~ 20000 > 0.57568518 1771264 > ts'mcsg G'[ G=:edgs~ 50000 > 2.870659 3977216 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
