From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 7E84ABBAF for ; Tue, 1 Jun 2010 20:52:49 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ag4CAGP0BEzVhjEYkGdsb2JhbACReoxRAQEBAQkJDAcRAx/CbYUWBA X-IronPort-AV: E=Sophos;i="4.53,341,1272837600"; d="scan'208";a="60438912" Received: from ihsmtp02voda.lis.interhost.com (HELO ihsmtp02cons.lis.interhost.com) ([213.134.49.24]) by mail1-smtp-roc.national.inria.fr with ESMTP; 01 Jun 2010 20:52:48 +0200 Received: from [192.168.1.64] ([95.136.106.136]) by ihsmtp02cons.lis.interhost.com with Microsoft SMTPSVC(6.0.3790.3959); Tue, 1 Jun 2010 19:52:48 +0100 Message-ID: <4C0556FB.70907@inescporto.pt> Date: Tue, 01 Jun 2010 19:52:43 +0100 From: Hugo Ferreira User-Agent: Thunderbird 2.0.0.24 (X11/20100317) MIME-Version: 1.0 To: Pietro Abate Cc: caml-list@inria.fr Subject: Re: [Caml-list] hypergraph partitioning algorithm ? References: <20100601145634.GA24691@uranium.pps.jussieu.fr> <20100601164548.GA32202@uranium.pps.jussieu.fr> In-Reply-To: <20100601164548.GA32202@uranium.pps.jussieu.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 01 Jun 2010 18:52:48.0309 (UTC) FILETIME=[A1132650:01CB01BB] X-Spam: no; 0.00; partitioning:01 eray:01 ozkural:01 partitioning:01 bdds:01 bdds:01 jeannet:01 fabio:01 pop-art:01 inrialpes:01 ocaml:01 ocaml:01 afaik:01 wikipedia:01 wiki:01 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 >> 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 >