MinaProtocol / mina / 641

Committed 30 Sep 2025 02:39AM UTC coverage: 32.179% (-29.2%) from 61.353%

Build # 641

Build Type

push

buildkite

Committed by

web-flow

Commit Message

Merge pull request #17874 from MinaProtocol/cjjdespres/rework-genesis-population

Rework, speed up root ledger population from genesis

Run Details

0 of 32 new or added lines in 5 files covered. (0.0%)

20703 existing lines in 409 files now uncovered.

23281 of 72349 relevant lines covered (32.18%)

23480.06 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

7.69

/src/lib/mina_stdlib/graph_algorithms.ml

1	module Nat = Nat	5✔
2	open Core_kernel
3
4	type 'a adjacency_list = ('a * 'a list) list
5
6	module Make (V : Comparable.S) = struct
7	module G = struct
8	type t = V.Set.t V.Map.t
9	end
10
11	let connected_component (g : G.t) v0 =
UNCOV 12	let rec go seen next =	×
UNCOV 13	match next with	×
UNCOV 14	\| [] ->	×
15	seen
UNCOV 16	\| v :: next ->	×
UNCOV 17	go (Set.add seen v)	×
UNCOV 18	( Option.value_map ~default:[]	×
UNCOV 19	~f:(fun neighbors -> Set.to_list (Set.diff neighbors seen))	×
UNCOV 20	(Map.find g v)	×
21	@ next )
22	in
23	go V.Set.empty [ v0 ]
24
25	let choose (g : G.t) : V.t option =
UNCOV 26	with_return (fun { return } ->	×
UNCOV 27	Map.iteri g ~f:(fun ~key ~data:_ -> return (Some key)) ;	×
UNCOV 28	None )	×
29
30	let connected (g : G.t) : bool =
UNCOV 31	match choose g with	×
UNCOV 32	\| None ->	×
33	(* G is empty *)
34	true
UNCOV 35	\| Some v ->	×
UNCOV 36	Int.equal (Map.length g) (Set.length (connected_component g v))	×
37
38	let remove_vertex (g : G.t) v : G.t =
UNCOV 39	Map.remove g v \|> Map.map ~f:(Fn.flip Set.remove v)	×
40
41	(* Naive algorithm for computing the minimum number of vertices required to disconnect
42	a graph as
43	connectivity G =
44	if not (connected G)
45	then 0
46	else 1 + min_{v in V(G)} connectivity (G - v)
47	The function returns a lazy nat, because the algorithm naturally can
48	be seen as a search over sequences of vertices of increasing length,
49	and upon finishing examining all sequences of a given length, we learn
50	one more piece of information about the return value (i.e., whether it
51	is bigger than that length or equal to it.)
52	This means that the caller of this function can control how far this
53	search goes based on how much information they need. For example, if
54	they just want to know whether the graph is connected, they only need
55	to force the outermost constructor. In general, if they want to know
56	whether the connectivity is >= n, they only need to force the first
57	n + 1 constructors.
58	*)
59
60	let rec connectivity (g : G.t) : Nat.t =
UNCOV 61	lazy	×
UNCOV 62	( if not (connected g) then Z	×
63	else
UNCOV 64	S	×
65	( lazy
UNCOV 66	(Nat.min	×
UNCOV 67	(List.map (Map.keys g) ~f:(fun v ->	×
UNCOV 68	connectivity (remove_vertex g v) ) ) ) ) )	×
69	end
70
71	let connectivity (type a) (module V : Comparable.S with type t = a)
72	(adj : V.t adjacency_list) =
UNCOV 73	let module M = Make (V) in	×
74	let g : M.G.t =
UNCOV 75	V.Map.of_alist_exn (List.map adj ~f:(fun (x, xs) -> (x, V.Set.of_list xs)))	×
76	in
77	M.connectivity g	10✔

MinaProtocol / mina / 641

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous