No, you're not doing r =. m +"(1 _) m
followed by m <./ r The <./ is applied on each result cell of m +"(1 _) m individually, and those results are assembled into the final result. Dissect doesn't look inside u .v, but you could try dissect '<./@(+"1 _)~ 2 2 $ 3 5 7 1' Henry Rich On 10/30/2014 9:25 AM, Jon Hough wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
