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
