Matrix multiply is a good place to start as the dot conjunction simply generalizes the operations behind it.
On Thu, Oct 30, 2014 at 11:42 PM, Jon Hough <[email protected]> wrote: > Thanks. It wasn't matrix multiplication that stumped me. It was trying to > understand how the verb train worked. The conjunction . Had escaped me up > until now, so I just need read up on it a bit more carefully. > > --- Original Message --- > > From: "Raul Miller" <[email protected]> > Sent: October 31, 2014 4:13 AM > To: "Programming forum" <[email protected]> > Subject: Re: [Jprogramming] Algorithm to Check Graph is connected > > Can you be more specific about what you are not sure about getting, > with the . conjunction? > > For example, does it help to visualize the structure of matrix > multiplication? > > Here are some pages that might help with that kind of visualization: > > http://www.stoimen.com/blog/2012/11/26/computer-algorithms-strassens-matrix-multiplication/ > or http://www.sophia.org/tutorials/multiplying-matrices or > http://mathnathan.com/2010/08/matrix-multiplication-opencl/ > > Does it help to think of +/ as representing summation? > > Or are you trying to envision the steps in the process? If so, we > could sketch out some examples. > > Or are you trying to envision the data structure of the result as > based on the arguments. If so, you might try working with examples > like this: > > (i.3) < .(;&.>) 3 3$'abcdefghi' > or > (i.3 3) < .(;&.>) 3 3$'abcdefghi' > or > (i.3 3) < .+ i.3 3 > or > (i.3 3) +/ .+ i.3 3 > > Or other variations on that theme... > > I hope this helps. Joe's tips should help also. > > Thanks, > > -- > Raul > > > On Thu, Oct 30, 2014 at 9:25 AM, Jon Hough <[email protected]> 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 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- Devon McCormick, CFA ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
