(* ============================== Module Graph ============================== *)

module type OrderedType = sig
    type t
    val compare : t -> t -> int
end

(* Signature des graphes *)
module type MyGraph = sig
    type node
    module NodeSet : Set.S with type elt = node
    module NodeMap : Map.S with type key = node
    type graph

    val empty : graph
    val is_empty : graph -> bool

    val add_node : node -> graph -> graph
    val remove_node : node -> graph -> graph

    val add_edge : node -> node -> graph -> graph
    val remove_edge : node -> node -> graph -> graph

    val fold_node : (node -> 'a -> 'a) -> graph -> 'a -> 'a
    val fold_edge : (node -> node -> 'a -> 'a) -> graph -> 'a -> 'a

    val succs : node -> graph -> NodeSet.t
end

(* Foncteur pour faire des graphes *)
module Make (X : OrderedType) : (MyGraph with type node = X.t) = struct
    type node = X.t
    module NodeSet = Set.Make(X)
    module NodeMap = Map.Make(X)
    type graph = NodeSet.t NodeMap.t

    let empty = NodeMap.empty
    let is_empty g = NodeMap.is_empty g

    let add_node n g =
        if NodeMap.mem n g then g
        else NodeMap.add n NodeSet.empty g

    let remove_node n g =
        let g_without_n_and_its_succs = NodeMap.remove n g in
        NodeMap.fold (
            fun m m_succs g_prov ->
            NodeMap.add m (NodeSet.remove n m_succs) g_prov
        ) g_without_n_and_its_succs empty

    let add_edge src dst g =
        let src_succs =
            try NodeMap.find src g
            with Not_found -> NodeSet.empty in
        let src_succs_with_dist = NodeSet.add dst src_succs in
        let g2 = NodeMap.add src src_succs_with_dist g in
        add_node dst g2

    let remove_edge src dst g =
        try
            let src_succs = (NodeMap.find src g) in
            let src_succs_without_dist = NodeSet.remove dst src_succs in
            NodeMap.add src src_succs_without_dist g
        with Not_found -> g

    let fold_node f g v0 = NodeMap.fold (fun n n_succs acc -> f n acc) g v0

    let fold_edge f g v0 =
        NodeMap.fold (
            fun src src_succs acc -> NodeSet.fold (fun dst acc_src -> f src dst acc_src) src_succs acc
        ) g v0

    let succs n g = NodeMap.find n g;;
end

module Int : (OrderedType with type t = int) = struct
    type t = int
    let compare = compare
end

module MyStringGraph = Make(String);; (* Graphe dont les noeuds sont des String *)
module MyIntGraph = Make(Int);; (* Graphe dont les noeuds sont des int *)

let test = MyStringGraph.add_edge "n1" "n2" MyStringGraph.empty;;
let test = MyStringGraph.add_edge "n2" "n4" test;;
print_string "Nodes : "; print_string (MyStringGraph.fold_node (fun n acc -> (n^" - "^acc)) test "");;