Hypergraph generators¶

At the moment this module only implement one method, which calls Brendan McKay’s Nauty (http://cs.anu.edu.au/~bdm/nauty/) to enumerate hypergraphs up to isomorphism.

class sage.graphs.hypergraph_generators.HypergraphGenerators

A class consisting of constructors for common hypergraphs.

BinomialRandomUniform(n, k, p)

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()
19600
sage: hypergraphs.BinomialRandomUniform(50, 3, 0).num_blocks()
0

CompleteUniform(n, k)

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())
2

UniformRandomUniform(n, k, m)

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

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, options='', debug=False)

Enumerates hypergraphs up to isomorphism using Nauty.

INPUT:

• number_of_sets, number_of_vertices (integers)

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

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

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

• regular (integer) – 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 (integer) – 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 (integer) – constraints the maximum cardinality of the intersection of two sets fro the hypergraphs. Set to None by default.

• connected (boolean) – whether to require the hypergraphs to be connected. Set to False by default.

• debug (boolean) – if True the first line of genbg’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) – anything else that should be forwarded as input to Nauty’s genbg. See its documentation for more information : http://cs.anu.edu.au/~bdm/nauty/.

Note

For genbg 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))]


Only connected ones:

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


Non-empty sets only:

sage: list(hypergraphs.nauty(3,2, set_min_size = 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))


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