This crate is a work in progress, and I haven't really tested anything beyond the basics.

A lot of it is taken from petgraph, which is great. A little from rshyper, which I have never used. And the whole structure comes from the python library of the same name (here), with which I am not associated in any way (although I would like to be). There's a research paper attached to that library, here.

What's a Hypergraph?

A hypergraph is a generalization of a graph in which an edge can connect any number of vertices. To elaborate, while a traditional graph edge connects exactly two vertices, a hypergraph edge (also called a hyperedge) can connect any subset of the vertex set. This means that there can be up to $2^n$ hyperedges for a set of $n$ vertices. It also means that hypergraphs can represent more complex relationships than traditional graphs.

Undirected Hypergraphs

In src/graph/undirected, you'll find Hypergraph and UniformHypergraph. These are generic over the weights of nodes and edges. A hypergraph is uniform when all hyperedges have the same number of vertices. Lots of cool algorithms and metrics work only on uniform hypergraphs - for example, there's the adjacency tensor, which is a faithful representation of a uniform hypergraph, but can't be used for non-uniform hypergraphs.

I might add more special kinds of undirected hypergraphs later, like simple hypergraphs (where no hyperedge contains a vertex more than once) or loopless hypergraphs (where no hyperedge contains a vertex that is also an endpoint of the hyperedge), or some of the named ones, like Steiner systems.

An ordinary graph, represented by the Graph type, is a 2-uniform hypergraph.

Directed Hypergraphs

In src/graph/directed, you'll find Hypergraph and UniformHypergraph. These are similar to their undirected counterparts, are generic over the weights of nodes and edges, but they contain directed hyperedges, which map sets of vertices. Analytically, you can think of the set of directed hyperedges in a graph as a function on the power set of vertices ($E: 2^V \to 2^V$).

An ordinary directed graph, represented by the DiGraph type, is a 1-uniform directed hypergraph.

Multiplex Hypergraphs

In a multiplex, several layers of edges exist atop the same set of nodes, i.e. $M = (V, E_1, E_2, \ldots, E_k)$, where each $E_i$ is a set of hyperedges. This allows for the representation of more complex relationships between nodes, as different layers can capture different types of interactions. In code, this is represented by each layer having a different type of weight.

They are generic over the weights of nodes and layers, not edges, because each layer has its own edge weight type.

There's two kinds of multiplex hypergraphs implemented in this crate: Multiplex or the aggregate multiplex, where distinct layers cannot be isolated, and the decomposed multiplex, where each layer can be treated independently. There's no single type for the decomposed multiplex - the nodes are contained in the MultiplexBase type, and each layer is a separate Layer type.

Yeah, it's not ideal. There may be significant overhaul of the src/graph/multiplex module in the future to make it more ergonomic.

Temporal Hypergraphs

Temporal hypergraphs are hypergraphs where edges are active only at certain times. Otherwise, they behave like normal hypergraphs. Any snapshot of a temporal hypergraph yields a normal hypergraph, but two snapshots taken at different times may yield different hypergraphs.

To clarify, the graph is not generally mutable, it is only edges that exhibit certain temporal properties and may or may not be active at a certain time.

Algorithms on Hypergraphs

I've copied the whole src/algo module from petgraph, and am modifying them to work with hypergraphs.

Some algorithms, like Tarjan's strongly connected components, are implemented within the src/graph module itself.

In the future, I want to add a few Approximation algorithms to the crate, which I haven't seen done elsewhere. Should be fun. This includes stuff like maximum matching, vertex covers, the Lovasz number, and others. Note: I was wrong, there are approx. algorithms in petgraph, but they haven't been called such. Also, no Lovasz number, so that's still on the table.

I might also implement randomised algorithms. I recently published another crate, erm, which provides a data type that is an ideal return type for randomised algorithms. It can be found here.

There's a lot of work to be done.

Stay tuned.

Traits

Most ways to extract information from graphs are implemented as traits in the src/traits module. This includes incidence matrices, adjacency matrices, iterators over nodes and edges, neighbourhood functions, and more. Look at the src/traits module for more information.

Opinions regarding mutability

I've tried to make sure any functions that mutate the structure of the graph are part of the individual type's implementation, and not part of any trait. In addition, functions that mutate the weights of a graph are in their own trait, Weights.

Features

Multiplexes and temporal hypergraphs are their own, non-default features, as are parallel iterators over the nodes and edges of a hypergraph.

• multiplex: Enables support for multiplex hypergraphs.
• temporal: Enables support for temporal hypergraphs.
• rayon: Enables parallel iterators over the node and edge weights of a hypergraph. Note that there's no parallel access to the structure of the graph itself, i.e. no parallel walkers - yet.
• macros: The only default-enabled feature, it enables the use of macros to construct basic hypergraphs. NOTE: The syntax inside the hypergraph! macro is not yet fixed, I might tweak it. It looked nice when I implemented it, but felt a little clunky to use.

If any of the algorithm stuff balloons, I might make it a separate feature. When I get around to HNNs (I promise I will) that'll be its own feature. Finally, when I add support for large graphs (disk writes and maybe databases), that'll be it's own feature.

AI Disclaimer

I do not use ChatGPT, Claude, Perplexity, or any online tool for code generation or assistance. I do use GitHub Copilot (you know what copilot is) for generating boilerplate code or making multiple identical code changes, never for complex logic, or any logic really. While it's excellent for assignments, I believe it cannot produce truly original content, whether in code or literature.