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
