Connectivity loops and such
Author Message
Connectivity loops and such

Hi all:
connectivity (transitive closure) matrices, I can't resist pulling out
some examples from a talk on building good train layouts.
Below a1 is an edge matrix, ie, you can go from i to j in 1 step if there
is a one at i,j (or j,i if I'm transposed today).  The connectivity matrix
is a matrix with 1 at i,j if you can get from i to j in any number of steps.
The basic approach is  a1 {or} . {and} a1 gives the two step connections,
a1 {or}.{and} a1 {or}.{and} a1 gives the three step connections and so on.
An {or} reduction of the 0 step, 1 step, 2step,... n-1 step connection
matrices gives the connectivity matrix.  (Though there are more clever
approaches)  Anyway, this is fun, interesting, and frustrating to program
in APL/J because of the difficulty in predicting how well scans are
implemented.  Three J functions are given.  I share these because:
The gross loopy one is fastest,
The tacit one is slowest.
Suggestions for a fast tacit version?  (Does this work much better
in Release 2? (my tests are using J 7.0))
How do APL2 solutions fair?
Any other solutions we should think about (fast/beautiful/{*filter*})?
P.S. sorry if I posted this already some months ago - you know how
my short term memory is ..
Here is the example.

NB. takes "or" reduction of "or" dot "and" scan to get connectivity

NB. same idea using power function
conn=. '+./(y.&(+./ . *.))^:(i.#y.)=i.#y.' : ''

NB. ugliest loop I've ever seen, but algorithm based on warshall's idea: outer products
wars=. ('\$.=.loop#~#w=.y.+.=i.#y.[i=._1',:'loop)w=.w+.(i{"1 w)*./(i=.>:i){w') : ''

NB. some utilities
doubleM=.,~,.~                   NB.  block double of matrix

whatpow2=.[: 2&^. }. % }:        NB.  gives powers of 2

whatpow2 1 4 16 32 64
2 2 1 1

]a1=.(i.12) e."1 (3 11),4 6,1,9,9,0,8 10,0,2 5,7,1,:7 7
0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 1 0 1 0 0 0 0 0
0 1 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 1 0 0
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0
1 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 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
wars a1
1 0 0 1 0 0 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1 0 1
1 0 0 1 1 0 0 1 0 1 0 1
1 0 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1 0 1
(wars a1)-:conn a1
1
(wars a1)-:conn0 a1
1
\$a6=.doubleM a5=.doubleM a4=.doubleM a3=.doubleM a2=.doubleM a1
384 384

NB. test conn0; time should be O(n^4) and space O(n^3)
t1=.ts 'conn0 a1'
t2=.ts 'conn0 a2'
t3=.ts 'conn0 a3'
]t=.t1,t2,:t3
0.59  10184
13.78  71576
404.41 558104
whatpow2 t
4.54572 2.81317
4.87517 2.96299

NB. test conn; time should be O(n^4) and space O(n^3)
t1=.ts 'conn a1'
t2=.ts 'conn a2'
t3=.ts 'conn a3'
t4=.ts 'conn a4'
t5=.ts 'conn a5'
]t=.t1,t2,t3,t4,:t5
0.11      6736
0.77     26196
4.84    149964
37.68 1.02995e6
294.29 7.64214e6
whatpow2 t
2.80735 1.95938
2.65208  2.5172
2.96072 2.77988
2.96537 2.89141

NB. test wars; time should be O(n^3) and space O(n^2)
t1=.ts 'wars a1'
t2=.ts 'wars a2'
t3=.ts 'wars a3'
t4=.ts 'wars a4'
t5=.ts 'wars a5'
t6=.ts 'wars a6'
]t=.t1,t2,t3,t4,t5,:t6
0.05   3164
0.22   4448
0.88  10028
4.77  31964
29.66 117308
212.61 453884
whatpow2 t
2.1375 0.491407
2  1.17281
2.43841  1.67241
2.63646  1.87578
2.84162  1.95202
--
Clifford A. Reiter
Mathematics Department, Lafayette College
Easton, PA 18042 USA,   610-250-5277

Thu, 20 Mar 1997 00:03:12 GMT
Connectivity loops and such
Hmm... I tend to prefer

close=. (+. +./ .*.~)^:_

for transitive closure.

Raul D. Miller           n =: p*q             NB. 9<##:##:n [.large prime p, q

NB.  public e, n, y
x -: n&|&(*&y)^:d 1  NB. 1=(d*e)+.p*&<:q

Thu, 20 Mar 1997 02:08:55 GMT
Connectivity loops and such

: Hmm... I tend to prefer
:    close=. (+. +./ .*.~)^:_
: for transitive closure.

: Raul D. Miller           n =: p*q             NB. 9<##:##:n [.large prime p, q

Beautiful idea; thanks Raul.  If I understand, this should be O(log(n)n^3)
in time and O(n^2) in space.  Pretty close to Warshall.
Some time/space tests:

]t   NB. time/space of warshall with n=12,24,48,96,192,384
0.071      3164
0.225      4448
0.907     10028
4.78     31964
30.16    117308
212.62    453884

NB. test close, time should be O(log(n)n^3) and space O(n^2)

]t
0.049   2016
0.208   4524
1.42  13860
10.55  49812
84.14 190836
666.96 749364
whatpow2 t
2.08573  1.1661
2.77124 1.61526
2.89328 1.84557
2.99555 1.93777
2.98674 1.97333
Cliff
--
Clifford A. Reiter
Mathematics Department, Lafayette College
Easton, PA 18042 USA,   610-250-5277

Fri, 21 Mar 1997 02:59:49 GMT
Connectivity loops and such
Reiter Clifford A:

Actually, if you're going to do that, it's simpler to do the reflexive
closure before you begin the transitive closure

This doesn't significantly affect the timing (maybe trivially faster),
but it's factored better.

Also, if you don't mind using recursion, you can implement Warshall
tacitly:

warsha    =. ] +. {"1 *./ {

--
Raul D. Miller           n =: p*q             NB. 9<##:##:n [.large prime p, q

NB.  public e, n, y
x -: n&|&(*&y)^:d 1  NB. 1=(d*e)+.p*&<:q

Fri, 21 Mar 1997 04:25:20 GMT
Connectivity loops and such
. warsha    =. ] +. {"1 *./ {

Unfortunately, this requires O(n^3) space.  However, it's trivial to
correct that to O(n^2) space.  Taking advantage of the associative
nature of the computation:

--
Raul D. Miller           n =: p*q             NB. 9<##:##:n [.large prime p, q

NB.  public e, n, y
x -: n&|&(*&y)^:d 1  NB. 1=(d*e)+.p*&<:q

Fri, 21 Mar 1997 13:18:17 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages