module type VertexSig = sig
      val t : 'a
      val compare : 'a -> 'a -> int
    end

module Graph(Vertex : VertexSig) : sig
  module VertexSet : Set.S with type elt = Vertex.t
  module EdgeSet : Set.S with type elt = Vertex.t * Vertex.t

  val add_vertex : VertexSet.elt -> VertexSet.t * 'a -> VertexSet.t
  val add_edge : VertexSet.elt * VertexSet.elt -> VertexSet.t * VertexSet.t -> VertexSet.t

  val get_edges : Vertex.t -> 'a * EdgeSet.t -> EdgeSet.t

  val remove_vertex : Vertex.t -> VertexSet.t * EdgeSet.t -> VertexSet.t * EdgeSet.t
  val remove_edge : Vertex.t * Vertex.t -> 'a * EdgeSet.t -> EdgeSet.t

  exception Vertex_not_found
end =
  struct


    module Edge =
      struct
        type t = Vertex.t * Vertex.t (* Error: Unbound type constructor Vertex.t *)

        let compare (a, _) (b, _) = Vertex.compare a b
      end

    module EdgeSet = Set.Make(Edge)
    module VertexSet = Set.Make(Vertex)

    let add_vertex v (vset, eset) = VertexSet.add v vset

    let get_edges v (vset, eset) = EdgeSet.filter (fun (u, _) -> (compare u v) = 0) eset

    let remove_vertex v (vset, eset) =
      let edges_from = get_edges v (vset, eset) in
      let edges_to = EdgeSet.filter (fun (_, u) -> (compare u v) = 0) eset in
      let edges = EdgeSet.diff (EdgeSet.diff eset edges_from) edges_to in
      let vertices = VertexSet.remove v vset in
      (vertices, edges)

    exception Vertex_not_found

    let add_edge (v, u) (vset, eset) =
      if VertexSet.exists (fun e -> e = v) vset && VertexSet.exists (fun e -> (compare e u) = 0) vset
      then VertexSet.add v eset
      else raise Vertex_not_found

    let remove_edge (v, u) (vset, eset) = EdgeSet.remove (v, u) eset

  end;;