[Caml-list] [ocamlgraph] Johnson's algo, C-bindings, GraphML reader, edge dominators

[Caml-list] [ocamlgraph] Johnson's algo, C-bindings, GraphML reader, edge dominators

[Johannes Schauer]

Hi,

it appears that ocamlgraph doesnt have a mailinglist and while I could've just
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 ctypes
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 tempted
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 calculate
those, how would the ocamlgraph maintainers like my contribution? Just an email
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 gives a
404.

Thanks!

cheers, josch