1	# What ts2vg's command line prints: the edge list, the degree sequence, the
2	# degree counts and the degree distribution.
3	import Base
4	import ./graph.bend as G
5	
6	# Edges, one per line: `src dst`, then the weight when the graph is weighted.
7	
8	def weight_text(weighted: Bool, w: F32) -> String:
9	  match weighted:
10	    case True{}:
11	      " " ++ F32.show(w)
12	    case False{}:
13	      ""
14	
15	def edge_line(+weighted: Bool, s: U32, t: U32, w: F32) -> String:
16	  U32.show(s) ++ " " ++ U32.show(t) ++ weight_text(weighted, w) ++ "\n"
17	
18	def 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	
27	def 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.
38	def slots(+n: U32) -> Array<U32>:
39	  Array.new(U32, Nat.add(1n, U32.log2(n)), 0)
40	
41	def bump.set(+i: U32, r: Array<U32> & U32) -> Array<U32>:
42	  (d, v) = r
43	  Array.set(U32, d, i, (v + 1 : U32))
44	
45	def bump(d: Array<U32>, +i: U32) -> Array<U32>:
46	  bump.set(i, Array.get(U32, d, i))
47	
48	def added(r: Array<U32> & U32) -> Array<U32>:
49	  (d, old) = r
50	  d
51	
52	def 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.
57	def 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.
68	def 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	
77	def 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.
85	def 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.
90	def 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.
101	def 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	
108	def 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	
115	def 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	
124	def 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	
127	def 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	
134	def degree_counts(+share: Bool, +n: U32, d: Array<U32>) -> String:
135	  degree_counts.from(U32.is_zero(n), share, n, d)