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.

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 corresponing 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 corresponing 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)) # optional - nauty
[((), (0,), (1,), (0, 1))]

Only connected ones:

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

Non-empty sets only:

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

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

sage: fano = hypergraphs.nauty(7,7, uniform = 3, max_intersection =1).next() # optional - nauty
sage: print fano # optional - nauty
((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 = hypergraphs.nauty(7,7, regular = 3, max_intersection =1).next() # optional - nauty
sage: print fano # optional - nauty
((0, 1, 2), (0, 3, 4), (0, 5, 6), (1, 3, 5), (2, 4, 5), (2, 3, 6), (1, 4, 6))

Previous topic

Implements various backends for Sage graphs.

Next topic

Incidence structures (i.e. hypergraphs, i.e. set systems)

This Page