Re: [boost] interest in hyper graph library
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
--- Oliver Kullmann <O.Kullmann@swansea.ac.uk> 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
I'm working with something as follows. A graph consists of a set of vertices and a set of edges. vertices are connected to edges through a seperate datastructure. This allows data to be attached to vertices, edges, and the connection between a vertex and edge. As for as multilevel hypergraphs go. It essentially allows the graph to be partitioned into multiple smaller graphs. ie: a 100,000 node graph is partitioned into a graph with 1000 nodes, then the 1000 node graph is partitioned into a 10 node graph. The graph can be walked at each level, and you can move to a higher or lower level. This is somewhat like subgraph in the current BGL. I'll try to get a skeleton prototype, and a short design document put together so I can get some feedback. __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
participants (2)
-
Brian Makin -
Oliver Kullmann