general.hpp File Reference

Plans for concepts regarding hypergraphs. More...

Go to the source code of this file.

Detailed Description

Plans for concepts regarding hypergraphs.

Update namespaces.
Collect possible requirements on a hypergraph concept
  • We must connect to the similar (and more refined) considerations for clause-sets.
  • Operation * of crossing out vertices:
    1. A framework for "doing/undoing" is needed.
    2. As usual we have the "eager" and the "lazy" approaches.
    3. For the eager approach the Boehm datastructure seems appropriate (as used in the original OKsolver).
    4. The information which hyperedges have not been touched is also useful (for example for autarky-purposes).
  • Sorting of hyperedges:
    1. Often smallest and largest hyperedges are sought.
    2. Two possibilities: Only for heuristical purposes (thus an "approximation" is enough), or for decision purposes (thus we need the precise information).
    3. For heuristical purposes the simplest solution is to sort the hyperedges according to size just once at the beginning. Likely this should (nearly) always happen.
    4. The most powerful solution is to keep the hyperedges sorted throughout (according to size). Datastructures like std::set (balanced trees) are then appropriate.
    5. For decision purposes (for example in a parameterised setting) the largest hyperedge may be needed, and this can be realised by a heap datastructure.
  • Sizes of hyperedges:
    1. The information on the largest and smallest hyperedge should be offered (nearly) always.
    2. And always for an hyperedge we should be able to ask for its size. Most often stored and updated.
    3. For every size the number of hyperedges of this size is also often useful.
  • Sorting of vertices : dual to sorting of hyperedges.
  • Vertex degrees:
    1. Smallest and largest vertex degrees.
    2. For every vertex its degree.
    3. For every possible degree the number of vertices.
    Can we exploit here duality ?!?
Concept design in general
  • Writing the basic concepts for hypergraphs, similar to the concepts for graphs from the Boost graph library (sequences of vertices and hyperedges, where hyperedges are sequences of vertices).
  • The direct access from vertices to incident edges could be "outsourced" to the concept of an associated bipartite graph (the vertex-hyperedge bipartite graph; associated, so that update operations are reflected), but it seems better to only "embed" this bipartite graph into the hypergraph data structure, as the bipartite vertex-edge graph is embedded into the boost graph concept via the refinement of an "incidence graph": This seems to model better the main nature of that bipartite graph as a data structure; and also in this way generalisations like access only to hyperedges where the vertex is the "first" or the "last" vertex are perhaps modelled more easily (in this way we then can model directed graphs, and also methods like "watched literals" (such bipartite graphs are actually vertex-edge graphs)!).
  • However, it should be the case that such "incidence hypergraphs" directly yield models of bipartite graphs via regarding either the vertices or the hyperedges as "left part".
  • Clarify the relations to module Graphs (see Graphs/plans/Graphs.hpp).
  • Clarify the relation to Concepts/plans/BipartiteGraphs.hpp.
  • Clause-sets are refinements of hypergraphs, where also application of partial assignments may be supported (perhaps also resolution etc. ?).
  • See QuantumPhysics/plans/OrthogonalTriples.hpp for some examples.
Move the related files from OKlib/Concepts here : DONE
The simplest form of hypergraphs
  • The simplest concept of a hypergraph represents a hypergraph just as a range of ranges.
  • A first example is Hypergraphs::Generators::Hindman_k2 in OKlib/Combinatorics/Hypergraphs/Generators/Hindman.hpp; see also Combinatorics/Hypergraphs/Generators/plans/Hindman.hpp.
  • A second, slightly extended example is Hypergraphs::Generators::GreenTao in OKlib/Combinatorics/Hypergraphs/Generators/GreenTao.hpp; see also Combinatorics/Hypergraphs/Generators/plans/GreenTao.hpp.
  • Perhaps here already one has some hierarchy:
    1. Simplest just a range of ranges, with no further requirements.
    2. The set of vertices is here not directly accessible (only through the union of all hyperedges).
    3. Next a simple concept providing some simple wrapper-class, providing for example traits like "hyperedge_type".
    4. As a next level two explicit statistics-functions nver and nhyp might be added (where nhyp was as the size of the hyperedge-range already accessible before, but nver is new).
    5. Does one need two size-types, one for the vertices, one for the hyperedges? Seems necessary.
    6. One could also have a concept inbetween: A hypergraph just provides some type- and statistics-members plus access to the range of ranges. Hypergraphs::Generators::Hindman_k2 is an example. This is perhaps simplest, just a wrapper around the range of ranges, and not itself making the hyperedges available.
    7. What to do with the set of vertices? A slightly extended concept could just offer a range which contains the vertices.
    8. As in Hypergraphs::Generators::GreenTao.
    9. Shall it always be possible that nver() and nhyp() can be called without computing the hypergraph? Perhaps.

Definition in file general.hpp.