Hypergraph generators#

This module implements generators of hypergraphs. All hypergraphs can be built through the hypergraphs object. For instance, to build a complete 3-uniform hypergraph on 5 points, one can do:

sage: H = hypergraphs.CompleteUniform(5, 3)

>>> from sage.all import *
>>> H = hypergraphs.CompleteUniform(Integer(5), Integer(3))

To enumerate hypergraphs with certain properties up to isomorphism, one can use method nauty(), which calls Brendan McKay’s Nauty (http://cs.anu.edu.au/~bdm/nauty/):

sage: list(hypergraphs.nauty(2, 2, connected=True))
[((0,), (0, 1))]

>>> from sage.all import *
>>> list(hypergraphs.nauty(Integer(2), Integer(2), connected=True))
[((0,), (0, 1))]

This module contains the following hypergraph generators

nauty()

Enumerate hypergraphs up to isomorphism using Nauty.

CompleteUniform()

Return the complete \(k\)-uniform hypergraph on \(n\) points.

UniformRandomUniform()

Return a uniformly sampled \(k\)-uniform hypergraph on \(n\) points with \(m\) hyperedges.

Functions and methods#

class sage.graphs.hypergraph_generators.HypergraphGenerators[source]#

Bases: object

A class consisting of constructors for common hypergraphs.

BinomialRandomUniform(n, k, p)[source]#

Return a random \(k\)-uniform hypergraph on \(n\) points, in which each edge is inserted independently with probability \(p\).

  • n – number of nodes of the graph

  • k – uniformity

  • p – probability of an edge

EXAMPLES:

sage: hypergraphs.BinomialRandomUniform(50, 3, 1).num_blocks()              # needs numpy
19600
sage: hypergraphs.BinomialRandomUniform(50, 3, 0).num_blocks()              # needs numpy
0

>>> from sage.all import *
>>> hypergraphs.BinomialRandomUniform(Integer(50), Integer(3), Integer(1)).num_blocks()              # needs numpy
19600
>>> hypergraphs.BinomialRandomUniform(Integer(50), Integer(3), Integer(0)).num_blocks()              # needs numpy
0
CompleteUniform(n, k)[source]#

Return the complete \(k\)-uniform hypergraph on \(n\) points.

INPUT:

  • k, n – nonnegative integers with \(k\leq n\)

EXAMPLES:

sage: h = hypergraphs.CompleteUniform(5, 2); h
Incidence structure with 5 points and 10 blocks
sage: len(h.packing())                                                      # needs sage.numerical.mip
2

>>> from sage.all import *
>>> h = hypergraphs.CompleteUniform(Integer(5), Integer(2)); h
Incidence structure with 5 points and 10 blocks
>>> len(h.packing())                                                      # needs sage.numerical.mip
2
UniformRandomUniform(n, k, m)[source]#

Return a uniformly sampled \(k\)-uniform hypergraph on \(n\) points with \(m\) hyperedges.

  • n – number of nodes of the graph

  • k – uniformity

  • m – number of edges

EXAMPLES:

sage: H = hypergraphs.UniformRandomUniform(52, 3, 17)
sage: H
Incidence structure with 52 points and 17 blocks
sage: H.is_connected()
False

>>> from sage.all import *
>>> H = hypergraphs.UniformRandomUniform(Integer(52), Integer(3), Integer(17))
>>> H
Incidence structure with 52 points and 17 blocks
>>> H.is_connected()
False
nauty(number_of_sets, number_of_vertices, multiple_sets=False, vertex_min_degree=None, vertex_max_degree=None, set_max_size=None, set_min_size=None, regular=False, uniform=False, max_intersection=None, connected=False, debug=False, options='')[source]#

Enumerate hypergraphs up to isomorphism using Nauty.

INPUT:

  • number_of_sets – integer, at most 64 minus number_of_vertices

  • number_of_vertices – integer, at most 30

  • multiple_sets – boolean (default: False); whether to allow several sets of the hypergraph to be equal.

  • vertex_min_degree, vertex_max_degree – integers (default: None); define the maximum and minimum degree of an element from the ground set (i.e. the number of sets which contain it).

  • set_min_size, set_max_size – integers (default: None); define the maximum and minimum size of a set.

  • regular – integers (default: False); if set to an integer value \(k\), requires the hypergraphs to be \(k\)-regular. It is actually a shortcut for the corresponding min/max values.

  • uniform – integers (default: False); if set to an integer value \(k\), requires the hypergraphs to be \(k\)-uniform. It is actually a shortcut for the corresponding min/max values.

  • max_intersection – integers (default: None); constraints the maximum cardinality of the intersection of two sets from the hypergraphs.

  • connected – boolean (default: False); whether to require the hypergraphs to be connected.

  • debug – boolean (default: False); if True the first line of genbgL’s output to standard error is captured and the first call to the generator’s next() function will return this line as a string. A line leading with “>A” indicates a successful initiation of the program with some information on the arguments, while a line beginning with “>E” indicates an error with the input.

  • options – string (default: "") – anything else that should be forwarded as input to Nauty’s genbgL. See its documentation for more information : http://cs.anu.edu.au/~bdm/nauty/.

    Note

    For genbgL the first class elements are vertices, and second class elements are the hypergraph’s sets.

OUTPUT:

A tuple of tuples.

EXAMPLES:

Small hypergraphs:

sage: list(hypergraphs.nauty(4, 2))
[((), (0,), (1,), (0, 1))]

>>> from sage.all import *
>>> list(hypergraphs.nauty(Integer(4), Integer(2)))
[((), (0,), (1,), (0, 1))]

Only connected ones:

sage: list(hypergraphs.nauty(2, 2, connected=True))
[((0,), (0, 1))]

>>> from sage.all import *
>>> list(hypergraphs.nauty(Integer(2), Integer(2), connected=True))
[((0,), (0, 1))]

Non-empty sets only:

sage: list(hypergraphs.nauty(3, 2, set_min_size=1))
[((0,), (1,), (0, 1))]

>>> from sage.all import *
>>> list(hypergraphs.nauty(Integer(3), Integer(2), set_min_size=Integer(1)))
[((0,), (1,), (0, 1))]

The Fano Plane, as the only 3-uniform hypergraph with 7 sets and 7 vertices:

sage: fano = next(hypergraphs.nauty(7, 7, uniform=3, max_intersection=1))
sage: print(fano)
((0, 1, 2), (0, 3, 4), (0, 5, 6), (1, 3, 5), (2, 4, 5), (2, 3, 6), (1, 4, 6))

>>> from sage.all import *
>>> fano = next(hypergraphs.nauty(Integer(7), Integer(7), uniform=Integer(3), max_intersection=Integer(1)))
>>> print(fano)
((0, 1, 2), (0, 3, 4), (0, 5, 6), (1, 3, 5), (2, 4, 5), (2, 3, 6), (1, 4, 6))

The Fano Plane, as the only 3-regular hypergraph with 7 sets and 7 vertices:

sage: fano = next(hypergraphs.nauty(7, 7, regular=3, max_intersection=1))
sage: print(fano)
((0, 1, 2), (0, 3, 4), (0, 5, 6), (1, 3, 5), (2, 4, 5), (2, 3, 6), (1, 4, 6))

>>> from sage.all import *
>>> fano = next(hypergraphs.nauty(Integer(7), Integer(7), regular=Integer(3), max_intersection=Integer(1)))
>>> print(fano)
((0, 1, 2), (0, 3, 4), (0, 5, 6), (1, 3, 5), (2, 4, 5), (2, 3, 6), (1, 4, 6))