1 module List = ListLabels
15 let incr counts k incr =
16 let prev = Opt.get (Map.get counts ~k) ~default:{parents=0; children=0} in
17 Map.set counts ~k ~v:(incr prev)
19 let incr_parents count = {count with parents = succ count.parents} in
20 let incr_children count = {count with children = succ count.children} in
21 let zero_children counts =
22 List.filter (Map.to_list counts) ~f:(fun (_, {children=c; _}) -> c = 0 )
24 let zero_parents counts =
25 List.filter (Map.to_list counts) ~f:(fun (_, {parents=p; _}) -> p = 0 )
28 List.fold_left pairs ~init:Map.empty ~f:(
30 let counts = incr counts p incr_children in
31 let counts = incr counts c incr_parents in
35 (* At least one node with no in-coming links and
36 * at least one node with no out-going links. *)
37 match (zero_parents counts, zero_children counts) with
38 | _ :: _, _ :: _ -> Ok ()
39 | _, _ -> Error `Cycle