MinaProtocol / mina / 353

Committed 09 Jul 2025 08:00PM UTC coverage: 31.655% (-29.3%) from 60.949%

Build # 353

Build Type

push

buildkite

Committed by

web-flow

Commit Message

Merge pull request #17485 from MinaProtocol/brian/more8s

Remove hardcoded state size where previosly missed

Run Details

2 of 8 new or added lines in 4 files covered. (25.0%)

19023 existing lines in 391 files now uncovered.

22662 of 71591 relevant lines covered (31.65%)

24587.72 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 / 353

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