bend_visgraph.bend
bend-visgraph@1.0.1.0 · 284 lines · 0 definitions
1# ts2vg's visibility graphs of time series, in Bend2, on every CPU thread.
2# Docs, tests and benchmark: https://github.com/aaaxn/bend-visgraph
3#
4# bend-visgraph's command line takes ts2vg's options with the input first:
5# bend_visgraph INPUT [-o OUTPUT] [-x XS] [-t TYPE] [-d DIRECTED] [-w WEIGHTED] [-p LIMIT] [-m MODE]
6# where XS, which ts2vg's command line lacks, holds the x of each value.
7import Base
8import bend-visgraph@1.0.1.0/src/graph.bend as G
9import bend-visgraph@1.0.1.0/src/parallel.bend as Par
10import bend-visgraph@1.0.1.0/src/series.bend as Series
11import bend-visgraph@1.0.1.0/src/report.bend as Report
12import bend-visgraph@1.0.1.0/src/vg.bend as VG
13
14type Mode is Data:
15 EdgeList{}
16 DegreeSequence{}
17 DegreeDistribution{}
18 DegreeCounts{}
19
20type Flag is Data:
21 Output{}
22 XFile{}
23 GraphType{}
24 Directed{}
25 Weighted{}
26 Limit{}
27 OutputMode{}
28
29type Entry<-A: Data> is Data:
30 Entry{name: String, value: A}
31
32type Config is Data:
33 Config{output: String, xs: String, g: G.Graph, dir: G.Direction, k: G.Weight, limit: U32, mode: Mode}
34 Usage{msg: String}
35
36type Outcome is Data:
37 Ok{text: String}
38 Err{msg: String}
39
40def usage() -> String:
41 "usage: bend_visgraph INPUT [-o OUTPUT] [-x XS] [-t natural|horizontal] [-d left_to_right|top_to_bottom] [-w WEIGHT] [-p LIMIT] [-m el|ds|dd|dc]"
42
43# Option names
44
45def flags() -> List<&2, Entry<Flag>>:
46 [Entry{"-o", Output{}}, Entry{"--output", Output{}}, Entry{"-x", XFile{}}, Entry{"--xs", XFile{}}, Entry{"-t", GraphType{}}, Entry{"--type", GraphType{}},
47 Entry{"-d", Directed{}}, Entry{"--directed", Directed{}}, Entry{"-w", Weighted{}}, Entry{"--weighted", Weighted{}},
48 Entry{"-p", Limit{}}, Entry{"--penetrable_limit", Limit{}}, Entry{"-m", OutputMode{}}, Entry{"--outputmode", OutputMode{}}]
49
50def graphs() -> List<&2, Entry<G.Graph>>:
51 [Entry{"natural", G.Natural{}}, Entry{"horizontal", G.Horizontal{}}]
52
53def directions() -> List<&2, Entry<G.Direction>>:
54 [Entry{"left_to_right", G.LeftToRight{}}, Entry{"top_to_bottom", G.TopToBottom{}}]
55
56def weights() -> List<&2, Entry<G.Weight>>:
57 [Entry{"distance", G.Distance{}}, Entry{"sq_distance", G.SqDistance{}}, Entry{"v_distance", G.VDistance{}},
58 Entry{"abs_v_distance", G.AbsVDistance{}}, Entry{"h_distance", G.HDistance{}}, Entry{"abs_h_distance", G.AbsHDistance{}},
59 Entry{"slope", G.Slope{}}, Entry{"abs_slope", G.AbsSlope{}}, Entry{"angle", G.Angle{}}, Entry{"abs_angle", G.AbsAngle{}},
60 Entry{"num_penetrations", G.NumPenetrations{}}]
61
62def modes() -> List<&2, Entry<Mode>>:
63 [Entry{"el", EdgeList{}}, Entry{"ds", DegreeSequence{}}, Entry{"dd", DegreeDistribution{}}, Entry{"dc", DegreeCounts{}}]
64
65def lookup.hit(-A: Data, hit: Bool, v: A, rest: Maybe<&2, A>) -> Maybe<&2, A>:
66 match hit:
67 case True{}:
68 Some{v}
69 case False{}:
70 rest
71
72def lookup.entry(-A: Data, +s: String, e: Entry<A>, rest: Maybe<&2, A>) -> Maybe<&2, A>:
73 Entry{name, v} = e
74 lookup.hit(A, String.eq(s, name), v, rest)
75
76def lookup(-A: Data, +s: String, table: List<&2, Entry<A>>) -> Maybe<&2, A>:
77 match table:
78 case Nil{}:
79 None{}
80 case Con{e, rest}:
81 lookup.entry(A, s, e, lookup(A, s, rest))
82
83# Options
84
85def defaults() -> Config:
86 Config{"", "", G.Natural{}, G.Undirected{}, G.Unweighted{}, 0, EdgeList{}}
87
88def bad(name: String, value: String) -> Config:
89 Usage{"invalid value for " ++ name ++ ": " ++ value}
90
91def with_graph(found: Maybe<&2, G.Graph>, name: String, value: String, o: String, x: String, d: G.Direction, k: G.Weight, l: U32, m: Mode) -> Config:
92 match found:
93 case Some{g}:
94 Config{o, x, g, d, k, l, m}
95 case None{}:
96 bad(name, value)
97
98def with_direction(found: Maybe<&2, G.Direction>, name: String, value: String, o: String, x: String, g: G.Graph, k: G.Weight, l: U32, m: Mode) -> Config:
99 match found:
100 case Some{d}:
101 Config{o, x, g, d, k, l, m}
102 case None{}:
103 bad(name, value)
104
105def with_weight(found: Maybe<&2, G.Weight>, name: String, value: String, o: String, x: String, g: G.Graph, d: G.Direction, l: U32, m: Mode) -> Config:
106 match found:
107 case Some{k}:
108 Config{o, x, g, d, k, l, m}
109 case None{}:
110 bad(name, value)
111
112def with_limit(found: Maybe<&2, U32>, name: String, value: String, o: String, x: String, g: G.Graph, d: G.Direction, k: G.Weight, m: Mode) -> Config:
113 match found:
114 case Some{l}:
115 Config{o, x, g, d, k, l, m}
116 case None{}:
117 bad(name, value)
118
119def with_mode(found: Maybe<&2, Mode>, name: String, value: String, o: String, x: String, g: G.Graph, d: G.Direction, k: G.Weight, l: U32) -> Config:
120 match found:
121 case Some{m}:
122 Config{o, x, g, d, k, l, m}
123 case None{}:
124 bad(name, value)
125
126def set(cfg: Config, flag: Maybe<&2, Flag>, +name: String, +value: String) -> Config:
127 match cfg flag:
128 case Usage{msg} _:
129 Usage{msg}
130 case Config{o, x, g, d, k, l, m} None{}:
131 Usage{"unknown option: " ++ name}
132 case Config{o, x, g, d, k, l, m} Some{Output{}}:
133 Config{value, x, g, d, k, l, m}
134 case Config{o, x, g, d, k, l, m} Some{XFile{}}:
135 Config{o, value, g, d, k, l, m}
136 case Config{o, x, g, d, k, l, m} Some{GraphType{}}:
137 with_graph(lookup(G.Graph, value, graphs()), name, value, o, x, d, k, l, m)
138 case Config{o, x, g, d, k, l, m} Some{Directed{}}:
139 with_direction(lookup(G.Direction, value, directions()), name, value, o, x, g, k, l, m)
140 case Config{o, x, g, d, k, l, m} Some{Weighted{}}:
141 with_weight(lookup(G.Weight, value, weights()), name, value, o, x, g, d, l, m)
142 case Config{o, x, g, d, k, l, m} Some{Limit{}}:
143 with_limit(U32.read(value), name, value, o, x, g, d, k, m)
144 case Config{o, x, g, d, k, l, m} Some{OutputMode{}}:
145 with_mode(lookup(Mode, value, modes()), name, value, o, x, g, d, k, l)
146
147def parse(opts: List<String>, cfg: Config) -> Config:
148 match opts:
149 case Nil{}:
150 cfg
151 case Con{+name, Con{value, rest}}:
152 parse(rest, set(cfg, lookup(Flag, name, flags()), name, value))
153 case Con{name, Nil{}}:
154 Usage{"missing value for " ++ name}
155
156# The graph and what to print of it
157
158def output(mode: Mode, +k: G.Weight, es: G.Edges, +n: U32) -> String:
159 match mode:
160 case EdgeList{}:
161 Report.edges_text(Report.is_weighted(k), es, "")
162 case DegreeSequence{}:
163 Report.degree_sequence(n, Par.degrees(es, n))
164 case DegreeDistribution{}:
165 Report.degree_counts(True{}, n, Par.degrees(es, n))
166 case DegreeCounts{}:
167 Report.degree_counts(False{}, n, Par.degrees(es, n))
168
169def only_degrees(mode: Mode) -> Bool:
170 match mode:
171 case EdgeList{}:
172 False{}
173 case _:
174 True{}
175
176def graph_of(+g: G.Graph, +dir: G.Direction, +k: G.Weight, +limit: U32, ys: Array<F32>, xs: G.Xs, +n: U32) -> G.Edges:
177 Par.build(VG.Options{g, dir, k, G.neg_inf(), G.inf(), limit}, VG.Series{n, ys, xs})
178
179# Where x comes from: the index, or the values of the -x file, last first.
180type XSource is Data:
181 ByIndex{}
182 Given{rev: List<&2, F32>}
183
184def xs_of(x: XSource, +n: U32) -> G.Xs:
185 match x:
186 case ByIndex{}:
187 G.Index{}
188 case Given{rev}:
189 G.At{Series.ys(rev, n)}
190
191def report.built(weighted_degrees: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +limit: U32, mode: Mode, rev: List<&2, F32>, x: XSource, +n: U32) -> Outcome:
192 match weighted_degrees:
193 case True{}:
194 Err{"Building with 'only_degrees' is only supported for unweighted graphs."}
195 case False{}:
196 Ok{output(mode, k, graph_of(g, dir, k, limit, Series.ys(rev, n), xs_of(x, n), n), n)}
197
198# x as the index is an F32, which holds every index below 2^24 exactly.
199def report.sized(too_long: Bool, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +limit: U32, +mode: Mode, rev: List<&2, F32>, +n: U32) -> Outcome:
200 match too_long:
201 case True{}:
202 Err{"bend_visgraph takes at most 16777216 values, since x is the index as an F32"}
203 case False{}:
204 report.built(only_degrees(mode) && Report.is_weighted(k), g, dir, k, limit, mode, rev, ByIndex{}, n)
205
206def report.xs(x: Series.XsCheck, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +limit: U32, +mode: Mode, rev: List<&2, F32>, +n: U32) -> Outcome:
207 match x:
208 case Series.XsBad{msg}:
209 Err{msg}
210 case Series.XsOk{xrev}:
211 report.built(only_degrees(mode) && Report.is_weighted(k), g, dir, k, limit, mode, rev, Given{xrev}, n)
212
213# The x coordinates of the -x file, if one was given.
214type XsIn is Data:
215 NoXs{}
216 XsRead{p: Series.Parsed}
217
218def report(p: Series.Parsed, x: XsIn, +g: G.Graph, +dir: G.Direction, +k: G.Weight, +limit: U32, +mode: Mode) -> Outcome:
219 match p x:
220 case Series.Bad{line} _:
221 Err{"line " ++ U32.show(line) ++ " holds no number"}
222 case Series.Values{rev, +n} NoXs{}:
223 report.sized(U32.is_gt(n, 16777216), g, dir, k, limit, mode, rev, n)
224 case Series.Values{rev, +n} XsRead{xp}:
225 report.xs(Series.xs(xp, n), g, dir, k, limit, mode, rev, n)
226
227# Files
228
229def write_text.done(m: File & Result<&1, &1, U32 & String, Unit>) -> IO(Unit):
230 (f, r) = m
231 do IO<Unit>:
232 done : Unit <- IO.pass(Unit, r)
233 File.close(f)
234
235def write_text(path: String, text: String) -> IO(Unit):
236 do IO<Unit>:
237 f : File <- IO.try(File, File.open(path, "w"))
238 m : File & Result<&1, &1, U32 & String, Unit> <- File.write(f, text)
239 write_text.done(m)
240
241def emit.to(stdout: Bool, path: String, text: String) -> IO(Unit):
242 match stdout:
243 case True{}:
244 IO.write(text)
245 case False{}:
246 write_text(path, text)
247
248def emit(+path: String, outcome: Outcome) -> IO(Unit):
249 match outcome:
250 case Ok{text}:
251 emit.to(String.is_empty(path), path, text)
252 case Err{msg}:
253 IO.die(Unit, 1, msg)
254
255def read_xs(none: Bool, path: String) -> IO(XsIn):
256 match none:
257 case True{}:
258 IO.pure(XsIn, NoXs{})
259 case False{}:
260 do IO<XsIn>:
261 text : String <- Series.read_text(path)
262 return XsRead{Series.parse(text)}
263
264def run(input: String, cfg: Config) -> IO(Unit):
265 match cfg:
266 case Usage{msg}:
267 IO.die(Unit, 2, msg ++ "\n" ++ usage())
268 case Config{+out, +xpath, g, dir, k, limit, mode}:
269 do IO<Unit>:
270 text : String <- Series.read_text(input)
271 x : XsIn <- read_xs(String.is_empty(xpath), xpath)
272 emit(out, report(Series.parse(text), x, g, dir, k, limit, mode))
273
274def start(args: List<String>) -> IO(Unit):
275 match args:
276 case Con{prog, Con{input, opts}}:
277 run(input, parse(opts, defaults()))
278 case _:
279 IO.die(Unit, 2, usage())
280
281def main() -> IO(Unit):
282 do IO<Unit>:
283 args : List<String> <- IO.args()
284 start(args)