Hello,

I'm defining a graph structure compatible with the ocamlgraph library.

I want to be able to access all neighbors and edge to neighbors of a vertex in 0(1), so I think I need to store the outgoing edge list of each vertex in the vertex structure. I also need to be able to access the source and destination of an edge in 0(1), so I store these vertex in the edge structure.

A standard Caml will be :

type vertex = {
    label : int;
    out_edges : edge list;
    ...
} and edge = {
    label : int;
    src : vertex;
    dst : vertex;
    ...
}

However, in ocamlgraph, the vertex and edge type must be defined by modules of signatures (and I cannot modify it) :

module type VERTEX = sig
    type t
    type label 
    val create : label -> t
    val label : t -> label
end
module type EDGE = sig
    type t
    type label
    type vertex
    val create : vertex -> label -> vertex -> t
    val label : t -> label
    val src : t -> vertex
    val dst : t -> vertex
end
module type GRAPH = sig
    module V : VERTEX
    module E : EDGE
    ...
end

Then the graph structure is generally created with a functor like :

module Make_Graph(V : VERTEX)(E : EDGE with type vertex = V.t) = struct
    module V = V
    module E = E
    ...
end

It works fine, but it doesn't respond to my problem : I want that V use a type from E and at the same time E use a type of V. So I write the following code :

module type MYVERTEX = sig
    include VERTEX
    type edge
    val out_edges : t -> edge list 
end

module MyVertex = struct
    type edge
    type t = { label : int; out_edges : edge list }
    let out_edges v = v.out_edges
    ...
end

module MyEdge = struct
    type vertex
    type t = { label : int; src : vertex; dst : vertex }
    ...
end

module Make_MyGraph(V : MYVERTEX with type edge = E.t)(E : EDGE with type vertex = V.t) = struct
    module V = V
    module E = E
    ...
end


The compiler found an error on "with type edge = E.t" : "Unbound type constructor E.t". I understood it, E has not been defined yet, but I want to do that any way : if I suppress "with type edge = E.t", the V.edge and E.t types are not the same (and some other functions inside Make_MyGraph won't work).


I tried things like :

module Make_MyGraph(VV : MYVERTEX)(EE : EDGE with type vertex = V.t) = struct
    module E = EE
    module V = VV with type edge = E.t (*ocamlc doesn't understand the with keyword here*)
    ...
end


or 

module Make_MyEdge(E : EDGE)(V : MYVERTEX with type edge = E.t) = struct
    include V
end
module Make_MyGraph(VV : MYVERTEX)(EE : EDGE with type vertex = VV.t) = struct
    module E = EE
    module V = Make_MyEdge(E)(VV) (*ocamlc doesn't accepte VV,
Modules do not match:
  sig type t = VV.t type label = VV.label type edge = VV.edge end
is not included in
  sig type t type label type edge = E.t end
*)
    ...
end


-- 

Damien Bobillot


Test.ml file :

===================

module type VERTEX = sig
    type t
    type label
end
module type EDGE = sig
    type t
    type label
    type vertex
end
module type MYVERTEX = sig
    include VERTEX
    type edge
end

module MyVertex = struct
    type edge
    type t = { label : int; out_edges : edge list }
end
module MyEdge = struct
    type vertex
    type t = { label : int; src : vertex; dst : vertex }
end
module Make_MyGraph(V : MYVERTEX with type edge = E.t)(E : EDGE with type vertex = V.t) = struct
    module V = V
    module E = E
end

(*module Make_MyGraph(VV : MYVERTEX)(EE : EDGE with type vertex = V.t) = struct
    module E = EE
    module V = VV with type edge = E.t
end*)

(*module Make_MyEdge(E : EDGE)(V : MYVERTEX with type edge = E.t) = struct
    include V
end
module Make_MyGraph(VV : MYVERTEX)(EE : EDGE with type vertex = VV.t) = struct
    module E = EE
    module V = Make_MyEdge(E)(VV)
end*)

===========