It's a hook. The dot needs a space to its left to prevent it binding with the slash.
(Insert slashdot joke, here.) Thanks, -- Raul On Thu, Oct 30, 2014 at 1:49 AM, Jon Hough <jgho...@outlook.com> wrote: > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
