Detect cycle in undirected graph in Ocaml

Question

Does someone has idea how to detect if there is a cycle in undirected graph in OCaml?

Here's the type I'm using for graph:

type 'a graph = { 
  nodes : 'a list; 
  edges : ('a * 'a * int) list 
}

And for example, I would like to check if this graph contains cycles:

let graph = { 
  nodes = ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'; 'j';]; 
  edges = [
    ('c', 'j', 9); ('d', 'e', 8); ('a', 'b', 8); 
    ('b', 'c', 7); ('f', 'g', 6); ('b', 'h', 4); 
    ('a', 'd', 4); ('g', 'h', 2); ('b', 'f', 2); 
    ('e', 'g', 1)
  ]
}

Answer 1

I managed to detect cycle by using union-find data structure.

A structure to represent a subset for union-find:

let create n =
    {parent = Array.init n (fun i -> i);
     rank = Array.init n (fun i -> 0)} 

A utility function to find set of an element. It uses path compression technique:

let rec find uf i =
  let pi = uf.parent.(i) in
  if pi == i then
     i
  else begin
     let ci = find uf pi in
     uf.parent.(i) <- ci;
     ci
  end

A function that does union of two sets of x and y. It uses union by rank:

let union ({ parent = p; rank = r } as uf) x y =
    let cx = find uf x in
    let cy = find uf y in
    if cx == cy then raise (Failure "Cycle detected") else  begin
       if r.(cx) > r.(cy) then
          p.(cy) <- cx
       else if r.(cx) < r.(cy) then
          p.(cx) <- cy
       else begin
          r.(cx) <- r.(cx) + 1;
          p.(cy) <- cx
       end
    end

I created function for checking if there is a cycle.

let thereIsCycle c1 c2 g subset =
  let isCycle = try Some (union subset (findIndex c1 g.nodes) (findIndex c2 g.nodes)) with _ -> None in
      match isCycle with
     | Some isCycle -> false
     | None -> true

let rec findIndex x lst =
    match lst with
    | [] -> raise (Failure "Not Found")
    | h :: t -> if x = h then 0 else 1 + findIndex x t