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 (), with which I am not associated in any way (although I would like to be). There's a research paper attached to that library,
.
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: 2V \to 2V$).
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.
| Algorithm | Status |
|---|---|
| A-Star | Undirected |
| Bellman-Ford | Undirected |
| Dijkstra | Undirected |
| Dominators | Undirected |
| Feedback Arc | Not done |
| Floyd-Warshall | Undirected |
| Ford-Fulkerson | Directed |
| Isomorphism | Not done |
| k-shortest paths | Undirected |
| 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.
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.