Plans regarding the basic notions for hypergraphs.
More...
Go to the source code of this file.
Detailed Description
Plans regarding the basic notions for hypergraphs.
 Todo:
 Lists instead of sets

Additionally to "hypergraphs" and "general hypergraphs" we introduce "ordered hypergraphs" and "ordered general hypergraphs":

Computationally these notions are considered to be more fundamental.

An ordered hypergraphs is a pair [V,E], where V and E are lists without repetition, such that [setify(V),setify(E)] is a hypergraph.

An ordered general hypergraph is a triple [V,E,f], where V, E are lists without repetition, such that [setify(V),setify(E),f] is a general hypergraph.

Multiversions:

We also should have "multihypergraphs", triples [V,E,c], s.t. [V,E] is a hypergraph, and c: E > NN.

And "ordered multihypergraphs, [V,E,c] s.t. [setify(V),setify(E),c] is a multihypergraph, and [V,E] is an ordered hypergraph.
 Todo:
 Naming conventions

"hg" for hypergraph, "ghg" for general hypergraph, and "ohg", "oghg" for the ordered versions.

"muhg" for multihypergraph, and "omuhg" for ordered multihypergraph.

Conversions then as "hg2ghg", "ohg2hg" etc.

Connections to graphs (see ComputerAlgebra/Graphs/Lisp/plans/general.hpp):

g, gl <= hg

mug, mugl <= muhg

gg <= ghg

og, ogl <= ohg

omug, omugl <= omuhg

ogg <= oghg
 Todo:
 Polar hypergraphs

While a "square hypergraph" is a hypergraph [V,E] with V = E, we introduce the notion of a "bipolar hypergraph" ("bphg") as a pair [V,f], s.t. [V,V,f] is a general hypergraph.

A "polar hypergraph" is a bipolar hypergraph [V,f] s.t. for all y in f(x) we also have x in f(y).

Specialising correspondences [R,A,B] to "relationals" [R,A], considering only symmetric relations, representing the relation R <= A^2 by a function from A to P(A), and changing the order, we have exactly the polar hypergraphs; dropping "symmetric", we get the bipolar hypergraphs.

Another view is that the bipolar hypergraphs [V,f] correspond exactly to the digraphs with vertex set V, where f(v) is the set of outneighbours, while polar hypergraphs correspond exactly to the graphs with vertex set V.

The notion of a "polar hypergraph" comes from incidence structures:

Given an incidence structure [I,A,B], a "polarity" p is a bijection p: A > B such that I(x,p(y)) = I(y,p(x)) for all x, y in A.

Given such a polarity, we obtain a "polar indicence structure" as a pair [I',A] with I': A^2 > {0,1} through I'(x,y) := I(x,p(y)) (where I' is symmetric).

And while incidence structures correspond to general hypergraphs, polar incidence structures correspond to polar hypergraphs.

See ComputerAlgebra/IncidenceStructures/Lisp/plans/general.hpp.

Relations with graphs:

We have natural translations gl2phg, dgl2bphg and phg2gl, bphg2dgl.

Additionally we also have bphg2g, which is the same as g2dg after bphg2dgl.

For the direction (d)gl2(b)phg, it seems most natural to implement the function f through hashmaps.

Additionally we have stdgl2phg and stddgl2bphg, which use arrays.
Definition in file Basics.hpp.