In an undirected graph, a (...) component is a maximal connected subgraph
http://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
R.E. Boss
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
