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
