src/vg.bend
bend-visgraph@1.0.0.0 · 220 lines · 0 definitions
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.
5import Base
6import bend-visgraph@1.0.0.0/src/graph.bend as G
7import bend-visgraph@1.0.0.0/src/penetrable.bend as P
8import bend-visgraph@1.0.0.0/src/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.
13type 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.
18def 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.
23type Series is Type:
24 Series{n: U32, ys: Array<F32>, xs: G.Xs}
25
26def 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
33def fill(vs: List<&2, F32>, +i: U32, a: Array<F32>) -> Array<F32>:
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
40def column(+n: U32, vs: List<&2, F32>) -> Array<F32>:
41 fill(vs, 0, Array.new(F32, Nat.add(1n, U32.log2(n)), 0.0))
42
43def 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.
47def series(+ys: List<&2, F32>) -> Series:
48 counted(length(ys, 0), ys)
49
50def 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.
55def series_at(xs: List<&2, F32>, +ys: List<&2, F32>) -> Series:
56 counted_at(length(ys, 0), xs, ys)
57
58def chosen(visibility: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +lo: F32, +hi: F32, +limit: U32, ys: Array<F32>, 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.
68def 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`.
77def 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.
88def degrees(es: G.Edges, +n: U32) -> Array<U32>:
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.
96type Adjacency is Type:
97 Adjacency{offsets: Array<U32>, targets: Array<U32>, weights: Array<F32>}
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
102def is_undirected(d: G.Direction) -> Bool:
103 match d:
104 case G.Undirected{}:
105 True{}
106 case _:
107 False{}
108
109def bumped(r: Array<U32> & U32, +i: U32) -> Array<U32>:
110 (a, +c) = r
111 Array.set(U32, a, i, (c + 1 : U32))
112
113type Counts is Type:
114 Counts{outs: Array<U32>, ins: Array<U32>}
115
116def 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
124def 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.
135def starts(count: Nat, +i: U32, r: Array<U32> & U32, +acc: U32) -> Array<U32>:
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.
146type Halves is Type:
147 Halves{cur: Array<U32>, us: Array<U32>, vs: Array<U32>, ws: Array<F32>}
148
149def put_half(+u: U32, +v: U32, +w: F32, r: Array<U32> & U32, us: Array<U32>, vs: Array<U32>, ws: Array<F32>) -> 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
153def 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
161def 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
170type Rows is Type:
171 Rows{cur: Array<U32>, targets: Array<U32>, weights: Array<F32>}
172
173def put_row(+u: U32, +v: U32, +w: F32, r: Array<U32> & U32, targets: Array<U32>, weights: Array<F32>) -> 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.
179def by_source(count: Nat, +p: U32, ur: Array<U32> & U32, vr: Array<U32> & U32, wr: Array<F32> & 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
194def slots_for(+n: U32) -> Nat:
195 Nat.add(1n, U32.log2(n))
196
197def rows_done(offsets: Array<U32>, r: Rows) -> Adjacency:
198 Rows{cur, targets, weights} = r
199 Adjacency{offsets, targets, weights}
200
201def rows_from(+h: U32, oc: Array<U32> & Array<U32>, 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
206def with_starts(es: G.Edges, +both: Bool, +h: U32, outs: Array<U32>, ins: Array<U32>) -> 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
209def with_total(es: G.Edges, +both: Bool, r: Array<U32> & U32, ins: Array<U32>) -> Adjacency:
210 (outs, +h) = r
211 with_starts(es, both, h, outs, ins)
212
213def 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.
219def 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)}))