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
> one needs for every vertex the list of hyperedges in
> the vertex occurs. (Sometimes you need direct access
> only to a user-specified
> Then there is the issue of operations: removing a
> hyperedge, adding a hyperedge, removing a set of
> (in several variations (!)), adding a vertex. One
> often needs
> the possibility to undo these operations (using a
> of operation tokens). And then there
> is the quite important issue of "eagerness" and
> Really performing these operations, or only to
> them (for example removing a vertex: really removing
> it, or only
> to store that it was removed, and taking this into
> 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
> for many users, you need the possibility to overcome
> 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
> > 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
> What do you mean with "multilevel"?
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk