Hypergraphs

Hypergraphs

A hypergraph is a pair H=(V,E) where V is a (finite) set and E is a set of subsets of V.

Basic Operations

Creating

Create a new hypergraph with H = HyperGraph{T}() where T is the datatype of the vertices, or HG{T}().

Given an n-by-m matrix A, use HyperGraph(A) to create a hypergraph with vertex set {1,2,...,n} with edges determined by the nonzero entries in the columns of A. This acts like an inverse operation to incidence.

Warning: Do not use HyperGraph{Any} because a Set of objects also matches Any; there would be no clear way to distinguish vertices from edges.

The convenience function IntHypergraph() is a synonym for HyperGraph{Int}(). Also: IntHypergraph(n) creates a new HyperGraph{Int} with vertex set {1,2,...,n} and no edges.

Similarly, StringHypergraph() is a synonym for HyperGraph{String}().

The function CompleteHypergraph(n,k) creates a hypergraph with vertex set {1,2,...,n} whose edges are all k-element subsets of the vertex set.

In addition, RandomHypergraph(n,k,p) creates a random k-uniform hypergraph with n vertices. A given k-element subset of {1,2,...,n} is an edge with probability p (independently).

Example

The points and lines of a finite projective plane are a natural example of a hypergraph. Using the BalancedIncompleteBlockDesigns module, we can create such a hypergraph for a plane of prime order like this:

HyperGraph(prime_plane(n))

Adding

• To add a vertex to a hypergraph use add!(H,v) where the type of v needs to be of the appropriate type.

• Edges are sets of vertices and they are added by add!(H,e) where e is either a Set or a one-dimensional array of elements of the appropriate type. Note that if some elements of e are not already vertices of H they are added to H's vertex set.

• An edge with at least two elements may also be added by listing its vertices as arguments. The following are all equivalent:

add!(H,Set(1:3))
add!(H,[1,2,3])
add!(H,1,2,3)

These functions return true if successful in adding a new elementsto the hypergraph and false if the vertex/edge already exists.

Deleting

• To delete a vertex from a hypergraph use delete!(H,v) where v must be of the appropriate type. When a vertex is deleted, so are all edges that contain it.

• To delete an edge from a hypergraph use delete!(H,e) where e is a Set or a one-dimensional array of elements of the appropriate type. One may also specify e by a list of arguments. The following are all equivalent:

delete!(H,Set(1:3))
delete!(H,[1,2,3])
delete!(H,1,2,3)

Querying

• Use NE(H) and NV(H) to determine the number vertices and edges, respectively, in H.

• The functions vlist(H) and elist(H) return the vertices and edges, respectively, as lists (one-dimensional arrays).

• Use vertex_type(H) to check the datatype of the vertices.

• For a vertex v, use H[v] to return the set of edges that contain v.

• Use deg(H,v) to determine the number of edges that contain v, i.e., its degree.

• Use has(H,v) or has(H,e) to determine if H contains vertex v or edge e, respectively. For edge queries, e is a set, a list, or a sequence of two or more arguments. Warning: The following are not the same: has(G,1) and has(G,[1]). The first checks if 1 is a vertex and the second checkes if {1} is an edge.

• The function is_uniform(H) determines if H is a uniform hypergraph. That is, if all edges have the same size.

• incidence(H) returns an n-by-m incidence matrix of the hypergraph H. The rows correspond to the vertices and the columns to the edges. There is a 1 in position i,j precisely when vertex i is an element of edge j. Other entries are 0.

Conversion to/from an UndirectedGraph

Use G = UndirectedGraph(H) or simplify(H) to convert H to an UndirectedGraph. The vertex set of G is the same as the vertex set of H. Two vertices of G are adjacent if and only if they are elements of a common edge of H. In other words, each edge of H becomes a clique of G.

Note that a UndirectedGraph does not contain loops; singleton edges of H make no contribution to the edge set of G.

Conversely, if G is a UndirectedGraph, then use HyperGraph(G) (or HG(G)) to convert to a hypergraph.