Re: [boost] interest in hyper graph library

From: Brian Makin (merimus_at_[hidden])
Date: 2006-09-27 21:58:22

--- Oliver Kullmann <O.Kullmann_at_[hidden]> wrote:

> On Wed, Sep 20, 2006 at 07:00:38AM -0700, Brian
> Makin wrote:
> > 
> > I am not terribly familiar with the SAT problem
> (on a
> > cursory basis only).
> > 
> > Do you have a reference or example which would
> > demonstrate the requirements which would be placed
> on a
> > hgraph library?
> >
> 
> Satisfiability (SAT) and constraint satisfaction
> (CSP) are very fast
> moving targets; but regarding the data structure
> typically
> one needs for every vertex the list of hyperedges in
> which
> the vertex occurs. (Sometimes you need direct access
> only to a user-specified
> subset.)
> 
> Then there is the issue of operations: removing a
> hyperedge, adding a hyperedge, removing a set of
> vertices
> (in several variations (!)), adding a vertex. One
> often needs
> the possibility to undo these operations (using a
> stack
> of operation tokens). And then there
> is the quite important issue of "eagerness" and
> "laziness":
> Really performing these operations, or only to
> "register"
> them (for example removing a vertex: really removing
> it, or only
> to store that it was removed, and taking this into
> account
> when performing operations).
> 
> I think hypergraphs are more linked to
> non-polynomial time
> algorithms than graphs, and then one needs a (great)
> variety of
> datastructures, they must be extendible, and, very
> important
> for many users, you need the possibility to overcome
> the
> public interface! 
>  
> Another issue is the handling of hyperedges of
> different lengths:
> Empty? Unit (loop)?
> Very important in the SAT area are length-2
> hyperedges (edges).
> Allowing for multiple hyperedges? With names?
> Attaching information?
> As a data structure a "general hypergraph" is more
> natural, but often
> in applications you need a "hypergraph" (no
> duplicated hyperedges);
> sometimes even it should be simple (no subsumed
> hyperedges). This subsumption
> elimination is a non-trivial process.
>  
> > My current app the graph is representing netlists
> of
> > circuits.
> > 
> 
> this is quite close to a SAT application; libraries
> have big problems
> here, because a SAT solver operating one such a
> hypergraph, used for
> its problem representation, needs to access and
> augment the data structure
> in many ways (you need "online" access, and "on the
> fly", and can't afford
> import and export).
> 
> > Actually I intend to create a multilevel
> hypergraph. 
> 
> What do you mean with "multilevel"?
> 
> Oliver
> 
> 
> 

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com