From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=2.9 required=5.0 tests=AWL,DNS_FROM_RFC_POST, RCVD_IN_SORBS_WEB,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 8DA59BBAF for ; Fri, 13 Mar 2009 01:10:33 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApUCAK9BuUlA6ba4k2dsb2JhbACUdT8BAQEBCQkKCREDqmCBBo8jAQMBA4N7BoMs X-IronPort-AV: E=Sophos;i="4.38,353,1233529200"; d="scan'208";a="36486267" Received: from nf-out-0910.google.com ([64.233.182.184]) by mail4-smtp-sop.national.inria.fr with ESMTP; 13 Mar 2009 01:10:32 +0100 Received: by nf-out-0910.google.com with SMTP id b21so749634nfd.7 for ; Thu, 12 Mar 2009 17:10:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:cc:message-id:from:to :in-reply-to:content-type:content-transfer-encoding:mime-version :subject:date:references:x-mailer; bh=bWrzIT6jsGeaLj+pqRkszHCR5Sb+QRq6UESVKk2FzpI=; b=KL6UZSsM5TVnR1lmcY5IxisT9wbQk3Y+vvUq0SKeM6iJYK7g3nfC4Bf+4LjKC41PE6 NR0pJeutSTTAJvrysh0WAmBfLhLrTSsFwt1Ezdkr7szLvyzyt3EgWb7IeW9RwK3/zNxe aiM8s28bKz0On9kioNfvAk/yikPtgpa/BbBcw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=cc:message-id:from:to:in-reply-to:content-type :content-transfer-encoding:mime-version:subject:date:references :x-mailer; b=WIblF7kvcc+OXYdncrK7XhURfMQvUhx4lBQNbl7FLFHv34nxMK29daJcb1cFe9srT4 cWLhzhcZtWyxJ23FDmSvaD6vf1ka9HAOPaUZoVq/B8awaLh8spWkZnPsGaLtD9R0lOSJ DXikwJsT/q+4ZhWS50axBiRRThtG3ZaZ1MJdo= Received: by 10.216.50.76 with SMTP id y54mr375879web.70.1236903031780; Thu, 12 Mar 2009 17:10:31 -0700 (PDT) Received: from ?192.168.1.101? ([64.30.3.122]) by mx.google.com with ESMTPS id g9sm2424680gvc.28.2009.03.12.17.10.28 (version=TLSv1/SSLv3 cipher=RC4-MD5); Thu, 12 Mar 2009 17:10:30 -0700 (PDT) Cc: Matthieu Wipliez , OCaml Message-Id: From: Alexy Khrabrov To: Jean-Christophe Filliatre In-Reply-To: <49B91E68.5020508@lri.fr> Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v930.3) Subject: Re: Re : [Caml-list] changing labels on ocamlgraph edges Date: Thu, 12 Mar 2009 20:10:19 -0400 References: <5F21734C-C88E-4401-8EB4-811681A42E67@gmail.com> <1236844549.22473.184.camel@localhost> <366870.61081.qm@web27007.mail.ukl.yahoo.com> <49B91E68.5020508@lri.fr> X-Mailer: Apple Mail (2.930.3) X-Spam: no; 0.00; filliatre:01 type-based:01 plural:01 iter:01 non-standard:01 abbreviation:01 cheers:01 wrote:01 graph:01 graph:01 integer:01 caml-list:01 edges:01 edges:01 explicitly:02 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