It still relies on assertion 0=0*_ when updating n-table inside the algo itself in cases like this:
[my=: 3 3 $ 0 100 _ _ 0 2 _ _ 0 0 100 _ _ 0 2 _ _ 0 floyd my ┌─────┬─────────┐ │0 1 1│0 100 102│ │3 1 2│_ 0 2│ │3 3 2│_ _ 0│ └─────┴─────────┘ regards, Danil 2018-03-05 18:17 GMT+03:00 Raul Miller <[email protected]>: > For completeness, here's the fixed floydrecon: > > floydrecon=: verb define > n=. ($y)$_(I._=,y)},($$i.@#)y > for_j. i.#y do. > d=. y <. j ({"1 +/ {) y > b=. y~:d > y=. d > n=. (n*-.b)+b * j{"1 n > end. > ) > > The problem with the earlier version was that 0 * _ is 0 and not > infinity. (Though, now that I think about this, I'm wondering about > why this doesn't throw a NaN error ... perhaps because the problem > occurs so often that NaN errors would be needlessly disruptive?) > > This version deals with that by avoiding the use of arithmetic on > infinities when computing n. > > -- > Raul > > > On Mon, Mar 5, 2018 at 7:09 AM, Raul Miller <[email protected]> wrote: > > Yeah, basically, the value used for n was incorrect. I threw together > > a quick patch, and updated the page. > > > > Thanks for catching this error. > > > > (And, sadly, that's not the only bug on rosettacode, and it's not just > > J - rosettacode just doesn't get enough exercise. There's version > > incompatibility issues, of course, but there's also code that either > > never worked or never worked on anything outside the task examples. > > There's typos and copy and paste issues and incomplete thoughts > > scattered throughout the site. This junk gradually gets found, when > > knowledgable people try out the task implementations, but there's > > still problems lurking here and there. Fortunately, there's enough > > good stuff that the site is still worthwhile, but it still needs more > > attention than it gets.) > > > > Thanks again, > > > > -- > > Raul > > > > > > On Mon, Mar 5, 2018 at 6:51 AM, Danil Osipchuk <[email protected]> > wrote: > >> 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 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
