hypergraph partitioning algorithm ?

hypergraph partitioning algorithm ?

[Pietro Abate]

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

Re: [Caml-list] hypergraph partitioning algorithm ?

[Eray Ozkural]

Hi there,

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.

Cheers,

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

Re: [Caml-list] hypergraph partitioning algorithm ?

[Pietro Abate]

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

Re: [Caml-list] hypergraph partitioning algorithm ?

[Eray Ozkural]

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

Re: [Caml-list] hypergraph partitioning algorithm ?

[Hugo Ferreira]

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