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
