I made a merge of comp and mcsg and came up with
mcsg2=: 3 : 0
T=. (~.{."1 y) ,&.> ({."1 </.{:"1) y=./:~"1 y
C=. i.>:>./, y
for_e. T do. C=. (<./i) (i=. {&C^:_ >e)}C end.
(</. [EMAIL PROTECTED]) {~^:_ C
)
e=:edgs~ 1e4
ts'comp e'
0.096245647 1513216
ts'mcsg2 e'
0.093119119 1521792
(mcsg2-:comp) e
1
However I realized that it is rather inappropriate to take into account
points which are not mentioned in the edges. E.g.
comp 6 edgs 10
+---------+-+-+-----+
|0 2 4 7 9|1|3|5 6 8|
+---------+-+-+-----+
whereas
6 edgs 10
9 9
6 5
9 2
4 9
0 7
0 4
6 8
does not mention 1 and 3.
So it is better to leave those points out.
For that reason, both edgs and mcsg2 are adapted to
edgs1=: ([,2:) [EMAIL PROTECTED] ]
mcsg3=: 3 : 0
T=. (~.{."1 y) ,&.> ({."1 </.{:"1) y=./:~"1 y i.~ t0=.~.,y
C=. i.>:>./, y
for_e. T do. C=. (<./i) (i=. {&C^:_ >e)}C end.
t0 </.~ {~^:_ C
)
(mcsg3;])6 edgs1 10
+-----------------+---+
|+-----+---------+|6 5|
||6 5 8|9 2 4 0 7||9 2|
|+-----+---------+|4 9|
| |0 7|
| |0 4|
| |6 8|
+-----------------+---+
Of course mcsg3 is a bit faster
ts'mcsg3 e'
0.084887871 1781440
But recently I discovered another approach which appears to be much faster
even:
T=: 6e4 edgs1 1e5
rpl=: ([EMAIL PROTECTED])$ (((,~{:){~(,~{.)i.[)~,)
ts'([:(] <@~./.~&, ((>./ ([EMAIL PROTECTED],: <.//.) <./) rpl ])^:_) |:)T'
0.23658526 8525312
ts'mcsg3 T'
0.69177839 11368384
Notice however that the outcome does not (exactly) match mcsg3:
(([:(] <@~./.~&, ((>./ ([EMAIL PROTECTED],: <.//.) <./) rpl ])^:_) |:);]) 6
edgs1 10
+-----------------+---+
|+-----+---------+|6 5|
||6 5 8|9 4 0 2 7||9 2|
|+-----+---------+|4 9|
| |0 7|
| |0 4|
| |6 8|
+-----------------+---+
However the number of points per component (and number of components) do
match:
(mcsg3-:&:(#&>) ([:(] <@~./.~&, ((>./ ([EMAIL PROTECTED],: <.//.) <./) rpl
])^:_)
|:))T
1
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: [EMAIL PROTECTED] [mailto:programming-
> [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
