I was aware of this solution but expected it to have a poor performance. It was even worse than I thought.
ts'comp G'[ G=:edgs~ 100 0.0011008729 133504 ts'mcsg G' 0.00068417142 9280 (comp -: mcsg) G 1 ts'comp G'[ G=:edgs~ 1000 0.63168909 9439296 ts'mcsg G' 0.01000385 72832 ts'comp G'[ G=:10 edgs 10000 |out of memory: mfe | comp G ts'mcsg G' 0.17620183 885504 R.E. Boss -----Oorspronkelijk bericht----- Van: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Namens Roger Hui Verzonden: maandag 11 september 2006 21:15 Aan: Programming forum Onderwerp: Re: [Jprogramming] FW: Components in graphs There is an alternative solution using connection matrices. It can be slower (or much slower) depending on the density of the graph. mfe =: >:@{. ([EMAIL PROTECTED] e. #.) ] urc =: |: +. ] +. [EMAIL PROTECTED]@# tc =: +./ .*.~^:_ sfm =: <@I."1"_ comp=: ~. @ sfm @ tc @ urc @ mfe mfe computes the direct graph matrix from the list of edges: ] e=: 6 edgs 10 9 9 6 5 9 2 4 9 0 7 0 4 6 8 ] m=: mfe e 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 urc computes the matrix of the undirected graph with reflexive closure: ] m1=: urc m 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 Now compute the transitive closure of the the undirected graph: ] t=: tc m1 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 sfm computes the successor lists from a connection matrix. The unique successor lists are the node numbers of the components: ~. sfm t +---------+-+-+-----+ |0 2 4 7 9|1|3|5 6 8| +---------+-+-+-----+ ----- 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
