From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id B47767F30A for ; Sun, 10 Mar 2013 16:31:43 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of j.schauer@email.de) identity=pra; client-ip=212.227.17.12; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="j.schauer@email.de"; x-sender="j.schauer@email.de"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of j.schauer@email.de) identity=mailfrom; client-ip=212.227.17.12; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="j.schauer@email.de"; x-sender="j.schauer@email.de"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mout.web.de) identity=helo; client-ip=212.227.17.12; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="j.schauer@email.de"; x-sender="postmaster@mout.web.de"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqIHAO+lPFHU4xEMkGdsb2JhbABCFogCtw2FFwIBgUoWDgEBAQEJCRQUKIJQSws1AiYCSUSHfAipWJFngSOMKndKgjSBEwOWVIEfhEmOGYFy X-IPAS-Result: AqIHAO+lPFHU4xEMkGdsb2JhbABCFogCtw2FFwIBgUoWDgEBAQEJCRQUKIJQSws1AiYCSUSHfAipWJFngSOMKndKgjSBEwOWVIEfhEmOGYFy X-IronPort-AV: E=Sophos;i="4.84,819,1355094000"; d="scan'208";a="6319186" Received: from mout.web.de ([212.227.17.12]) by mail2-smtp-roc.national.inria.fr with ESMTP; 10 Mar 2013 16:31:43 +0100 Received: from localhost ([80.187.110.115]) by smtp.web.de (mrweb003) with ESMTPSA (Nemesis) id 0LqlRS-1UjwEc0WXK-00ddEN; Sun, 10 Mar 2013 16:31:40 +0100 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable From: Johannes Schauer Cc: Sylvain.Conchon@lri.fr, Jean-Christophe.Filliatre@lri.fr, Julien.Signoles@lri.fr User-Agent: alot/0.3.4 To: caml-list@inria.fr Message-ID: <20130310153132.5538.26027@hoothoot> Date: Sun, 10 Mar 2013 16:31:32 +0100 X-Provags-ID: V02:K0:rs7fYgtcgtPujUosnApYaIvQr5YHpP9USDi+LS6hUMM 5BvZQh/0mORq5c4el2Iokj97DbVpm5u9mj8/65Gf74SpgZCGyN lAI4qQrYwU0hwOLyBRr1l0iIiSGfq3x/iwlbvKDY3T+d6MoLJU pm1HJPNaAeAC3gsOMMQZ1+HDRB1dGbkTGwgXYaTRpgrQWGYUin HEn6/adRHkH0rnhsPwQcg== Subject: [Caml-list] [ocamlgraph] Johnson's algo, C-bindings, GraphML reader, edge dominators Hi, it appears that ocamlgraph doesnt have a mailinglist and while I could've j= ust bothered the three developers is person I thought I might get more input by writing to this list. :) Johnson's Algorithm ------------------- I fixed an implementation by Pietro Abate of Johnson's algorithm for enumerating elementary circuits in a directed graph. He first demonstrated = his solution here: http://mancoosi.org/~abate/finding-all-elementary-circuits-directed-graph The fixed version can be found in this git repository: https://github.com/josch/cycles_johnson_abate I tested that implementation against several other implementations for cycle enumeration - An extended version of Johnson's algo by K.A. Hawick and H.A. James in D https://github.com/josch/cycles_hawick_james - Johnson's algo by F. Meyer in Java https://github.com/josch/cycles_johnson_meyer - Johnson's algo as part of networkx in Python https://github.com/josch/cycles_johnson_networkx - My own implementation of Tarjan's algorithm in Python https://github.com/josch/cycles_tarjan The whole testing framework sits at https://github.com/josch/cycle_test We use the implementation of Johnson's algorithm in Ocaml by P. Abate and myself with the additional feature to (optionally) only enumerate cycles up= to a given length. The (still generic) version of the Ocaml implementation can= be found at: https://gitorious.org/debian-bootstrap/bootstrap/blobs/9922b429/graphUtils.= ml#line128 So maybe it would be useful to integrate this into ocamlgraph? Using Ocamlgraph from C ----------------------- My ocaml code heavily uses ocamlgraph. I was asked to write a Python binding for my code but I thought that it would make more sense to allow my code to= be used from C because every other language has some way to make use of C libraries. For example it would then be straight forward to use Python ctyp= es for a Python binding. So is there some existing code that allows ocamlgraph based code to be used from C where I could get some inspiration from how to best do the implementation and build system? GraphML reader -------------- Pietro Abate recently contributed a GraphML writer to ocamlgraph. I'm tempt= ed to write a GraphML reader but should I accomplish to do this, it would make most sense if the result could also be integrated into ocamlgraph. GraphML = is XML based, so what XML reader library would the ocamlgraph authors prefer I= use for that task? Edge dominators --------------- The current implementation of dominators in ocamlgraph only computes vertex dominators. I also need edge dominators. When I implemented to also calcula= te those, how would the ocamlgraph maintainers like my contribution? Just an e= mail to all three developers listed on the website? I'm a bit puzzled because I'm not used to sending code to individuals instead of mailing lists or bug trackers and also because the link to on the front page Julien Signoles giv= es a 404. Thanks! cheers, josch