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
