librarylibs/Graphs/src/Graphs.xtl
Graphs: graphs as adjacency matrices -- from edges, degrees, reachability, shortest paths, breadth-first levels, connected components. Import it with an alias of your choice: "g:" u_se< "Graphs". Put libs/Graphs/src on XETAL_PATH ("just path"); the reference is libs/Graphs/docs. Names with l: are exported; those under h: are private to this file.
A graph of n nodes, numbered 1 to n, is an n by n matrix: item i j is 1 when there is an edge from i to j (or, for s_hortest, the edge's length, 0 meaning none). Walks are matrix products: with the inner product '| '& a step from every node at once, with 'm_in '+ the shortest way through one more node.
Building
ˡa̲djacency : (Num a, Truthy a) => Int -> Int -> a
n a_djacency edges: the n by n matrix of the edges, given as 2 rows, from over to (directed).
ˡa̲djacency ← { n e → at ← (n × (f̲irst e) − 1) + f̲irst 1 d̲rop e ⍝ (from - 1) times n, plus to 0 + (n c̲at n) r̲eshape (r̲ange n × n) m̲ember? at ⍝ 0 + : as Ints }
ˡw̲eighted : Int -> Int -> Int
n w_eighted edges: the n by n matrix of edge lengths, given as 3 rows, from over to over length (directed; 0 where there is no edge).
ˡw̲eighted ← { n e → at ← (n × (f̲irst e) − 1) + f̲irst 1 d̲rop e len ← f̲irst 2 d̲rop e (n c̲at n) r̲eshape '{ c → k ← w̲here at = c◆ 0 = t̲ally k ? 0◆ f̲irst (f̲irst k) s̲elect len } e̲ach r̲ange n × n }
ˡu̲ndirected : (Truthy a, Truthy b) => a -> b
u_ndirected m: the graph with every edge going both ways.
ˡu̲ndirected ← { m → m ∨ o̲\ m }
ˡo̲utDegree : Num a => a -> a
o_utDegree m, i_nDegree m: how many edges leave and reach each node.
ˡo̲utDegree ← { m → '+ r̲/₂ m }
ˡi̲nDegree : Num a => a -> a
ˡi̲nDegree ← { m → '+ r̲/ m }
Reachability
ʰc̲lose : Truthy a => a -> a
Walks of length 1 to 2k: m with m times itself or-ed in, until it no longer grows.
ʰc̲lose ← { m → n ← m ∨ m '∨ '∧ i̲nner m n m̲atch m ? m ʰc̲lose n }
ˡr̲each : (Num a, Truthy b) => a -> b
r_each m: item i j is 1 when j can be reached from i by one or more edges (Warshall's transitive closure, by repeated squaring).
ˡr̲each ← { m → ʰc̲lose 0 < m }
Paths
ʰr̲elax : Num a => a -> a
Min-plus products until the distances settle.
ʰr̲elax ← { d → e ← d 'm̲in '+ i̲nner d e m̲atch d ? d ʰr̲elax e }
ˡs̲hortest : Num a => a -> Float
s_hortest w: the length of the shortest path from i to j, for edge lengths w (0 meaning no edge); 0 from a node to itself, -1 where there is no path (Floyd-Warshall by min-plus products).
ˡs̲hortest ← { w → n ← t̲ally w i ← (r̲ange n) '= t̲able r̲ange n d ← (f̲loat w) + far × f̲loat (w = 0) ∧ n̲ot i r ← ʰr̲elax d r − (f̲loat r ≥ far) × 1.0 + r ⍝ -1 where nothing reached }
Levels and components
ʰb̲fs : (Num a, Truthy a) => a -> a -> a -> a -> a -> a
The breadth-first frontier from seen nodes s, level by level.
ʰb̲fs ← { m s f k lv → 0 = '+ r̲/ f ? lv nxt ← (f '∨ '∧ i̲nner m) ∧ n̲ot s ((((m ʰb̲fs s ∨ nxt)_ nxt)_ k + 1)_ lv + (k + 1) × nxt) }
ˡl̲evels : Int -> Int -> Int
m l_evels s: how many edges from node s to each node (0 for s itself), -1 where it cannot be reached (breadth-first search).
ˡl̲evels ← { m s → (s < 1) ∨ s > t̲ally m ? @ p̲anic< "the graph's nodes are 1 to {t_ally m}: there is no node {s}" n ← t̲ally m start ← (r̲ange n) = s lv ← ((((m ʰb̲fs start)_ start)_ 0)_ (r̲ange n) × 0) lv − (lv = 0) ∧ n̲ot start }
ˡc̲omponents : Truthy a => a -> Int
c_omponents m: each node's component, numbered 1, 2, ... in order of their least node (edges taken both ways).
ˡc̲omponents ← { m → n ← t̲ally m r ← (ˡr̲each ˡu̲ndirected m) ∨ (r̲ange n) '= t̲able r̲ange n first ← '{ i → f̲irst w̲here i s̲elect r } e̲ach r̲ange n (u̲nique first) i̲ndexOf first }