module type EqualType =
    sig
        type t
        val equal : t -> t -> bool
    end

module type S =
    sig
        type node
        type t
        val empty : t
        val exists_node : node -> t -> bool
        val add_node : node -> t -> t
        val add_edge : node -> node -> t -> t
        val transitive_closure : node -> t -> node list
        val find_paths : node -> node -> t -> node list list
    end

module Make(Eq: EqualType) = struct

    type node = Eq.t

    (* adjacency lists representation of a digraph *)
    type t = (node * node list) list
    (* e.g.
        [ (a , [b; c; d]);
          (b , [f]);
          (c , []);
          (d , [f; b]);
          (f , []) ]
      refers to the graph:
        a ----> b --> f
        |\      ^     ^
        | \     |     |
        v  \    |    /
        c   `-> d---'
    *)

    (* checks if a node is equal to the first element of a pair *)
    let eqfirst n = fun p -> Eq.equal n (fst p)

    let empty = []

    let exists_node n = List.exists (eqfirst n)

    let add_node n g =
        if exists_node n g then g else (n, []) :: g

    (* plenty of room for optimization here.. *)
    let add_edge n1 n2 g =
        let g = add_node n1 g in
        let g = add_node n2 g in
        let al = List.assoc n1 g in
        (n1, n2 :: al) :: List.remove_assoc n1 g

    (* this is a hair tricky, so pay attention *)
    let rec transitive_closure n g =
        let rec tc_aux g acc n =
            if List.mem n acc then acc (* already seen this node *)
            else
                let acc = n :: acc in
                List.fold_left (tc_aux g) acc (List.assoc n g)
        in
            tc_aux g [] n

    (* a more general fold would be fun *)

    let find_paths n1 n2 g =
        (* find_path_aux takes these parameters:
            graph target_node current_path paths_accum node *)
        let rec find_path_aux g target cpath acc n =
            (* check if we've already seen this node in this path *)
            if List.mem n cpath then acc else
            let cpath = n :: cpath in
            if n = target then (List.rev cpath) :: acc else
            List.fold_left (find_path_aux g target cpath) acc (List.assoc n g)
        in
            find_path_aux g n2 [] [] n1

  end