From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 0EAEFBBAF for ; Tue, 1 Jun 2010 19:06:58 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkQBANfaBEzRVaE2mGdsb2JhbACRcYw0CBUBAQEBAQgJDAcRIrJAggKFQi6ITwEBAwWFEQSDQw X-IronPort-AV: E=Sophos;i="4.53,341,1272837600"; d="scan'208";a="52234766" Received: from mail-fx0-f54.google.com ([209.85.161.54]) by mail2-smtp-roc.national.inria.fr with ESMTP; 01 Jun 2010 19:06:57 +0200 Received: by fxm5 with SMTP id 5so3248053fxm.27 for ; Tue, 01 Jun 2010 10:06:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:references:message-id:from:to :in-reply-to:content-type:content-transfer-encoding:mime-version :subject:date:cc:x-mailer; bh=F6oQMr5i9T2Ayg3kyijpoH5/2U5ffNieGq6jHwzWpUE=; b=Ats73H6VZvQ/otbcAoo9E+xFb9I6de62DRFgvRUmlDCoKpUIufCTcvt45jfZHVo8jO UT8HSf2aV3Z7nmx6b11km927/dRHXkciwwgAPqydiWq9bQOHwiKjn8y3YZFyWOl3Z/3r PBudE2RzIoNUu14RSP3jMgJNsM6YmAlCbSO4c= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=references:message-id:from:to:in-reply-to:content-type :content-transfer-encoding:mime-version:subject:date:cc:x-mailer; b=pAjbzjyKwh43+MIpajqYIt8G9yBR8Z16vh9WVk5x3uSnWYwp/IxB3zQWhXC4l12SHM fk5Gf3GsCOK3I2fper/WkJ4SVzTFtF6BrUbWIQ1meAtkzRyb75uZJPptdCs95JIvzlRQ uWIJUDz1nhq3Od56kqU7C9xo/YU4UxPZc+suk= Received: by 10.204.46.196 with SMTP id k4mr868286bkf.72.1275412017536; Tue, 01 Jun 2010 10:06:57 -0700 (PDT) Received: from [188.56.10.230] ([188.56.10.230]) by mx.google.com with ESMTPS id v2sm3952940bkz.1.2010.06.01.10.06.52 (version=TLSv1/SSLv3 cipher=RC4-MD5); Tue, 01 Jun 2010 10:06:56 -0700 (PDT) References: <20100601145634.GA24691@uranium.pps.jussieu.fr> <20100601164548.GA32202@uranium.pps.jussieu.fr> Message-Id: From: Eray Ozkural To: Pietro Abate In-Reply-To: <20100601164548.GA32202@uranium.pps.jussieu.fr> Content-Type: text/plain; charset=us-ascii; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (iPhone Mail 7E18) Subject: Re: [Caml-list] hypergraph partitioning algorithm ? Date: Tue, 1 Jun 2010 20:05:33 +0300 Cc: "caml-list@inria.fr" X-Mailer: iPhone Mail (7E18) X-Spam: no; 0.00; eray:01 ozkural:01 partitioning:01 partitioning:01 cheers:01 eray:01 ozkural:01 bdds:01 ocaml:01 ocaml:01 afaik:01 wikipedia:01 wiki:01 beginner's:01 bug:01 Hi there, Writing from mobile sorry for top posting. Partitioning a binary decision diagram sounds right. What I meant was an efficient implementation isn't easy and FM is only part of the code. You'll be better off calling a multi level hypergraph partitioning package like patoh or hmetis. It can take several months to write one from scratch and make it run fast. Cheers, -- Eray Ozkural http://myspace.com/arizanesil On Jun 1, 2010, at 7:45 PM, 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 ... > > 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