changing labels on ocamlgraph edges

changing labels on ocamlgraph edges

[Alexy Khrabrov]

It looks like the only way to change a label on an edge e -- say  
increment it -- is to read off the old one with G.E.label, then  
remember the src and dst with G.E.src/dst, then G.remove_edge_e g e,  
create a new edge e' with G.V.create src (label+1) dst, and  
G.add_adge_e g e'.  Is this supposed to be so complicated even for the  
imperative graphs?

Cheers,
Alexy

Re: [Caml-list] changing labels on ocamlgraph edges

[Julien SIGNOLES]

Hello,

> It looks like the only way to change a label on an edge e -- say  
> increment it -- is to read off the old one with G.E.label, then  
> remember the src and dst with G.E.src/dst, then G.remove_edge_e g e,  
> create a new edge e' with G.V.create src (label+1) dst, and  
> G.add_adge_e g e'.  Is this supposed to be so complicated even for the  
> imperative graphs?

No it is not :-). You just have to define yourself a mutable label. Here
is an example.

==========
open Graph

module G = 
  Imperative.Digraph.ConcreteLabeled
    (struct include String let equal = (=) let hash = Hashtbl.hash end)
    (struct 
       type t = int ref 
       let default = ref 0 
       let compare = Pervasives.compare
     end)

let g = G.create ()

let print_edge v1 v2 = 
  Format.printf "edge = %d@." !(G.E.label (G.find_edge g v1 v2))

let e = G.E.create "foo" (ref 1) "bar"
let () = 
  G.add_edge_e g e;
  print_edge "foo" "bar";
  G.E.label e := 2;
  print_edge "foo" "bar"
==========

Hope this helps,
Julien Signoles

Re : [Caml-list] changing labels on ocamlgraph edges

[Matthieu Wipliez]

> No it is not :-). You just have to define yourself a mutable label. Here
> is an example.
> 
> ==========
> open Graph
> 
> module G = 
>   Imperative.Digraph.ConcreteLabeled
>     (struct include String let equal = (=) let hash = Hashtbl.hash end)
>     (struct 
>        type t = int ref 
>        let default = ref 0 
>        let compare = Pervasives.compare
>      end)

I'm also using ocamlgraph with labels of type t = bool ref * int option
And I found that for add_edge to have the proper behavior, I need to replace the default add_edge with this one:
  let add_edge graph v1 v2 = add_edge_e graph (v1, (ref false, None), v2)

Otherwise all edges share the same reference (created in "default"), and changing the boolean for an edge changes it for all edges...

Cheers,
Matthieu

> 
> let g = G.create ()
> 
> let print_edge v1 v2 = 
>   Format.printf "edge = %d@." !(G.E.label (G.find_edge g v1 v2))
> 
> let e = G.E.create "foo" (ref 1) "bar"
> let () = 
>   G.add_edge_e g e;
>   print_edge "foo" "bar";
>   G.E.label e := 2;
>   print_edge "foo" "bar"
> ==========
> 
> Hope this helps,
> Julien Signoles
> 
> _______________________________________________
> 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] changing labels on ocamlgraph edges

[Jean-Christophe Filliatre]

Matthieu Wipliez wrote:
> I'm also using ocamlgraph with labels of type t = bool ref * int option
> And I found that for add_edge to have the proper behavior, I need to replace the default add_edge with this one:
>   let add_edge graph v1 v2 = add_edge_e graph (v1, (ref false, None), v2)
>
> Otherwise all edges share the same reference (created in "default"), and changing the boolean for an edge changes it for all edges...
>   

May be we should document add_edge more carefully, so that it is clear 
that it makes use of the default edge label, and that, consequently, 
this label is shared among all edges created with add_edge

Indeed you have to use add_edge_e instead to avoid sharing

--
Jean-Christophe

Re: Re : [Caml-list] changing labels on ocamlgraph edges

[Alexy Khrabrov]

On Mar 12, 2009, at 10:38 AM, Jean-Christophe Filliatre wrote:
> May be we should document add_edge more carefully, so that it is  
> clear that it makes use of the default edge label, and that,  
> consequently, this label is shared among all edges created with  
> add_edge
>
> Indeed you have to use add_edge_e instead to avoid sharing

And another clarification: if you add_edge_e, the edge e is sA->vB- 
 >dC, and exactly such an edge exists already, nothing happens.   That  
is, if you just call add_edge v1 v2 repeatedly, only one edge is ever  
created.  However, if you add an edge with the same src, dst, but a  
different label, which can only be done with G.E.create, and add it  
with add_edge_e, then it's added and you have several edges.

Another aspect is that if you add an edge and any vertex in it is not  
yet in the graph, it's added into the graph as well.

I sense that several important and intuitive operations are missing,  
namely

G.add_edge_lavel v1 v2 label

G.E.create would look better if the label were the trailing argument,  
or leading optional one with the type-based default value

G.get_edge_label and G.set_edge_label are needed just like those for  
Mark'ing vertices -- that would simplify labeling the edges and make  
it more natural.

While I was experimenting with changing the edge labels by removing  
old edges and adding new ones with just a different label, I found  
that performance is OK -- a graph with 35K vertices and 2,5 million  
edges, of those 80K unique (src,dst), is created in 8 minutes with  
add_edge v1 v2 and 9.5 minutes with remove/add where the label is a  
count of total edges between the vertices.  Then it's stored as a  
graph with integer edges, not references, and marshals into almost the  
same size as the default-labeled graph.  So it would be nicer and  
easier to allow such labels instead of making the user to explicitly  
mark references.

Finally, it's very annoying to see plural of vertex as also "vertex"  
-- in G.nb_vertex or iter_vertex; it's "vertices"! :)  Also nb_ is a  
non-standard abbreviation for "number of", perhaps better names are  
num_vertices and num_edges?

Cheers,
Alexy

Re : Re : [Caml-list] changing labels on ocamlgraph edges

[Matthieu Wipliez]

> Finally, it's very annoying to see plural of vertex as also "vertex" -- in 
> G.nb_vertex or iter_vertex; it's "vertices"! :)  Also nb_ is a non-standard 
> abbreviation for "number of", perhaps better names are num_vertices and 
> num_edges?

Good point, for instance I'm using SystemC FIFOs and they have nb_read/nb_write for non-blocking read and write, and num_available/num_written for the number of tokens available and written.

Nevertheless, these are minor issues, ocamlgraph is an excellent piece of software altogether! (and a good example of why functors can be a good thing ^^).

Cheers,
Matthieu

PS : is there a list dedicated to ocamlgraph? This might be a better place for this kind of discussion :-)