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
hypergraph partitioning algorithm ?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2010-06-01 (18:52)
From: Hugo Ferreira <hmf@i...>
Subject: Re: [Caml-list] hypergraph partitioning algorithm ?

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

Hugo F.


> thanks !
> pietro
>> On Tue, Jun 1, 2010 at 5:56 PM, Pietro Abate
>> <> 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
>>> --
>>> ----
>>> _______________________________________________
>>> Caml-list mailing list. Subscription management:
>>> Archives:
>>> Beginner's list:
>>> Bug reports:
>> -- 
>> Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara