Re: [Caml-list] hypergraph partitioning algorithm ?

[Eray Ozkural <examachine@gmail.com>]

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 <Pietro.Abate@pps.jussieu.fr>  
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
>> <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