It looks like a hook because of the spacing and because .+ looks like a noun
. is a conjunction, and returns a derived verb. As such there are two verbs in the train, so a fork (<./ . +) u . v uu=: </. vv=: + (<. (uu . vv)) ~ (3 3 $ i.3) running trace can be helpful: trace '(<. <./ . +)~ arr' --------------- 3 Adverb ----- <. / <./ --------------- 4 Conj ------- <./ . + <./ .+ --------------- 6 Bident ----- <. <./ .+ <. <./ .+ --------------- 8 Paren ------ ( <. <./ .+ ) <. <./ .+ --------------- 3 Adverb ----- <. <./ .+ ~ (<. <./ .+)~ --------------- 6 Bident ----- (<. <./ .+)~ arr (<. <./ .+)~ arr ============================== On Thu, Oct 30, 2014 at 1:56 AM, Raul Miller <[email protected]> wrote: > 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 <[email protected]> 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" <[email protected]> > > Sent: October 30, 2014 11:02 AM > > To: [email protected] > > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
