From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 583FBBBAF for ; Tue, 1 Jun 2010 18:45:51 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjkCAG3WBEyGnQCBkWdsb2JhbACReIw8FQEBAQEJCwoHEQMfwm+FFgQ X-IronPort-AV: E=Sophos;i="4.53,341,1272837600"; d="scan'208";a="51582685" Received: from shiva.jussieu.fr ([134.157.0.129]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 01 Jun 2010 18:45:51 +0200 Received: from hydrogene.pps.jussieu.fr (hydrogene.pps.jussieu.fr [134.157.168.1]) by shiva.jussieu.fr (8.14.4/jtpda-5.4) with ESMTP id o51Gjnk3077278 ; Tue, 1 Jun 2010 18:45:50 +0200 (CEST) X-Ids:164 Received: from hydrogene.pps.jussieu.fr (localhost.localdomain [127.0.0.1]) by hydrogene.pps.jussieu.fr (8.13.4/jtpda-5.4) with ESMTP id o51GjmZ7001547 ; Tue, 1 Jun 2010 18:45:48 +0200 Received: (from abate@localhost) by hydrogene.pps.jussieu.fr (8.13.4/8.13.2/Submit) id o51GjmHG001546; Tue, 1 Jun 2010 18:45:48 +0200 Date: Tue, 1 Jun 2010 18:45:48 +0200 From: Pietro Abate To: Eray Ozkural Cc: caml-list@inria.fr Subject: Re: [Caml-list] hypergraph partitioning algorithm ? Message-ID: <20100601164548.GA32202@uranium.pps.jussieu.fr> References: <20100601145634.GA24691@uranium.pps.jussieu.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-Operating-System: GNU/Linux User-Agent: Mutt/1.5.9i X-Miltered: at jchkmail.jussieu.fr with ID 4C05393D.005 by Joe's j-chkmail (http : // j-chkmail dot ensmp dot fr)! X-j-chkmail-Enveloppe: 4C05393D.005/134.157.168.1/hydrogene.pps.jussieu.fr/hydrogene.pps.jussieu.fr/ X-Spam: no; 0.00; partitioning:01 eray:01 ozkural:01 partitioning:01 bdds:01 ocaml:01 ocaml:01 afaik:01 wikipedia:01 wiki:01 beginner's:01 bug:01 eray:01 ozkural:01 bilkent:01 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 > 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