Is (<. <./ .+)～ a fork? It looks like it should be a fork, but running dissect on it shows a hook.
--- Original Message --- From: "Henry Rich" <henryhr...@nc.rr.com> Sent: October 30, 2014 11:02 AM To: programm...@jsoftware.com Subject: Re: [Jprogramming] Algorithm to Check Graph is connected Only one small tweak to this fine post: > The rough J equivalent of C's array[i][j] = 30; would be > > 30 (<i,j)} array Precisely (Raul said 'rough', but the subtlety may be lost on beginners), the equivalent would be array =: 30 (<i,j)} array 30 (<i,j)} array makes a whole new copy of array with element (i,j) changed. This can be expensive if the array is large. By assigning to the same name you save the cost of the new copy. Henry Rich On 10/29/2014 8:09 PM, Raul Miller wrote: > The rough J equivalent of C's array[i][j] = 30; would be > > 30 (<i,j)} array > > For example: > 30 (<2 3)} 6 6$0 > 0 0 0 0 0 0 > 0 0 0 0 0 0 > 0 0 0 30 0 0 > 0 0 0 0 0 0 > 0 0 0 0 0 0 > 0 0 0 0 0 0 > > That said, be aware that often (not always, but often enough to be > worth discussing the algorithm) J will offer better approaches. > > For example, for your connectedness problem: > mat1 =: 5 5 $ _ 3 4 2 _, 3 _ _ 1 8, 4 _ _ 5 5, 2 1 5 _ _, _ 8 5 _ _ > mat2 =: 3 3 $ _ 1 _, 1 _ _, _ _ _ > > (<. <./ .+~)~^:# mat1 > 4 3 4 2 9 > 3 2 6 1 8 > 4 6 8 5 5 > 2 1 5 2 9 > 9 8 5 9 10 > (<. <./ .+~)~^:# mat2 > 2 1 _ > 1 2 _ > _ _ _ > > The expression (<. <./ .+)~^:_ finds the path distance between every > pair of points in your distance matrix. If any of them are _ the > matrix is not connected. > > _ e. , (<. <./ .+)~^:_ mat1 > 0 > _ e. , (<. <./ .+)~^:_ mat2 > 1 > > The expression (<. <./ .+)~^:# is a slightly less efficient version of > (<. <./ .+)~^:_ > > The difference is that # specifies a repeat count equal to the number > of rows in the matrix, while _ stops as soon as the result converges. > To see why this matters, it can be instructive to look at some > examples. You can see all the intermediate results (as well as initial > and final values) by using a: instead: > > (<. <./ .+~)~^:a: mat1 > _ 3 4 2 _ > 3 _ _ 1 8 > 4 _ _ 5 5 > 2 1 5 _ _ > _ 8 5 _ _ > > 4 3 4 2 9 > 3 2 6 1 8 > 4 6 8 5 5 > 2 1 5 2 9 > 9 8 5 9 10 > > and > > (<. <./ .+~)~^:a: mat2 > _ 1 _ > 1 _ _ > _ _ _ > > 2 1 _ > 1 2 _ > _ _ _ > > The final result was achieved on the first iteration in both examples. > > So... how does that expression work? > > Structurally, it's doing something very like a transitive closure. See > example 5 in the dictionary entry for ^: > > http://jsoftware.com/help/dictionary/d202n.htm > > Except, each iteration, it's adding every pair between two copies of > the distance matrix and then for each endpoint pair finding the > minimum distance which resulted. And, for sanity's sake, taking the > minimum of that result and the original pair distance. > > The tricky part, if you have not seen it before, is the inner product: > u/ .v > > Matrix multiplication is +/ .* and we are following the same pattern > here. Rather than try to document the details, however, I would prefer > to point you at the dictionary > http://jsoftware.com/help/dictionary/d202n.htm and the nuvoc page > http://www.jsoftware.com/jwiki/Vocabulary/dot#dyadic > > (The other thing I am using is the u~ pattern. That's even simpler: > u~y is equivalent to y u y. So, +~1 is equivalent to 1+1. Actually, > it's so simple that it's worth explaining just because otherwise it's > something your eyes might gloss over.) > > Anyways, unless you are working with connection matrices which stress > the capacity of your machine, I imagine that finding all the path > distances and checking if any are infinity will be faster than your > > connected =: verb define > mat=: y NB. the graph (square matrix) > in=: 0 NB. list of connected nodes, start at node 0. > size=: # y NB. Size of y > all=: i. size NB. all nodes. > isconnected =: 0 NB. is connected flag. > counter =: 0 > NB. loop through all nodes in graph. > NB. Add any nodes connected to the in list to the in list. > NB. If connected, in will eventually contain every node. > while. (counter < size) do. > counter=: counter + 1 NB. increment counter (very bad J?). > toin =: '' > NB. only want nodes that may not be connected. (remove "in" nodes) > for_j. all -. in do. > NB. Get each column from in list and find non-infinite > NB. edges from these nodes to nodes in all - in list. > NB. (%) is to convert _ to 0. > if. ((+/@:%@:(j &{"2) @: (in& { "1) mat ) > 0) do. > toin =: toin , j > end. > end. > NB. append toin to in. Number of connected nodes increases. > in =: ~. in, toin > NB. check connectivity. > isconnected =:-. (# in ) < size > if. isconnected do. > end. > end. > isconnected > ) > > I hope this helps, > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
