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