src/report.bend
bend-visgraph@1.0.0.0 · 135 lines · 0 definitions
1# What ts2vg's command line prints: the edge list, the degree sequence, the
2# degree counts and the degree distribution.
3import Base
4import bend-visgraph@1.0.0.0/src/graph.bend as G
5
6# Edges, one per line: `src dst`, then the weight when the graph is weighted.
7
8def weight_text(weighted: Bool, w: F32) -> String:
9 match weighted:
10 case True{}:
11 " " ++ F32.show(w)
12 case False{}:
13 ""
14
15def edge_line(+weighted: Bool, s: U32, t: U32, w: F32) -> String:
16 U32.show(s) ++ " " ++ U32.show(t) ++ weight_text(weighted, w) ++ "\n"
17
18def edges_text(+weighted: Bool, es: G.Edges, acc: String) -> String:
19 match es:
20 case G.ENil{}:
21 acc
22 case G.ECon{s, t, w, next}:
23 edges_text(weighted, next, edge_line(weighted, s, t, w) ++ acc)
24 case G.EJoin{a, b}:
25 edges_text(weighted, b, edges_text(weighted, a, acc))
26
27def is_weighted(k: G.Weight) -> Bool:
28 match k:
29 case G.Unweighted{}:
30 False{}
31 case _:
32 True{}
33
34# Degrees: each edge adds one to the degree of both of its ends, as ts2vg's
35# degrees_in + degrees_out.
36
37# An array with room for `n` slots, indexed from 0.
38def slots(+n: U32) -> Array<U32>:
39 Array.new(U32, Nat.add(1n, U32.log2(n)), 0)
40
41def bump.set(+i: U32, r: Array<U32> & U32) -> Array<U32>:
42 (d, v) = r
43 Array.set(U32, d, i, (v + 1 : U32))
44
45def bump(d: Array<U32>, +i: U32) -> Array<U32>:
46 bump.set(i, Array.get(U32, d, i))
47
48def added(r: Array<U32> & U32) -> Array<U32>:
49 (d, old) = r
50 d
51
52def atomic_bump(d: Array<U32>, +i: U32) -> Array<U32>:
53 added(Array.atomic.add(d, i, 1))
54
55# The degrees of the nodes of `es`, added into `d`; parallel.bend counts
56# them on every thread.
57def degrees(es: G.Edges, d: Array<U32>) -> Array<U32>:
58 match es:
59 case G.ENil{}:
60 d
61 case G.ECon{s, t, w, next}:
62 degrees(next, atomic_bump(atomic_bump(d, s), t))
63 case G.EJoin{a, b}:
64 degrees(b, degrees(a, d))
65
66# The degree sequence, one per line. `r` is the degree array with the
67# degree of node `i`; the `f` nodes below `i` are still to print.
68def sequence_text(f: Nat, r: Array<U32> & U32, +i: U32, acc: String) -> String:
69 match f:
70 case 0n:
71 (d, v) = r
72 U32.show(v) ++ "\n" ++ acc
73 case 1n+q:
74 (d, v) = r
75 sequence_text(q, Array.get(U32, d, (i - 1 : U32)), (i - 1 : U32), U32.show(v) ++ "\n" ++ acc)
76
77def degree_sequence.from(empty: Bool, +n: U32, d: Array<U32>) -> String:
78 match empty:
79 case True{}:
80 ""
81 case False{}:
82 sequence_text(U32.to_nat((n - 1 : U32)), Array.get(U32, d, (n - 1 : U32)), (n - 1 : U32), "")
83
84# The degree sequence of the `n` nodes whose degrees `d` holds.
85def degree_sequence(+n: U32, d: Array<U32>) -> String:
86 degree_sequence.from(U32.is_zero(n), n, d)
87
88# How many nodes have each degree: `r` is the degree array with the degree
89# of node `i`; the `f` nodes above `i` are still to count.
90def count_loop(f: Nat, r: Array<U32> & U32, +i: U32, c: Array<U32>) -> Array<U32>:
91 match f:
92 case 0n:
93 (d, v) = r
94 bump(c, v)
95 case 1n+q:
96 (d, v) = r
97 count_loop(q, Array.get(U32, d, (i + 1 : U32)), (i + 1 : U32), bump(c, v))
98
99# Degree counts or the degree distribution: `k count` or `k count/n` for
100# each degree k some node has, from the smallest k.
101def count_value(share: Bool, +v: U32, +n: U32) -> String:
102 match share:
103 case True{}:
104 F32.show(F32.div(U32.to_f32(v), U32.to_f32(n)))
105 case False{}:
106 U32.show(v)
107
108def count_line(zero: Bool, +share: Bool, +k: U32, +v: U32, +n: U32, acc: String) -> String:
109 match zero:
110 case True{}:
111 acc
112 case False{}:
113 U32.show(k) ++ " " ++ count_value(share, v, n) ++ "\n" ++ acc
114
115def counts_text(f: Nat, +share: Bool, +n: U32, r: Array<U32> & U32, +k: U32, acc: String) -> String:
116 match f:
117 case 0n:
118 (c, +v) = r
119 count_line(U32.is_zero(v), share, k, v, n, acc)
120 case 1n+q:
121 (c, +v) = r
122 counts_text(q, share, n, Array.get(U32, c, (k - 1 : U32)), (k - 1 : U32), count_line(U32.is_zero(v), share, k, v, n, acc))
123
124def degree_counts.text(+share: Bool, +n: U32, c: Array<U32>) -> String:
125 counts_text(U32.to_nat((n - 1 : U32)), share, n, Array.get(U32, c, (n - 1 : U32)), (n - 1 : U32), "")
126
127def degree_counts.from(empty: Bool, +share: Bool, +n: U32, d: Array<U32>) -> String:
128 match empty:
129 case True{}:
130 ""
131 case False{}:
132 degree_counts.text(share, n, count_loop(U32.to_nat((n - 1 : U32)), Array.get(U32, d, 0), 0, slots(n)))
133
134def degree_counts(+share: Bool, +n: U32, d: Array<U32>) -> String:
135 degree_counts.from(U32.is_zero(n), share, n, d)