Hypergraphs Core API

Hypergraph Core

class graphcalc.hypergraphs.core.basics.Hypergraph(*, rank_max: int | None = None, allow_empty: bool = False, allow_singletons: bool = False, auto_add_vertices: bool = True, V: Iterable[Hashable] | None = None, E: Iterable[Iterable[Hashable]] | None = None)

Bases: object

Finite simple undirected hypergraph represented as a set system.

The hypergraph is stored as a pair (V, E) where V is a set of vertices and E is a set of hyperedges, each represented as a frozenset of vertices.

Conventions

• simple: duplicate hyperedges are ignored

• undirected: hyperedges are sets

• empty hyperedges are disallowed by default

• singleton hyperedges are disallowed by default

• an optional upper bound on hyperedge size may be enforced via rank_max

param rank_max:

Optional maximum allowed hyperedge size.

type rank_max:

int | None, default=None

param allow_empty:

Whether the empty hyperedge is permitted.

type allow_empty:

bool, default=False

param allow_singletons:

Whether singleton hyperedges are permitted.

type allow_singletons:

bool, default=False

param auto_add_vertices:

If True, vertices appearing in added hyperedges are automatically inserted into V. If False, each hyperedge must already be a subset of V.

type auto_add_vertices:

bool, default=True

param V:

Initial vertex set.

type V:

iterable, optional

param E:

Initial hyperedge set.

type E:

iterable of iterables, optional

Notes

The internal sets are stored privately as _V and _E. Public access is provided through read-only properties.

property E: FrozenSet[FrozenSet[Hashable]]

Return the hyperedge set as a read-only frozenset.

property V: FrozenSet[Hashable]

Return the vertex set as a read-only frozenset.

add_edge(edge: Iterable[Hashable]) → FrozenSet[Hashable]

add_edges(edges: Iterable[Iterable[Hashable]]) → None

add_vertex(v: Hashable) → None

add_vertices(vertices: Iterable[Hashable]) → None

clear() → None

copy() → Hypergraph

Return a shallow copy of the hypergraph.

d_degree(S: Iterable[Hashable]) → int

Backward-compatible alias for subset_degree().

degree(v: Hashable) → int

degree_stats() → Dict[str, float]

degrees() → Dict[Hashable, int]

dual() → Hypergraph

Return the dual hypergraph.

The vertices of the dual are the hyperedges of the original, indexed as integers 0, 1, ..., m-1 in the iteration order of self._E.

Notes

The dual may contain singleton or empty hyperedges even if the original hypergraph disallows them, so the dual is constructed with allow_empty=True and allow_singletons=True.

edge_size_counts() → Dict[int, int]

edge_sizes() → Dict[FrozenSet[Hashable], int]

edges() → Iterator[FrozenSet[Hashable]]

classmethod from_edges(edges: Iterable[Iterable[Hashable]], *, vertices: Iterable[Hashable] | None = None, rank_max: int | None = None, allow_empty: bool = False, allow_singletons: bool = False, auto_add_vertices: bool = True) → Hypergraph

Construct a hypergraph from an iterable of hyperedges.

has_edge(edge: Iterable[Hashable]) → bool

has_vertex(v: Hashable) → bool

incident_edges(v: Hashable) → Set[FrozenSet[Hashable]]

induced_subhypergraph(vertices: Iterable[Hashable]) → Hypergraph

Return the induced subhypergraph on a vertex subset.

Hyperedges are intersected with the subset and only valid resulting hyperedges are retained.

property is_empty: bool

Return True iff the hypergraph has no hyperedges.

is_incidence_connected() → bool

Test connectivity of the incidence bipartite graph.

Isolated vertices count: if V contains an isolated vertex, then the incidence graph is disconnected unless the whole hypergraph is empty.

is_uniform(k: int | None = None) → bool

Return whether the hypergraph is uniform.

If k is provided, test whether every hyperedge has size k. Otherwise, test whether all hyperedges have the same size.

property m: int

Number of hyperedges.

property n: int

Number of vertices.

neighbors(v: Hashable) → Set[Hashable]

Return the neighbors of v in the 2-section graph.

property rank: int

Maximum hyperedge size present, or 0 if there are no hyperedges.

remove_edge(edge: Iterable[Hashable]) → None

remove_vertex(v: Hashable, *, drop_incident_edges: bool = True) → None

Remove a vertex.

Parameters:

• v (hashable) – Vertex to remove.

• drop_incident_edges (bool, default=True) – If True, remove every incident hyperedge. If False, remove the vertex from each incident hyperedge and re-validate the result.

subset_degree(vertices: Iterable[Hashable]) → int

Return the number of hyperedges containing the given vertex subset.

This is also commonly called the codegree of the subset.

two_section_edges() → Set[FrozenSet[Hashable]]

Return the edge set of the 2-section graph.

validate() → None

Validate all stored hyperedges against the current configuration.

vertices() → Iterator[Hashable]