src/report.bend

bend-visgraph@2.0.0.0 · 115 lines · 17 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@2.0.0.0/visgraph.bend as VG
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: VG.Edges, acc: String) -> String:
19  match es:
20    case VG.ENil{}:
21      acc
22    case VG.ECon{s, t, w, next}:
23      edges_text(weighted, next, edge_line(weighted, s, t, w) ++ acc)
24    case VG.EJoin{a, b}:
25      edges_text(weighted, b, edges_text(weighted, a, acc))
26
27def is_weighted(k: VG.Weight) -> Bool:
28  match k:
29    case VG.Unweighted{}:
30      False{}
31    case _:
32      True{}
33
34def bump.set(+i: U32, r: Array<U32> & U32) -> Array<U32>:
35  (d, v) = r
36  Array.set(U32, d, i, (v + 1 : U32))
37
38def bump(d: Array<U32>, +i: U32) -> Array<U32>:
39  bump.set(i, Array.get(U32, d, i))
40
41# The degree sequence, one per line. `r` is the degree array with the
42# degree of node `i`; the `f` nodes below `i` are still to print.
43def sequence_text(f: Nat, r: Array<U32> & U32, +i: U32, acc: String) -> String:
44  match f:
45    case 0n:
46      (d, v) = r
47      U32.show(v) ++ "\n" ++ acc
48    case 1n+q:
49      (d, v) = r
50      sequence_text(q, Array.get(U32, d, (i - 1 : U32)), (i - 1 : U32), U32.show(v) ++ "\n" ++ acc)
51
52def degree_sequence.from(empty: Bool, +n: U32, d: Array<U32>) -> String:
53  match empty:
54    case True{}:
55      ""
56    case False{}:
57      sequence_text(U32.to_nat((n - 1 : U32)), Array.get(U32, d, (n - 1 : U32)), (n - 1 : U32), "")
58
59# The degree sequence of the `n` nodes whose degrees `d` holds.
60def degree_sequence(+n: U32, d: Array<U32>) -> String:
61  degree_sequence.from(U32.is_zero(n), n, d)
62
63# How many nodes have each degree: `r` is the degree array with the degree
64# of node `i`; the `f` nodes above `i` are still to count.
65def count_loop(f: Nat, r: Array<U32> & U32, +i: U32, c: Array<U32>) -> Array<U32>:
66  match f:
67    case 0n:
68      (d, v) = r
69      bump(c, v)
70    case 1n+q:
71      (d, v) = r
72      count_loop(q, Array.get(U32, d, (i + 1 : U32)), (i + 1 : U32), bump(c, v))
73
74# Degree counts or the degree distribution: `k count` or `k count/n` for
75# each degree k some node has, from the smallest k.
76def count_value(share: Bool, +v: U32, +n: U32) -> String:
77  match share:
78    case True{}:
79      F32.show(F32.div(U32.to_f32(v), U32.to_f32(n)))
80    case False{}:
81      U32.show(v)
82
83def count_line(zero: Bool, +share: Bool, +k: U32, +v: U32, +n: U32, acc: String) -> String:
84  match zero:
85    case True{}:
86      acc
87    case False{}:
88      U32.show(k) ++ " " ++ count_value(share, v, n) ++ "\n" ++ acc
89
90def counts_text(f: Nat, +share: Bool, +n: U32, r: Array<U32> & U32, +k: U32, acc: String) -> String:
91  match f:
92    case 0n:
93      (c, +v) = r
94      count_line(U32.is_zero(v), share, k, v, n, acc)
95    case 1n+q:
96      (c, +v) = r
97      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))
98
99def degree_counts.text(+share: Bool, +n: U32, c: Array<U32>) -> String:
100  counts_text(U32.to_nat((n - 1 : U32)), share, n, Array.get(U32, c, (n - 1 : U32)), (n - 1 : U32), "")
101
102def degree_counts.from(empty: Bool, +share: Bool, +n: U32, d: Array<U32>) -> String:
103  match empty:
104    case True{}:
105      ""
106    case False{}:
107      degree_counts.text(share, n, count_loop(U32.to_nat((n - 1 : U32)), Array.get(U32, d, 0), 0, VG.slots(n)))
108
109def degree_counts(+share: Bool, +n: U32, d: Array<U32>) -> String:
110  degree_counts.from(U32.is_zero(n), share, n, d)
111
112# The edge list of `g`.
113def edge_list(+weighted: Bool, g: VG.Graph) -> String:
114  VG.Graph{n, dir, es} = g
115  edges_text(weighted, es, "")