1 # bend-vg's library: ts2vg's options and a series in, the edges of its 2 # visibility graph out. `build` here relies on no @unsafe def; 3 # src/parallel.bend's `build` takes the same arguments and runs on every 4 # thread. 5 import Base 6 import ./graph.bend as G 7 import ./penetrable.bend as P 8 import ./report.bend as Report 9 10 # The options of ts2vg's graph classes: the graph, how its edges point, 11 # their weight, the weights to keep (above `min_weight` and below 12 # `max_weight`), and how many points an edge may cross. 13 type Options is Data: 14 Options{graph: G.Graph, directed: G.Direction, weighted: G.Weight, min_weight: F32, max_weight: F32, penetrable_limit: U32} 15 16 # ts2vg's defaults for the graph `g`: undirected, unweighted, every weight 17 # kept, no point crossed. 18 def options(g: G.Graph) -> Options: 19 Options{g, G.Undirected{}, G.Unweighted{}, G.neg_inf(), G.inf(), 0} 20 21 # The `n` values `ys` of a time series, indexed from 0, and their x: the 22 # index, or `G.At{xs}` with the x of each value, increasing. 23 type Series is Type: 24 Series{n: U32, ys: Array, xs: G.Xs} 25 26 def length(vs: List<&2, F32>, +n: U32) -> U32: 27 match vs: 28 case Nil{}: 29 n 30 case Con{v, rest}: 31 length(rest, (n + 1 : U32)) 32 33 def fill(vs: List<&2, F32>, +i: U32, a: Array) -> Array: 34 match vs: 35 case Nil{}: 36 a 37 case Con{v, rest}: 38 fill(rest, (i + 1 : U32), Array.set(F32, a, i, v)) 39 40 def column(+n: U32, vs: List<&2, F32>) -> Array: 41 fill(vs, 0, Array.new(F32, Nat.add(1n, U32.log2(n)), 0.0)) 42 43 def counted(+n: U32, ys: List<&2, F32>) -> Series: 44 Series{n, column(n, ys), G.Index{}} 45 46 # The series of the values `ys`, each at its index. 47 def series(+ys: List<&2, F32>) -> Series: 48 counted(length(ys, 0), ys) 49 50 def counted_at(+n: U32, xs: List<&2, F32>, ys: List<&2, F32>) -> Series: 51 Series{n, column(n, ys), G.At{column(n, xs)}} 52 53 # The series of the values `ys` at `xs`, which must hold as many values, 54 # increasing. 55 def series_at(xs: List<&2, F32>, +ys: List<&2, F32>) -> Series: 56 counted_at(length(ys, 0), xs, ys) 57 58 def chosen(visibility: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, +limit: U32, ys: Array, xs: G.Xs, +n: U32) -> G.Edges: 59 match visibility: 60 case True{}: 61 G.build(g, dir, k, lo, hi, ys, xs, n) 62 case False{}: 63 P.build(g, dir, k, lo, hi, limit, ys, xs, n) 64 65 # The edges of the graph of `s` with the options `o`, as ts2vg's `build` 66 # makes them. The natural and horizontal graphs run on one thread, and the 67 # limited penetrable ones split their sweeps among every thread. 68 def build(o: Options, s: Series) -> G.Edges: 69 Options{g, dir, k, lo, hi, +limit} = o 70 Series{+n, ys, xs} = s 71 chosen(U32.is_zero(limit), g, dir, k, lo, hi, limit, ys, xs, n) 72 73 # What to read off the edges 74 75 # `f(acc, src, dst, w)` over every edge of `es`, in the order the rope 76 # holds them, from `acc`. 77 def fold(~A: Type, ~f: A -> U32 -> U32 -> F32 -> A, es: G.Edges, acc: A) -> A: 78 match es: 79 case G.ENil{}: 80 acc 81 case G.ECon{s, t, w, next}: 82 fold(~A, ~f, next, f(acc, s, t, w)) 83 case G.EJoin{a, b}: 84 fold(~A, ~f, b, fold(~A, ~f, a, acc)) 85 86 # The degree of each of the `n` nodes of `es`, as ts2vg's `degrees`: the 87 # edges at the node, in either direction. 88 def degrees(es: G.Edges, +n: U32) -> Array: 89 Report.degrees(es, Report.slots(n)) 90 91 # The graph as compressed rows: the neighbors of node i are 92 # `targets[offsets[i]]` up to `targets[offsets[i + 1]]`, increasing, and 93 # the weights of their edges sit at the same positions. An undirected 94 # graph's edge appears in the rows of both its ends, a directed one's in 95 # its source's row. 96 type Adjacency is Type: 97 Adjacency{offsets: Array, targets: Array, weights: Array} 98 99 # Each half edge (u, v), from u to v, goes into two passes of a counting 100 # sort: by v, then by u, so each row ends up in increasing order. 101 102 def is_undirected(d: G.Direction) -> Bool: 103 match d: 104 case G.Undirected{}: 105 True{} 106 case _: 107 False{} 108 109 def bumped(r: Array & U32, +i: U32) -> Array: 110 (a, +c) = r 111 Array.set(U32, a, i, (c + 1 : U32)) 112 113 type Counts is Type: 114 Counts{outs: Array, ins: Array} 115 116 def count_half(present: Bool, +u: U32, +v: U32, c: Counts) -> Counts: 117 match present: 118 case True{}: 119 Counts{outs, ins} = c 120 Counts{bumped(Array.get(U32, outs, u), u), bumped(Array.get(U32, ins, v), v)} 121 case False{}: 122 c 123 124 def count_halves(es: G.Edges, +both: Bool, c: Counts) -> Counts: 125 match es: 126 case G.ENil{}: 127 c 128 case G.ECon{+s, +t, w, next}: 129 count_halves(next, both, count_half(both, t, s, count_half(True{}, s, t, c))) 130 case G.EJoin{a, b}: 131 count_halves(b, both, count_halves(a, both, c)) 132 133 # The counts of `n` nodes, in place, as where each node's run starts; slot 134 # `n` gets the total. 135 def starts(count: Nat, +i: U32, r: Array & U32, +acc: U32) -> Array: 136 match count: 137 case 0n: 138 (a, c) = r 139 Array.set(U32, a, i, acc) 140 case 1n+k: 141 (a, +c) = r 142 +i2 = (i + 1 : U32) 143 starts(k, i2, Array.get(U32, Array.set(U32, a, i, acc), i2), (acc + c : U32)) 144 145 # The half edges, by target: source, target and weight at each position. 146 type Halves is Type: 147 Halves{cur: Array, us: Array, vs: Array, ws: Array} 148 149 def put_half(+u: U32, +v: U32, +w: F32, r: Array & U32, us: Array, vs: Array, ws: Array) -> Halves: 150 (cur, +p) = r 151 Halves{Array.set(U32, cur, v, (p + 1 : U32)), Array.set(U32, us, p, u), Array.set(U32, vs, p, v), Array.set(F32, ws, p, w)} 152 153 def place_half(present: Bool, +u: U32, +v: U32, +w: F32, h: Halves) -> Halves: 154 match present: 155 case True{}: 156 Halves{cur, us, vs, ws} = h 157 put_half(u, v, w, Array.get(U32, cur, v), us, vs, ws) 158 case False{}: 159 h 160 161 def by_target(es: G.Edges, +both: Bool, h: Halves) -> Halves: 162 match es: 163 case G.ENil{}: 164 h 165 case G.ECon{+s, +t, +w, next}: 166 by_target(next, both, place_half(both, t, s, w, place_half(True{}, s, t, w, h))) 167 case G.EJoin{a, b}: 168 by_target(b, both, by_target(a, both, h)) 169 170 type Rows is Type: 171 Rows{cur: Array, targets: Array, weights: Array} 172 173 def put_row(+u: U32, +v: U32, +w: F32, r: Array & U32, targets: Array, weights: Array) -> Rows: 174 (cur, +p) = r 175 Rows{Array.set(U32, cur, u, (p + 1 : U32)), Array.set(U32, targets, p, v), Array.set(F32, weights, p, w)} 176 177 # The half edges from position `p` on, in target order, into their 178 # sources' rows. 179 def by_source(count: Nat, +p: U32, ur: Array & U32, vr: Array & U32, wr: Array & F32, out: Rows) -> Rows: 180 match count: 181 case 0n: 182 (us, u) = ur 183 (vs, v) = vr 184 (ws, w) = wr 185 out 186 case 1n+k: 187 (us, +u) = ur 188 (vs, +v) = vr 189 (ws, +w) = wr 190 Rows{cur, targets, weights} = out 191 +p2 = (p + 1 : U32) 192 by_source(k, p2, Array.get(U32, us, p2), Array.get(U32, vs, p2), Array.get(F32, ws, p2), put_row(u, v, w, Array.get(U32, cur, u), targets, weights)) 193 194 def slots_for(+n: U32) -> Nat: 195 Nat.add(1n, U32.log2(n)) 196 197 def rows_done(offsets: Array, r: Rows) -> Adjacency: 198 Rows{cur, targets, weights} = r 199 Adjacency{offsets, targets, weights} 200 201 def rows_from(+h: U32, oc: Array & Array, hv: Halves) -> Adjacency: 202 (offsets, cur) = oc 203 Halves{tcur, us, vs, ws} = hv 204 rows_done(offsets, by_source(U32.to_nat(h), 0, Array.get(U32, us, 0), Array.get(U32, vs, 0), Array.get(F32, ws, 0), Rows{cur, Array.new(U32, slots_for(h), 0), Array.new(F32, slots_for(h), 0.0)})) 205 206 def with_starts(es: G.Edges, +both: Bool, +h: U32, outs: Array, ins: Array) -> Adjacency: 207 rows_from(h, Array.clone(U32, outs), by_target(es, both, Halves{ins, Array.new(U32, slots_for(h), 0), Array.new(U32, slots_for(h), 0), Array.new(F32, slots_for(h), 0.0)})) 208 209 def with_total(es: G.Edges, +both: Bool, r: Array & U32, ins: Array) -> Adjacency: 210 (outs, +h) = r 211 with_starts(es, both, h, outs, ins) 212 213 def tallied(es: G.Edges, +both: Bool, +n: U32, c: Counts) -> Adjacency: 214 Counts{outs, ins} = c 215 with_total(es, both, Array.get(U32, starts(U32.to_nat(n), 0, Array.get(U32, outs, 0), 0), n), starts(U32.to_nat(n), 0, Array.get(U32, ins, 0), 0)) 216 217 # The rows of the `n` nodes of `es`, a graph whose edges point as `dir` 218 # says. 219 def adjacency(+dir: G.Direction, +es: G.Edges, +n: U32) -> Adjacency: 220 tallied(es, is_undirected(dir), n, count_halves(es, is_undirected(dir), Counts{Array.new(U32, slots_for(n), 0), Array.new(U32, slots_for(n), 0)}))