Connectivity loops and such 
Author Message
 Connectivity loops and such

Hi all:
  With all this talk about loops being good/bad and references to
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  
 
 [ 5 post ] 

 Relevant Pages 

1. break one loop and skip one iteration of outer loop

2. 2 files: a loop within a loop??

3. Problem with loop inside other loop

4. Impelement for loop and do while loop

5. using while loops within while loops?

6. Fast loop inside a slow loop?

7. Troubles using while loops and case loops

8. For Loop looping only once

9. nested while loops, inside loop not stopping correctly

10. For loop, possible to increment counter/exit loop?

11. changing the value of loop-control variable in loop

12. Loop variable value after loop finish

 

 
Powered by phpBB® Forum Software