Expand description
As you may have read in the README, hypergraphs are generalisations of graphs where edges can connect any number of nodes. These edges can represent non-dyadic relationships, such as polyatomic chemical bonds (looking at you, benzene), telecommunication networks, concurrent data structures, databases, image processing, and even hypergraph neural networks. Also, they can be used for anything that graphs can be used for, since they’re a true generalisation.
The application I had in mind when I first thought of writing this library was in Identity management, where companies (or really anyone with some data) write policies to regulate access to their resources. A policy is defined as a 3-tuple, which I figured was a nice hyperedge type. Since then, I found that a couple of libraries already exist, and I’m trying to borrow the best of them all, and add something new too.
Onto the library itself, so far we have three important modules, traits, algo, and graph. graph is where the important
user-facing stuff lives, and all the nice types are defined. algo is for important graph algorithms, including several
shortest-path algorithms, flow algorithms, and more. These are borrowed from petgraph and modified to fit my traits. The
heart of the implementation (and even a good bit of the docs) is still theirs. Thanks, petgraph! The traits module is where you need to look if you want to
implement your own graph types. Even otherwise, feel free to look around and suggest improvements.
Couple of smaller modules too: the prelude, which is, as preludes are, a bundle of commonly used types and traits, and macros,
which provides some convenient macros for working with hypergraphs.
TODO:
- Test Tarjan’s algorithm: not exhaustive, but seems to work.
- Fill up last 5 traits: This is honestly a pain. Not a lot of statistics in Rust afaik.
- Specifically Hypergraph Neural Networks: Welll, this is more of a long term goal. Even in the original python hypergraphx,
it is a part of
communitymodules. So this takes a backseat. Meanwhile I’ll learn some more ML, or find someone who knows enough about it to collaborate with. Maybe the real hypergraphs were the friends we made along the way. :-)
- Specifically Hypergraph Neural Networks: Welll, this is more of a long term goal. Even in the original python hypergraphx,
it is a part of
- Do temporal graphs: By 0.0.5, promise.
- Spectral graph stuff: Started off, eigenvalues are up. We’ll see about the rest.
- Parallelism: Pain to set up parallel traversal and concurrent modification of graphs. The rayon for the weights is as far as I think I can go for now.
- Add some of the more advanced properties.
- Add cycles (3 kinds) and cycle detection.
- Start off the list of specialised graphs: DAGs, Trees, Cycles, chordal/triangle free, tournaments…
Modules§
- algo
- This module is a clone of petgraph. A lot of the docs are still theirs, so I can’t guarantee that they are accurate for the new implementation. By 0.1.0, promise.
- graph
- So far, we have eight types of hypergraphs.
- macros
- This module is heavily inspired by the
rshypercrate. - prelude
- traits
- Most of the functionality of this library is encapsulated in these traits. A quick overview:
Macros§
- hyperedge
- The
hyperedgemacro streamlines the definition of hyperedges in a hypergraph. - hypergraph
- the [
hypergraph] macro works to aide the in the creation of hypergraphs by allowing users to define nodes and edges in a hypergraph in a more declarative way. - hypernode
- the [
hypernode] macro streamlines the process of inserting nodes into a hypergraph. - impl_
graph_ basics - impl_
weights