Re: [Caml-list] hypergraph partitioning algorithm ?

From: Pietro Abate <Pietro.Abate@pps.jussieu.fr>
To: Eray Ozkural <examachine@gmail.com>
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] hypergraph partitioning algorithm ?
Date: Tue, 1 Jun 2010 18:45:48 +0200	[thread overview]
Message-ID: <20100601164548.GA32202@uranium.pps.jussieu.fr> (raw)
In-Reply-To: <AANLkTinLvH_StpmesiODo2iYaMSKpZxQkvdqhVuJHEAU@mail.gmail.com>

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 ...

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

-- 
----
http://en.wikipedia.org/wiki/Posting_style