Huh actually, no, I don't see what's going on there... hmm... I'll be back with something that hopefully makes sense after I think about this.
-- Raul On Mon, Mar 5, 2018 at 6:41 AM, Raul Miller <[email protected]> wrote: > floydrecon is not meant to be used independently from the result of > floyd. The task verb on that page shows an example of its use: > > task mx > pair dist path > 1->2 1 1->2 > 1->3 3 1->2->3 > 2->1 _ 2->1 > 2->3 2 2->3 > 3->1 _ 3->1 > > Thanks, > > -- > Raul > > > On Mon, Mar 5, 2018 at 4:15 AM, Danil Osipchuk <[email protected]> > wrote: >> actually it seems that it is my code which works correctly, and the >> rosetta's one has a mistake in the initialization of the next-hop table. Or >> am I missing something? >> the same toy example, for unidirectional graph there is no way back from >> nodes 1 and 2 back to 0: >> >> [mx=: 3 3 $ 0 1 4 _ 0 2 _ _ 0 >> >> 0 1 4 >> >> _ 0 2 >> >> _ _ 0 >> >> >> The initialization in rosetta version says there is a way back: >> >> y=:mx >> >> ((|i.@,~)#y)*1>.y->./(,y)-._ >> >> 0 1 2 >> >> 0 1 2 >> >> 0 _ 2 >> >> >> NB. modify to return both next-hops and metrics: >> >> floydrecon=: verb define >> >> n=. ((|i.@,~)#y)*1>.y->./(,y)-._ >> >> for_j. i.#y do. >> >> d=. y <. j ({"1 +/ {) y >> >> b=. y~:d >> >> y=. d >> >> n=. (n*-.b)+b * j{"1 n >> >> end. >> >> n;y >> >> ) >> >> >> >> >> Basically, _ should appear in the same places: >> >> floydrecon mx >> >> ┌─────┬─────┐ >> >> │0 1 1│0 1 3│ >> >> │0 1 2│_ 0 2│ >> >> │0 _ 2│_ _ 0│ >> >> └─────┴─────┘ >> >> >> >> >> >> 2018-03-05 11:33 GMT+03:00 Danil Osipchuk <[email protected]>: >> >>> Raul, thank you >>> the rosseta version works faster than every thing I tried, not to say >>> giving correct results >>> Danil >>> >>> 2018-03-05 0:12 GMT+03:00 Raul Miller <[email protected]>: >>> >>>> You might get some ideas from >>>> https://rosettacode.org/wiki/Floyd-Warshall_algorithm#J >>>> >>>> Good luck, >>>> >>>> -- >>>> Raul >>>> >>>> >>>> On Sun, Mar 4, 2018 at 4:09 PM, Danil Osipchuk <[email protected]> >>>> wrote: >>>> > Hi, all >>>> > >>>> > I'm toying with the Floyd–Warshall algo >>>> > http://code.jsoftware.com/wiki/Essays/Floyd trying to extend it along >>>> the >>>> > lines of https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm >>>> to >>>> > get a next-hop table >>>> > >>>> > I'm doing something wrong since what I came with is ugly in the >>>> beginning, >>>> > in the middle and in the end and I barely think it works for a simplest >>>> > cases. >>>> > I'm sure there is a better way from which I could learn something. >>>> > regards, >>>> > Danil >>>> > >>>> > >>>> > merge =: 1 : 0 NB. m is a bit mask, merge x with values of y where m >>>> is 1, >>>> > preserve shape >>>> > : >>>> > ($m)$(,m)}(x ,:&:, y) >>>> > ) >>>> > >>>> > floyd=: 3 : 0 >>>> > nh =. (($y)$#y) (y < _) merge (i."0 #~#y) NB. initialize next-hop >>>> table, >>>> > #y means unreachable >>>> > for_k. i.#y do. >>>> > m =. y > [dk =. k ({"1 +/ {) y NB. dk is distance through >>>> k, m >>>> > is a mask were it is an improvement >>>> > y =. y m merge dk NB. update the distance table >>>> > nh=. nh m merge (|: ($y)$ k{"1 nh) NB. set next-hop through k >>>> where >>>> > there is an improvement >>>> > end. >>>> > nh;y >>>> > ) >>>> > --- transcript --- >>>> > >>>> > [mx=: 3 3 $ 0 1 4 _ 0 2 _ _ 0 >>>> > 0 1 4 >>>> > _ 0 2 >>>> > _ _ 0 >>>> > >>>> > floyd mx >>>> > ┌─────┬─────┐ >>>> > │0 1 1│0 1 3│ >>>> > │3 1 2│_ 0 2│ >>>> > │3 3 2│_ _ 0│ >>>> > └─────┴─────┘ >>>> > ---------------------------------------------------------------------- >>>> > 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
