From: Oliver Kullmann (O.Kullmann_at_[hidden])
Date: 2006-09-27 19:58:34
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
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
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
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"?