9 releases
0.2.2  Jun 19, 2024 

0.2.1  May 2, 2024 
0.1.5  Mar 5, 2024 
0.1.4  Apr 19, 2023 
0.1.1  Jan 26, 2023 
#200 in Data structures
105KB
2K
SLoC
mhgl
Matt's HyperGraph Library (mhgl)
A library for working with undirected hypergraphs, which are a generalization of a normal graph. A hypergraph consists of a set of nodes, denoted N
, and a collection of edges where each edge is a subset of N
. For a normal graph each edge is required to be of size 2, for example an edge (u, v)
between nodes u
and v
, whereas in a hypergraph there is no limit on the size of an edge. Each node and edge are assigned IDs, with the type for the ID depending on the struct used. The HyperGraph
trait provides a common api for developing struct independent algorithms.
Hypergraph Structs
ConGraph
 a connectivity only option that usesu32
's as IDs for nodes andu64
's for edge IDs with each being a simple counter starting at 0. No data that can be stored within theConGraph
structure itself.HGraph
 A struct generic over four types: the node data, the edge data, the node IDs, and the edge IDs. There are no trait bounds on the node and edge typesaAdditionally generic over the size of integersu8
throughu128
to store NodeIDs and EdgeIDs withu32
andu64
as the default for the respective IDs.KVGraph
 A keyvalue hypergraph where each node and edge allows you to store simplekvgraph::Value
s modeled after a simple subset of the PolarsAnyValue<'a>
.
ConGraph
and KVGraph
are essentially wrappers around HGraph
with
slightly tweaked function signatures for adding and deleting nodes or edges
(for example
you don't need to provide data for adding nodes to a ConGraph
but you do
for HGraph
).
Example
use mhgl::*;
let mut cg = ConGraph::new();
let nodes = cg.add_nodes(5);
let mut edges = Vec::new();
for ix in 1..nodes.len() {
let edge = cg.add_edge(&nodes[0..=ix]);
edges.push(edge);
}
let maxs_of_edge = cg.maximal_edges(&edges[0]);
let maxs_of_nodes = cg.maximal_edges_of_nodes([0, 1, 2]);
assert_eq!(maxs_of_edge[0], edges[edges.len()  1]);
assert_eq!(maxs_of_nodes[0], edges[edges.len()  1]);
assert_eq!(cg.boundary_up(&edges[0]), vec![edges[1]]);
#[derive(Debug)]
struct Foo(u8);
#[derive(Debug)]
struct Bar(u32);
let mut hg = HGraph::<Foo, Bar>::new();
let n0 = hg.add_node(Foo(1));
let n1 = hg.add_node(Foo(2));
let e = hg.add_edge(&[n0, n1], Bar(42)).unwrap();
let e_mut = hg.borrow_edge_mut(&e).unwrap();
e_mut.0 = 12;
let bar = hg.remove_edge(e).unwrap();
assert_eq!(bar.0, 12);
let mut kvgraph = KVGraph::new();
let n0 = kvgraph.add_node_with_label("toronto");
let n1 = kvgraph.add_node_with_label("seattle");
let edge = kvgraph.add_edge_with_label(&[n0, n1], "AC123").unwrap();
kvgraph.insert(&n0, "darkness", 0.6);
kvgraph.insert(&n1, "darkness", 0.8);
let df = kvgraph.dataframe();
println!("{:}", df);
The last line in the above code when ran output:
┌────────────┬───────────────────────────────────┬───────────────────────────────────┬───────────────────┬──────────┐
│ label ┆ id ┆ nodes ┆ labelled_nodes ┆ darkness │
│  ┆  ┆  ┆  ┆  │
│ str ┆ str ┆ str ┆ str ┆ f64 │
╞════════════╪═══════════════════════════════════╪═══════════════════════════════════╪═══════════════════╪══════════╡
│ toronto ┆ 6347a42e0bde4d80aad37e8c59d3… ┆ [6347a42e0bde4d80aad37e8c59d… ┆ [toronto] ┆ 0.6 │
│ seattle ┆ 032e1a16ec3940458ebd381c2b06… ┆ [032e1a16ec3940458ebd381c2b0… ┆ [seattle] ┆ 0.8 │
│ AC123 ┆ 1b23312822d24158850db4b814d5… ┆ [1b23312822d24158850db4b814d… ┆ [seattle,toronto] ┆ null │
└────────────┴───────────────────────────────────┴───────────────────────────────────┴───────────────────┴──────────┘
Currently data schema is shared between nodes and edges, which is unfortunate.
Features
There are 2 features related to the KVGraph
module
 "uuid" to enable the use of
KVGraph
as it usesUuid
s as the ID type for both nodes and edges.  "polars" to compute
polars
dataframes of any collection of nodes or edges.
Traits

HyperGraph
 A collection of functions for querying the adjacency structure of a hypergraph. There are a few main functions, each of which takes as an input an edge ID and returns related edges in the hypergraph. Each function also has an "of_nodes" variant which allows you to find the same info but instead of requiring an input edge of the hypergraph you can provide a slice of nodes.containing_edges
finds all edges which are strict supersets of the input edge.maximal_edges
finds all edges containing the input edge that are not themselves contained in another edge.link
takes all edges which contain the given edge and computes the complement of the input within that edge.boundary_up
the boundary up operator comes from topology and the terminology of simplicial complexes. It takes the input edge and finds all edges that are only a single extra node added to the input.boundary_down
similar to theboundary_up
operator but removes a node.

HgNode
 A marker trait for indicating which types are usuable for node and edge IDs (spoiler:u8
,u16,
u32,
u64, and
u132. Don't use
Uuid`s even though they implement the trait.)
Algorithms
Mostly under construction, currently there is only a simple random walk either using link,
boundary_up
* boundary_down
, and boundary_down
* boundary_up
to determine the next subset to move to. I plan to
port some algorithms, such as the connected components, s_walk, and homology algorithms from HyperNetX
to this library over time.
Alternative Hypergraph Libraries
This library should be considered as an alpha version. Here are a few hypergraph libraries I found, the most mature of which is HyperNetX developed by Pacific Northwest National Laboratory (PNNL).
 HyperNetX (Python): The most complete hypergraph library with algorithms for homology computations. Based on python and the underlying datastructure seems to be pandas arrays.
 HypergraphDB (Java): A database backend for storing and querying data, seems unmaintained but probably was ahead of its time.
 Hypergraph (Rust): Seemed limited in scope and a bit complicated to me.
 Gudhi (C++): This library is focused on computing persistent homology bargraphs. As such it has datastructures for simplicial complexes and more.
License: MIT
Dependencies
~2–32MB
~487K SLoC