Hypergraph¶

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description¶

Hypergraph[{e1, e2, ...}]

represents a hypergraph whose hyperedges e_i are Lists of vertices; the vertices are derived in first-appearance order. Hypergraph[{v1, ...}, {e1, ...}] gives the vertices explicitly. Hypergraph[g] converts a Graph. Hyperedges may repeat, overlap, nest, be empty, or repeat a vertex; their order is kept for ordered (Wolfram-model) use, while set-based heads read each as the set of its vertices.

Examples (11)¶

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (6)¶

In[1]:= Hypergraph[{{1,2,3},{3,4},{4,5,6},{7}}]
Out[1]= Hypergraph[<7 vertices, 4 hyperedges>]

In[2]:= InputForm[Hypergraph[{{1,2,3},{3,4},{4,5,6},{7}}]]
Out[2]= Hypergraph[{1, 2, 3, 4, 5, 6, 7}, {{1, 2, 3}, {3, 4}, {4, 5, 6}, {7}}]

In[3]:= InputForm[Hypergraph[{1,2,2,3},{{1,2}}]]
Out[3]= Hypergraph[{1, 2, 3}, {{1, 2}}]

In[4]:= InputForm[Hypergraph[Graph[{1<->2, 2->3}]]]
Out[4]= Hypergraph[{1, 2, 3}, {{1, 2}, {2, 3}}]

In[5]:= VertexDegree[Hypergraph[{{1,2,3},{3,4},{4,5,6},{7}}]]
Out[5]= {1, 1, 2, 2, 1, 1, 1}

In[6]:= IncidenceMatrix[Hypergraph[{{1,2},{2,3,3}}]]
Out[6]= {{1, 0}, {1, 1}, {0, 2}}

Scope (1)¶

In[7]:= InputForm[Hypergraph[{1,2},{{1,5}}]]
Out[7]= Hypergraph[{1, 2}, {{1, 5}}]

Applications (4)¶

The running example: 7 vertices, 4 hyperedges

In[8]:= h = Hypergraph[{{1, 2, 3}, {3, 4}, {4, 5, 6}, {7}}]
Out[8]= Hypergraph[<7 vertices, 4 hyperedges>]

Vertices, in first-appearance order

In[9]:= VertexList[h]
Out[9]= {1, 2, 3, 4, 5, 6, 7}

The hyperedges, kept exactly as written

In[10]:= EdgeList[h]
Out[10]= {{1, 2, 3}, {3, 4}, {4, 5, 6}, {7}}

The shared Graph accessors work on a Hypergraph

In[11]:= {VertexCount[h], EdgeCount[h]}
Out[11]= {7, 4}

Options & behaviour¶

An unknown vertex in a hyperedge leaves the call unevaluated:

Implementation notes¶

Algorithm. builtin_hypergraph is a canonicalising constructor with three accepted forms. Hypergraph[{e1, ...}] derives the vertices in first-appearance order; Hypergraph[{v1, ...}, {e1, ...}] takes them explicitly (duplicates dropped, first occurrence kept); Hypergraph[g] turns each edge u<->v/u->v of a Graph into the hyperedge {u, v}. A hyperedge must be a List; anything else leaves the call unevaluated. A canonical, already-valid Hypergraph is its own fixed point — the builtin returns NULL for it. Vertices are resolved by an integer fast path when every element is a machine integer in a range at most 4n + 1024 wide (Range[n], Wolfram-model states): first appearance by direct addressing into a seen bitmap, which skips the hash index for the dominant Σ|e| element-resolution cost; otherwise through the GraphVIdx open-addressing hash. Construction then seeds the validated-hypergraph memo (hyp_memo_from), resolving every hyperedge element to a vertex index.

Data structures. The object is a plain Expr tree Hypergraph[List, List] — no new EXPR_* tag. The memo (HYP_MEMO_SLOTS = 4, LRU-evicted, keyed by node pointer and holding an expr_copy reference so the node stays alive and immutable) stores the vertex index, the hyperedges as a vertex-index CSR in two forms — eoff/ev (raw, repeats kept) and soff/sv (distinct vertices, aliasing the raw arrays when no hyperedge repeats a vertex) — and, built lazily on first need, the vertex→hyperedge incidence CSR (voff/ve). hyp_int_list returns a packed int64 buffer above the packing threshold.

Complexity / limits. Construction is O(Σ|e|); validation by every later head is O(1) on a memo hit. The integer fast path roughly halves construction. Hyperedge counts and total incidence are capped at INT32_MAX. The memo is module-static and lock-free: hypergraph builtins run only on the evaluator thread.

Hypergraphs are ordinary Expr trees of the canonical form Hypergraph[{v1, ..., vn}, {e1, ..., em}] — no new EXPR_* tag. Each hyperedge is a List of vertices; vertices are arbitrary, pairwise distinct expressions. Hyperedges may repeat (a multi-hypergraph), overlap or nest, be empty, and may repeat a vertex ({1, 1, 2}, as Wolfram-model states do).
A hyperedge List is kept exactly as written: order-sensitive heads (HypergraphToGraph, EdgeList/InputForm, HyperedgeSizes and the arity heads, HypergraphEdgeDelete) see the order and repeats; every set-theoretic head reads a hyperedge as the set of its distinct vertices (see the category preamble).
Anything malformed (a non-List hyperedge, an unknown vertex, other arities) is left unevaluated. A valid hypergraph is its own fixed point.
Standard output is the terse summary Hypergraph[<n vertices, m hyperedges>]; InputForm/FullForm print the literal, which round-trips through the parser.
Construction seeds the validated-hypergraph memo (vertex hash index plus a vertex-index CSR of the hyperedges), so validation by later heads is O(1). When every vertex is a machine integer in a range at most 4n + 1024 wide, elements resolve by direct addressing, roughly halving construction time.
Shared Graph accessors accept a Hypergraph: VertexList, EdgeList (the hyperedge Lists as written), VertexCount, EdgeCount; VertexDegree[h] / VertexDegree[h, v] (hyperedges containing the vertex — repeated hyperedges count separately, a vertex repeated inside one hyperedge counts once; packed above the packing threshold); IncidenceMatrix[h] (the dense, packed n × m matrix of occurrence counts — 0/1 for set-like hyperedges, the multiplicity otherwise, as IncidenceMatrix gives 2 for a Graph self-loop; Mathilda has no SparseArray). VertexInDegree/VertexOutDegree are Graph-only and stay unevaluated.
Mathematica has no built-in Hypergraph; the name follows the WolframInstitute/Hypergraph paclet.
Benchmark (experiment 96): construction of 10⁵ hyperedges 19.9 ms (Mathematica paclet 2912 ms, xgi 301 ms); VertexDegree 0.005 ms warm / 0.432 ms cold; IncidenceMatrix 1000 × 10⁴ 0.365 ms warm / 0.498 ms cold.

Attributes: Protected.

References¶

C. Berge, Hypergraphs: Combinatorics of Finite Sets, North-Holland Mathematical Library 45 (Elsevier, 1989).
Source: src/graph/hyp_util.c
Specification: docs/spec/builtins/hypergraphs.md
Tests: tests/test_graphplot.c
Tests: tests/test_hypergraph.c

Notes & additional examples¶

Notes¶

A Hypergraph is an ordinary Expr tree, Hypergraph[{v1, ..., vn}, {e1, ..., em}], with no new kernel type — the same uniformity that lets Part, Map and the Graph accessors apply to it. Each hyperedge is a List of vertices; vertices are arbitrary, pairwise-distinct expressions. Hyperedges may repeat (a multi-hypergraph), overlap, nest, be empty, or repeat a vertex ({1, 1, 2}, as Wolfram-model states do).

Order is kept, and that is deliberate. Order-sensitive heads (HypergraphToGraph, EdgeList, the arity heads, HypergraphEdgeDelete) see the hyperedge exactly as written; every set-theoretic head reads it as the set of its distinct vertices. So one object answers both the ordered (directed) and the unordered question.

Standard output is the terse summary Hypergraph[<n vertices, m hyperedges>]; InputForm and FullForm print the literal, which round-trips through the parser. Mathematica has no built-in Hypergraph; the name follows the WolframInstitute/Hypergraph paclet.