Fifty Shades of J/Chapter 38
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
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 :
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.
)