Unfortunately, even after reading the Nuvoc entry for . , I'm not sure I get it.I was messing around with some usages:
f =. <./ . + m =: 2 2 $ 3 5 7 1 f~ m this gives 6 6 8 2 Which seems odd. From Nuvoc, "x u . v y is defined for general u and v as x u@(v"(1+lv,_)) y". So here I am doing m +"(1 _) m and then from using the result of that, r say, doing m <./ r But the result of doing that is clearly not what is wanted. > Date: Thu, 30 Oct 2014 06:58:31 -0400 > From: [email protected] > To: [email protected] > Subject: Re: [Jprogramming] Algorithm to Check Graph is connected > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
