[Jprogramming] Floyd–Warshall with path

[Raul Miller]

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.osipchuk at 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.osipchuk at 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 <rauldmiller at 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.osipchuk at 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