Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
changing labels on ocamlgraph edges
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2009-03-13 (00:10)
From: Alexy Khrabrov <deliverable@g...>
Subject: Re: Re : [Caml-list] changing labels on ocamlgraph edges
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,  

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?