Pietro,

Pietro Abate wrote:
> Hi. Deliberately going of topic...
> 
> On Tue, Jun 01, 2010 at 07:21:07PM +0300, Eray Ozkural wrote:
>> Those are not very often implemented, and no there is none that I can
>> think of, at least freely so. However, I was actually planning on
>> implementing one, adapting some of our efficient algorithms.
> 
> I'm far to be an expert on the field and I'd appreciate a bit of
> guidance...
> 
> I was under the impression the hypergraph partitioning is the leading
> strategy to reduce the size of a BDD. When dealing with real size
> problems, finding a suitable order to work with BDDs is essential. Last
> week I've implemented an heuristic (FORCE) to derive a static ordering
> from my graph, but I then discovered that the bdd package I'm using
> (buddy bdd) deals pretty badly with static ordering taking a cubic time
> on the # of variables to set up a bdd with this order. 
> 
> The other option I have is to partition the graph in clusters and then
> use the buddy dynamic ordering that "apparently' works well ... To cut a
> long story short, this is what led me to hypergraph partitioning. Now
> you are saying that they are not often implemented and I'm wondering if
> I'm completely off track here and there are other heuristics to compute
> a suitable block order and therefore reduce the size of a bdd ... MINCE
> for example uses hypergraph partitioning in order to find a suitable
> variable ordering ...
> 

I may not have understood your issue correctly but have you considered
using the CUDD BDD package [1]? It provides a means to reorder the
variables and thereby reduce the BDD size. If I recall correctly you
could do this manually or automatically.

In order to use the library you can use the MlCuDDIDL library [2]. Last
I used it the library had been updated and it seemed to work nicely
with large BDDs (nearly 2 Gbytes). (At the time the author Bertrand
Jeannet took the time to look into the issues and made some
changes).

HTHs,
Hugo F.

[1] http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html
[2] http://pop-art.inrialpes.fr/~bjeannet/mlxxxidl-forge/

> thanks !
> 
> pietro
> 
>> On Tue, Jun 1, 2010 at 5:56 PM, Pietro Abate
>> <Pietro.Abate@pps.jussieu.fr> wrote:
>>> Hello,
>>>
>>> Do you know of any implementation of the Fiduccia-Mattheyses algorithm
>>> or other hypergraph partitioning / clustering algorithms in ocaml ?
>>>
>>> There are two c++ libraries (GTL and scotch) that implement these
>>> algorithms, but no binding to ocaml afaik...
>>>
>>> thanks !
>>> p
>>>
>>> --
>>> ----
>>> http://en.wikipedia.org/wiki/Posting_style
>>>
>>> _______________________________________________
>>> 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
>>>
>>
>>
>> -- 
>> Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
>> http://groups.yahoo.com/group/ai-philosophy
>> http://myspace.com/arizanesil http://myspace.com/malfunct
>