Yes, I meant floydrecon will multiply 0 by _ in some cases (in my verb i opted for #y to denote absent next hop and didn't have that concern) thank you a lot for the pointers regards, Danil
On Mar 5, 2018 8:19 PM, "Raul Miller" <[email protected]> wrote: > floyd=: verb define > for_j. i.#y do. > y=. y <. j ({"1 +/ {) y > end. > ) > > I do not see any multiplications there? > > Generally speaking, this algorithm should use >. and <. instead of > arithmetic operations. > > But, yes, floydrecon does expect 0 * n to be zero and not an error. > > And, it could have used something like > > n=. ((->./@:-.&_@,)>.$$i.@#) y > > Thanks, > > -- > Raul > > On Mon, Mar 5, 2018 at 10:29 AM, Danil Osipchuk > <[email protected]> wrote: > > 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 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
