ocamlgraph ConcreteBidirectional and Dot

ocamlgraph ConcreteBidirectional and Dot

[Pietro Abate]

Hello all.

I've a small problem with ocamlgraph.
I want to parse a dot graph into a ConcreteBidirectional.

The problem is that the signature needed for Dot.Parse requires a function
edge, but I've no mean to specify a label (since it is unlabelled !!)... 

The functor for ConcreteBidirectional says E.t = (V.t * V.t), 
but I don't quite understand the type of B.G.E.label ... 

ConcreteBidirectional is of type Sig.I with
with type V.t = V.t and type V.label = V.t and type E.t = V.t * V.t

Sig.I includes Sig.G

and Sig.G has E: Sig.EDGE  with type vertex = vertex
but I'm missing the type of label for unlabelled graphs ... that should be
an implementation detail, isn't it ?

I tried to look at the implementation of per_imp.ml but I got a bit lost...

this is what I'm trying to do: 

-------------------
module V = struct
    type t = string
    let compare = Pervasives.compare
    let hash = Hashtbl.hash
    let equal l1 l2 = (l1 = l2)
end

module G = Imperative.Digraph.ConcreteBidirectional(V)

module B = Builder.I(G)

module L = struct
  open Dot_ast
  let node (id,_) attrs = match id with
    | Ident i -> i
    | Number n -> n
    | String s -> s
    | Html h -> h
  let edge l = ""
end

module DIn = Dot.Parse (B)(L)

---------------

the problem is:

Error: Signature mismatch:
       Modules do not match:
         sig
           val node : Graph.Dot_ast.id * 'a -> 'b -> string
           val edge : 'a -> string
         end
       is not included in
         sig
           val node :
             Graph.Dot_ast.node_id -> Graph.Dot_ast.attr list -> B.G.V.label
           val edge : Graph.Dot_ast.attr list -> B.G.E.label
         end
       Values do not match:
         val edge : 'a -> string
       is not included in
         val edge : Graph.Dot_ast.attr list -> B.G.E.label
Command exited with code 2.

Re: [Caml-list] ocamlgraph ConcreteBidirectional and Dot

[Pietro Abate]

I still don't have an answer for this problem, but I'm wondering now ...
is there a way to create a Labeled ConcreteBidirectional reusing these
building blocks ? 

is there an ocamlgraph specific ml ?

:)
p


On Fri, Apr 03, 2009 at 02:37:19PM +0200, Pietro Abate wrote:
> Hello all.
> 
> I've a small problem with ocamlgraph.
> I want to parse a dot graph into a ConcreteBidirectional.
> 
> The problem is that the signature needed for Dot.Parse requires a function
> edge, but I've no mean to specify a label (since it is unlabelled !!)... 
> 
> The functor for ConcreteBidirectional says E.t = (V.t * V.t), 
> but I don't quite understand the type of B.G.E.label ... 
> 
> ConcreteBidirectional is of type Sig.I with
> with type V.t = V.t and type V.label = V.t and type E.t = V.t * V.t
> 
> Sig.I includes Sig.G
> 
> and Sig.G has E: Sig.EDGE  with type vertex = vertex
> but I'm missing the type of label for unlabelled graphs ... that should be
> an implementation detail, isn't it ?
> 
> I tried to look at the implementation of per_imp.ml but I got a bit lost...
> 
> this is what I'm trying to do: 
> 
> -------------------
> module V = struct
>     type t = string
>     let compare = Pervasives.compare
>     let hash = Hashtbl.hash
>     let equal l1 l2 = (l1 = l2)
> end
> 
> module G = Imperative.Digraph.ConcreteBidirectional(V)
> 
> module B = Builder.I(G)
> 
> module L = struct
>   open Dot_ast
>   let node (id,_) attrs = match id with
>     | Ident i -> i
>     | Number n -> n
>     | String s -> s
>     | Html h -> h
>   let edge l = ""
> end
> 
> module DIn = Dot.Parse (B)(L)
> 
> ---------------
> 
> the problem is:
> 
> Error: Signature mismatch:
>        Modules do not match:
>          sig
>            val node : Graph.Dot_ast.id * 'a -> 'b -> string
>            val edge : 'a -> string
>          end
>        is not included in
>          sig
>            val node :
>              Graph.Dot_ast.node_id -> Graph.Dot_ast.attr list -> B.G.V.label
>            val edge : Graph.Dot_ast.attr list -> B.G.E.label
>          end
>        Values do not match:
>          val edge : 'a -> string
>        is not included in
>          val edge : Graph.Dot_ast.attr list -> B.G.E.label
> Command exited with code 2.
> 
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] ocamlgraph ConcreteBidirectional and Dot

[Jean-Christophe Filliâtre]

Hi,

Sorry for the late answer...

> I've a small problem with ocamlgraph.
> I want to parse a dot graph into a ConcreteBidirectional.
> 
> The problem is that the signature needed for Dot.Parse requires a function
> edge, but I've no mean to specify a label (since it is unlabelled !!)... 
> 
> The functor for ConcreteBidirectional says E.t = (V.t * V.t), 
> but I don't quite understand the type of B.G.E.label ... 

You're right, some type information is missing and there is no way to
instantiate the Dot functor with the current signature of
ConcreteBidirectional.

One easy patch (if you are compiling ocamlgraph from sources) is to add
the constraint

	... and type E.label = unit

to the signature of functor ConcreteBidirectional. I think we'll do that
in the next release of ocamlgraph (and similarly for other unlabeled
graph data structures provided in ocamlgraph).

Hope this helps,
-- 
Jean-Christophe

Re : [Caml-list] ocamlgraph ConcreteBidirectional and Dot

[Matthieu Wipliez]

Hi,

I have a question related to this: Is there a reason for the absence of a ConcreteBidirectionalLabeled graph in the API?

Thanks,
Matthieu


----- Message d'origine ----
> De : Jean-Christophe Filliâtre <Jean-Christophe.Filliatre@lri.fr>
> À : Pietro Abate <Pietro.Abate@pps.jussieu.fr>
> Cc : caml-list@yquem.inria.fr
> Envoyé le : Mardi, 7 Avril 2009, 9h35mn 22s
> Objet : Re: [Caml-list] ocamlgraph ConcreteBidirectional and Dot
> 
> Hi,
> 
> Sorry for the late answer...
> 
> > I've a small problem with ocamlgraph.
> > I want to parse a dot graph into a ConcreteBidirectional.
> > 
> > The problem is that the signature needed for Dot.Parse requires a function
> > edge, but I've no mean to specify a label (since it is unlabelled !!)... 
> > 
> > The functor for ConcreteBidirectional says E.t = (V.t * V.t), 
> > but I don't quite understand the type of B.G.E.label ... 
> 
> You're right, some type information is missing and there is no way to
> instantiate the Dot functor with the current signature of
> ConcreteBidirectional.
> 
> One easy patch (if you are compiling ocamlgraph from sources) is to add
> the constraint
> 
>     ... and type E.label = unit
> 
> to the signature of functor ConcreteBidirectional. I think we'll do that
> in the next release of ocamlgraph (and similarly for other unlabeled
> graph data structures provided in ocamlgraph).
> 
> Hope this helps,
> -- 
> Jean-Christophe
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: Re : [Caml-list] ocamlgraph ConcreteBidirectional and Dot

[Jean-Christophe Filliâtre]

> I have a question related to this: Is there a reason for the absence of a ConcreteBidirectionalLabeled graph in the API?

Simply an historical reason: the module ConcreteBidirectional is an
external contribution (by Ted Kremenek), which was only recently added
to Ocamlgraph.

Anybody can contribute to a ConcreteBidirectionalLabeled module and
we'll happily add it to Ocamlgraph.

-- 
Jean-Christophe