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](https://github.com/HGX-Team/hypergraphx)), 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](https://arxiv.org/pdf/2303.15356).
# What's a Hypergraph?
A hypergraph is a generalization of a graph in which an edge can connect any number of vertices. In other words, 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
TODO.
# Algorithms on Hypergraphs
I've copied the whole `src/algo` module from petgraph, and am modifying them to work with hypergraphs.
|A-Star | Done |
| Bellman-Ford | Done |
| Dijkstra | Done |
| Dominators | Undirected |
| Feedback Arc | Not done |
| Floyd-Warshall | Done |
| Ford-Fulkerson | Directed |
| Isomorphism | Not done |
| k-shortest paths | Done |
| Matching | Not done |
| Minimum Spanning Tree | Not done |
| PageRank | Not done |
| Simple Paths | Not done |
| Transitive Reduction | Not done |
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.
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.
# Features
Multiplexes and temporal hypergraphs are their own, non-default features, as are parallel iterators over the nodes and edges of a hypergraph.