I would read the result for mx that there *are* paths 3->1 and 2->1 with an infinite metric. Even if one to assume that this just a convention - to list non-existent paths as 1-hop paths of infinity, 3->2 though is not treated the same way and not listed regards, Danil
2018-03-05 14:41 GMT+03:00 Raul Miller <[email protected]>: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
