Re: [boost] interest in hyper graph library

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