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 <rauldmil...@gmail.com> 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 <danil.osipc...@gmail.com>
> 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 <rauldmil...@gmail.com>:
>>
>>> 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 <danil.osipc...@gmail.com>
>>> 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 <danil.osipc...@gmail.com>:
>>> >
>>> >> 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 <rauldmil...@gmail.com>:
>>> >>
>>> >>> 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 <
>>> danil.osipc...@gmail.com>
>>> >>> 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
