Fifty Shades of J/Chapter 38

From J Wiki
Jump to: navigation, search

Table of Contents ... Glossary ... Previous Chapter ... Next Chapter

Shortest Paths

Principal Topics

Finding shortest paths through networks is a basic technique in graph theory. Investigating these in J turns out to be a highly practical application of the verb JE (standing for Join Each) described in Parallel joins. JE performs scalarised joins, that it is a derivative of append which behaves like a scalar verb with a result which is always a boxed list or a list of boxed lists.

   unboxed=.0=L.
box =. ]`<@.unboxed
JE =.,each &box            NB. scalarised join, results boxed

The following examples demonstrate how JE works :

   1 2 JE 3 4 5              NB. two lists, append and box
┌─────────┐
│1 2 3 4 5│
└─────────┘
  (1 2;4 5 6) JE 7 8 9       NB. cf. 1 2 + 3
┌─────────┬───────────┐
│1 2 7 8 9│4 5 6 7 8 9│
└─────────┴───────────┘
  1 2 JE 4 5;7 8 9           NB. cf. 1 + 2 3
┌───────┬─────────┐
│1 2 4 5│1 2 7 8 9│
└───────┴─────────┘
   (1 2;2 4 6) JE 4 5;7 8 9  NB. cf. 1 2 + 3 4
┌───────┬───────────┐
│1 2 4 5│2 4 6 7 8 9│
└───────┴───────────┘

To begin the search for shortest paths, it helps to be specific by using a network in the form of a directed graph such as the following :

Fsoj38.png

There are three reasonably obvious ways in which such a network can be represented. First it can be represented as a list of 2-lists each of which is a directed arc

    arcs=.0 1;0 3;0 4;1 4;2 4;3 0;3 1;3 5;4 5;5 2;5 4

or this can be compacted into a list of n ‘nearest neighbour’ lists where n is the number of nodes listing the nearest neighbours of each node:

    n1=.1 3 4;4;4;0 1 5;5;2 4

or thirdly it can be represented as a matrix in which unconnected nodes are represented by _ :

   ]g1=.1(arcs)}6 6$_
_ 1 _ 1 1 _
_ _ _ _ 1 _
_ _ _ _ 1 _
1 1 _ _ _ 1
_ _ _ _ _ 1
_ _ 1 _ 1 _

If required, the matrix in which unconnected nodes are represented by 0s is simply %g1.

The nearest neighbour form can be recovered from the matrix form by

   mton =: I.&.>@<"1@:%
   mton g1
┌─────┬─┬─┬─────┬─┬───┐
│1 3 4│4│4│0 1 5│5│2 4│
└─────┴─┴─┴─────┴─┴───┘

and the reverse transformation is :

   ntom=.monad :'1(;(i.n),each each y)}(n,n=.#y)$_'  NB. neighbour to matrix representation

The rationale for using _ to represent unconnected nodes is partly visual, but more importantly, the following verb spm delivers the shortest path matrix (that is, the matrix whose values are the lengths of the shortest paths between all pairs of nodes) by using the ‘minimum-dot-plus’ inner product applied using the power conjunction as many times as there are nodes in the graph.

   spm=.monad : '<./y(<./ .+)^:(i.#y)y'
   spm g1
2 1 3 1 1 2
_ _ 3 _ 1 2
_ _ 3 _ 1 2
1 1 2 2 2 1
_ _ 2 _ 2 1
_ _ 1 _ 1 2

spm has the merit of working equally well for weighted graphs, that is if the non-infinity values in the base matrix are path-lengths rather than just ones.

   wts=.2 7 6 1 5 7 6 1 4 8 4
   h1=.wts(arcs)}6 6$0
   h1
0 2 0 7 6 0
0 0 0 0 1 0
0 0 0 0 5 0
7 6 0 0 0 1
0 0 0 0 0 4
0 0 8 0 4 0
   ind =. adverb : '(i.@$*x)@]'
   spm _(=&0 ind)}h1
14 2 15  7 3 7
 _ _ 13  _ 1 5
 _ _ 17  _ 5 9
 7 6  9 14 5 1
 _ _ 12  _ 8 4
 _ _  8  _ 4 8

For testing purposes, a random network, y square with a density x is obtainable by :

   randg=.dyad : '%(100*x)>?(y,y)$100'
   0.25 randg 8
_ _ _ _ _ 1 _ _
_ 1 1 _ _ 1 1 1
_ _ _ _ _ _ _ _
_ _ _ 1 1 1 _ 1
_ 1 _ _ 1 _ 1 _
_ 1 1 1 _ _ _ _
_ _ _ 1 _ 1 _ _
1 _ _ _ _ _ _ 1

and a random weighted matrix with weights in the range 1 to 100 by

   randh=.dyad : '(*~:&_)(>:?(y,y)$100)(*&.%)x randg y'
   0.25 randh 8
 0  0 61 0  0 0  0  0
 0  0  0 0  0 0  0 50
65 53  0 0 96 4  0  0
60 21  0 0  0 0  0  3
 0  0  0 0  0 0  0  0
14  0  0 0  0 0  0 23
 0  0  0 0 40 0  0  0
44  0  0 0  0 0 84  0

If symmetry is a requirement a suitable random matrix is generated by

    mksym=.(+|:) @ (*<:/~@(i.@#))
    %mksym% 0.6 randh 4
16 79  2  0
79 35  0  0
 2  0  7 14
 0  0 14 20

Before embarking on shortest path and critical paths routines, it is sensible to test for their possible existence. The connectivity matrix (a matrix which has a 1 for each pair of nodes for which a route exists) is a straightforward derivative of spm.

   connected=.~:&_@spm
   connected g1
1 1 1 1 1 1
0 0 1 0 1 1
0 0 1 0 1 1
1 1 1 1 1 1
0 0 1 0 1 1
0 0 1 0 1 1

The list of lists of reachable nodes from each node in order is given by

   btoi=.# i.@#  NB. binary list to list of 1-positions
   reachable=.btoi each@<"1@connected
   ]u=.reachable g1
┌───────────┬─────┬─────┬───────────┬─────┬─────┐
│0 1 2 3 4 5│2 4 5│2 4 5│0 1 2 3 4 5│2 4 5│2 4 5│
└───────────┴─────┴─────┴───────────┴─────┴─────┘

which can be expanded to a list of all possible journeys of which the first few are demonstrated for

   feasible=.;@:((i.@#)(,each each)reachable)
   12{.u=.feasible g1
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│0 4│0 5│1 2│1 4│1 5│2 2│2 4│2 5│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

ShtstPath below returns the actual shortest path between any single pair of vertices of an unweighted graph . It begins with a line to check that such a path exists in the first place

   ShtstPath=:dyad : 0
if._=(<y){spm x do.'no path' return.end.
r=.{.y [ tgt=.{:y
while.(-.tgt e.tails r)do. r=.r extend x addnodes r end.
r=.>(tgt=tails r)#r
)
   tails=.{:every
   addnodes=.<@[rtoi each tails@]
   rtoi=.btoi@:(%@{~)
   extend=.;@:(JE"1 0 each)
   g1 ShtstPath 0 2
0 3 5 2
0 4 5 2

which can be speeded up by

   ShtstPath1=.dyad : 0
if._=(<y){spm x do.'no path' return.end.
p=.i.0 [ r=.{.y [ 'src tgt'=.y          NB. p=paths found
while.(-.tgt e.tails r)do.              NB. r=paths ongoing
  r=.(r-.p)-.(tails p)e.src [ p=.p,((tails r)e.tgt)#r
  r=.r extend x addnodes r end.         NB. np=newpaths
r=.>(tgt=tails r)#r                     NB. reject incomplete paths
)
   g1 ShtstPath1 0 2
0 3 5 2
0 4 5 2

Next here is an algorithm which returns all paths between a pair of nodes in an unweighted matrix :

   AllPaths=.dyad : 0
if._=(<y){spm x do.'no path' return.end.
p=.i.0 [ r=.{.y [ 'src tgt'=.y          NB. initialise loop
while.(0~:#r)do.                        NB. r = incomplete paths
  r=.r-.p [ p=.p,((tails r)e.tgt)#r     NB. p = complete paths
  r=.r extend x addnodes r              NB. add one node to each r path
  r=.(#~((=&#~.)every))r                NB. remove loops
end. p
)
   g1 AllPaths 0 2
┌───────┬───────┬─────────┬───────────┐
│0 3 5 2│0 4 5 2│0 1 4 5 2│0 3 1 4 5 2│
└───────┴───────┴─────────┴───────────┘

In the case of a weighted matrix it may not be the case that the physically shortest path is the one with the lowest weighted value. To calculate the weighted value of a path use

       steps=.<"(1)@(2&(,/\))
   values=.+/@:([{~steps@])
   h1 values 0 3 5 2
16

Then to find a critical path, all that remains is to find that minimum value path from all paths :

   >(<h1) values each g1 AllPaths 0 2
16 18 15 26
   ((=<./)>(<h1) values each t)#t=.g1 AllPaths 0 2
┌─────────┐
│0 1 4 5 2│
└─────────┘

To build this into a critical path verb with a single argument h1, observe first that g1 is derived from h1 by

   unweight=.monad : '(%@~:&0)y'
   unweight h1
_ 1 _ 1 1 _
_ _ _ _ 1 _
_ _ _ _ 1 _
1 1 _ _ _ 1
_ _ _ _ _ 1
_ _ 1 _ 1 _
   CritPath=:dyad :0             NB. critical path
if._=(<y){spm x do.'no path' return.end.
t=.( unweight x)AllPaths y       NB. all paths
v=.>(<x) values each t           NB. all paths evaluated
(((=<./)v)#t),<<./v              NB. minimum value path selected
)
   h1 CritPath 0 2               NB. critical path and value
┌─────────┬──┐
│0 1 4 5 2│15│
└─────────┴──┘

If there is more than one critical path, all are reported as in the following graph together with their common value :

   
   h2 =: ". ;. _2 (0 : 0)
 0 0  0  0  0 10  0
 2 0  6  0 16 12 13
 0 0  3 10  0  0  0
 0 0  1  0  0  0  0
10 0 19  0  3  5  0
14 0  0  9  0  0  1
 0 0  0  0  0  0 15
)
   h2 CritPath 1 6
┌───┬─────┬───────┬──┐
│1 6│1 5 6│1 0 5 6│13│
└───┴─────┴───────┴──┘

For a list of slack values associated with each path only a slight modification to CritPath is needed

   slack=.-~>./
   Slacks=.dyad :0
if._=(<y){spm x do.'no path' return.end.
t=.(unweight x)AllPaths y
>t JE each slack >(<x)values each t
)
    h1 Slacks 0 2
┌──────────┬─────────┬────────────┬─────────────┐
│0 3 5 2 10│0 4 5 2 8│0 1 4 5 2 11│0 3 1 4 5 2 0│
└──────────┴─────────┴────────────┴─────────────┘

Finally the line of AllPaths which was used to remove loops can be adapted in a relatively unsubtle way to detect and report them :

   Loops=.dyad : 0
if._=(<y){spm x do.'no path' return.end.
l=.p=.i.0 [ r=.{.y [ 'src tgt'=.y      NB. initialise loop
while.(0~:#r)do.                       NB. r = incomplete paths
  r=.r-.p [ p=.p,((tails r)e.tgt)#r    NB. p = complete paths
  r=.r extend x addnodes r             NB. add one node to each r path
  l=.l,(#~((~:&#~.)every))r            NB. remember loops
  r=.(#~((=&#~.)every))r               NB. remove loops
end. l
)
   g1 Loops 0 2
┌─────┬───────┬─────────┬─────────┬───────────┐
│0 3 0│0 4 5 4│0 1 4 5 4│0 3 5 4 5│0 3 1 4 5 4│
└─────┴───────┴─────────┴─────────┴───────────┘

Code Summary

Data representations of networks, properties and conversions

arcs=: 0 1;0 3;0 4;1 4;2 4;3 0;3 1;3 5;4 5;5 2;5 4
nn=: 1 3 4;4;4;0 1 5;5;2 4                                    NB. nearest neighbor
btoi=: # i.@#                                                 NB. binary list to list of 1-positions
mton=: (btoi@:%)each@<"1                                      NB. matrix to n’st neighbour
ntom=: monad :'1(;(i.n),each each y)}(n,n=:#y)$_'             NB. nearest neighbour to matrix r
g1=: 1(arcs)}6 6$_                                            NB. 1 = connected, _ = not
wts=: 2 7 6 1 5 7 6 1 4 8 4
h1=: wts(arcs)}6 6$0                                          NB. weighted g1
randg=: dyad : '%(100*x)>?(y,y)$100'                          NB. random g matrix
randh=: dyad : '(*~:&_)(>:?(y,y)$100)(*&.%)x randg y'
mksym=: (+|:) @ (*<:/~@(i.@#))                                NB. make symmetric matrix
spm=: monad : '<./y(<./ .+)^:(i.#y)y'                         NB. shortest path between pairs of g matrix
ind=: adverb : '(i.@$*x)@]'                                   NB. spm _(=&0 ind)}h1 is shtst paths in h matrix

connected=: ~:&_@spm
reachable=: btoi each@<"1@connected
feasible=: ;@:((i.@#)(,each each)reachable)

Algorithms

ShtstPath1=: dyad : 0
if._=(<y){spm x do.'no path' return.end.
p=: i.0 [ r=: {.y [ 'src tgt'=: y                             NB. p=paths found
while.(-.tgt e.tails r)do.                                    NB. r=paths ongoing
  r=: (r-.p)-.(tails p)e.src [ p=: p,((tails r)e.tgt)#r
  r=: r extend x addnodes r end.                              NB. np=newpaths
r=: >(tgt=tails r)#r                                          NB. reject incomplete paths
)

tails=: {:&>                                                  NB. tails of list of lists
extend=: ;@:(JE"1 0 each)                                     NB. list to scalar joins
JE=: ,each &box                                               NB. scalarised join
box=. ]`<@.(-:>)                                              NB. boxes if unboxed, else do nothing
addnodes=: <@[rtoi each tails@]                               NB. new nodes
rtoi=: btoi@:(%@{~)                                           NB. btoi after _s into 0s

AllPaths=: dyad : 0
if._=(<y){spm x do.'no path' return.end.
p=: i.0 [ r=: {.y [ 'src tgt'=: y                             NB. initialise loop
while.(0~:#r)do.                                              NB. r = incomplete paths
  r=: r-.p [ p=: p,((tails r)e.tgt)#r                         NB. p = complete paths
  r=: r extend x addnodes r                                   NB. add one node to each r path
  r=: (#~((=&#~.)every))r                                     NB. remove loops
end. p
)

unweight=: monad : '(%@~:&0)y'
values=: +/@:([{~steps@])
steps=: <"(1)@(2&(,/\))

CritPath=: dyad :0                                            NB. critical path
if._=(<y){spm x do.'no path' return.end.
t=: ( unweight x)AllPaths y                                   NB. all paths
v=: >(<x) values each t                                       NB. all paths evaluated
(((=<./)v)#t),<<./v                                           NB. minimum value path selected
)

Slacks=: dyad :0
if._=(<y){spm x do.'no path' return.end.
t=: (unweight x)AllPaths y
>t JE each slack >(<x)values each t
)

slack=: -~>./

Loops=: dyad : 0
if._=(<y){spm x do.'no path' return.end.
l=: p=: i.0 [ r=: {.y [ 'src tgt'=: y                         NB. initialise loop
while.(0~:#r)do.                                              NB. r = incomplete paths
  r=: r-.p [ p=: p,((tails r)e.tgt)#r                         NB. p = complete paths
  r=: r extend x addnodes r                                   NB. add one node to each r path
  l=: l,(#~((~:&#~.)every))r                                  NB. remember loops
  r=: (#~((=&#~.)every))r                                     NB. remove loops
end.
)

Script

File:Fsojc38.ijs