README.md

May 25, 2026 · View on GitHub

graph

Hypergraph is a data structure library to generate directed hypergraphs.

A hypergraph is a generalization of a graph in which a hyperedge can join any number of vertices.

📣 Goal

This library aims at providing the necessary methods for modeling complex, multiway (non-pairwise) relational data found in complex networks. One of the main advantages of using a hypergraph model over a graph one is to provide a more flexible and natural framework to represent entities and their relationships (e.g. Alice uses some social network, shares some data to Bob, who shares it to Carol, etc).

🎁 Features

This library enables you to represent:

non-simple hypergraphs with two or more hyperedges containing the exact same set of vertices
self-loops — i.e., hyperedges containing vertices directed to themselves one or more times
unaries — i.e., hyperedges containing a unique vertex

And to compute:

Graph traversal: BFS, DFS, reachability, topological sort, random walks
Shortest paths: Dijkstra point-to-point and single-source
Structural analysis: strongly connected components, weakly connected components, all simple paths, subgraph extraction, cycle detection, connectivity, transitive closure
Filtered views: retain_vertices, retain_hyperedges
Graph projections: incidence matrix (dense and COO sparse), Laplacian, line graph, dual hypergraph
Analytics: PageRank, centrality scores (degree, closeness, betweenness), nestedness profile
Generic query interface: HypergraphQuery trait works over both Hypergraph and PersistentHypergraph

📐 API reference

Graph primitives

Available on both Hypergraph and PersistentHypergraph via the HypergraphQuery trait.

Method	Description
`count_vertices()` / `count_hyperedges()`	Number of elements
`is_empty()`	Whether the graph has any vertices
`vertex_indices()` / `hyperedge_indices()`	All stable indices
`get_vertex_weight(idx)` / `get_hyperedge_weight(idx)`	Weight lookup by index
`get_vertex_hyperedges(idx)`	Hyperedge indices that include a vertex
`get_hyperedge_vertices(idx)`	Ordered vertex list of a hyperedge

Vertex and hyperedge lookups

Method	Description
`contains_vertex(weight)`	Whether any vertex has the given weight
`get_vertex_index(weight)`	Indices of all vertices with the given weight
`find_hyperedges_by_weight(weight)`	Indices of all hyperedges with the given weight
`get_adjacent_vertices_from(v)`	Vertices directly reachable from `v`
`get_adjacent_vertices_to(v)`	Vertices with a direct edge into `v`
`get_full_adjacent_vertices_from(v)`	Neighbours from `v` paired with their connecting hyperedges
`get_full_adjacent_vertices_to(v)`	Predecessors of `v` paired with their connecting hyperedges
`get_full_vertex_hyperedges(v)`	Vertex lists of every hyperedge containing `v`
`get_vertex_degree_in(v)` / `get_vertex_degree_out(v)`	In/out degree
`get_hyperedges_intersections(edges)`	Shared vertices across multiple hyperedges
`get_hyperedges_connecting(from, to)`	Hyperedges that contain a directed `from→to` pair
`get_vertex_neighborhood(v)`	All co-members of `v` across every hyperedge it belongs to

Graph traversal

Method	Description
`get_bfs(from)`	Breadth-first traversal order from a vertex
`get_dfs(from)`	Depth-first traversal order from a vertex
`is_reachable(from, to)`	Whether `to` is reachable from `from`
`get_all_paths(from, to)`	All simple paths between two vertices
`topological_sort()`	Kahn's algorithm; returns an error on cycles
`random_walk(from, steps, seed)`	Random walk of `steps` hops from a vertex

Shortest paths

Method	Description
`get_dijkstra_connections(from, to)`	Cheapest path with hyperedge trace
`get_dijkstra_connections_with_cost(from, to)`	Same, plus the total cost
`get_dijkstra_from(from)`	Cheapest cost to every reachable vertex

Structural analysis

Method	Description
`strongly_connected_components()`	Kosaraju's algorithm
`connected_components()`	Weakly connected components
`is_acyclic()`	Cycle detection
`find_cut_vertices()`	Articulation points via iterative Tarjan DFS
`subgraph(vertices)`	Induced subgraph over a vertex set
`is_connected()`	Whether the hypergraph is connected (clique-expansion BFS)
`get_transitive_closure()`	All directed reachability pairs `(from, to)`

Graph properties

Method	Description
`get_orphan_vertices()`	Vertices belonging to no hyperedge
`get_orphan_hyperedges()`	Hyperedges with an empty vertex list
`get_endpoints()`	`(sources, sinks)` — in-degree 0 / out-degree 0
`get_inclusions()`	All proper subset/superset pairs of hyperedges
`is_k_uniform(k)`	Whether every hyperedge has exactly `k` vertices
`get_core(min_degree, min_size)`	k-core decomposition via iterative peeling
`get_nestedness_profile()`	Per-size inclusion statistics as `Vec<NestednessEntry>`

Graph projections

Method	Description
`expand_to_graph()`	Directed graph from consecutive vertex pairs
`expand_to_star()`	Bipartite vertex–hyperedge membership pairs
`to_incidence_matrix()`	Dense vertex × hyperedge incidence matrix
`to_incidence_matrix_coo()`	Sparse COO (row, col) pairs for the incidence matrix
`to_laplacian(normalized)`	Clique-expansion Laplacian (raw or normalized)
`get_line_graph()`	Pairs of hyperedges sharing at least one vertex
`get_dual()`	Dual hypergraph: per-vertex sorted list of incident hyperedges

Analytics

Method	Description
`compute_page_rank(damping, iterations)`	Iterative PageRank power method
`compute_centrality(v)`	Degree, closeness, and betweenness centrality for a vertex

Mutations (`Hypergraph` only)

Method	Description
`new()` / `with_capacity(n)`	Create an empty graph
`add_vertex(weight)`	Add a vertex; returns its stable `VertexIndex`
`add_hyperedge(vertices, weight)`	Add a hyperedge; returns its stable `HyperedgeIndex`
`remove_vertex(idx)`	Remove a vertex and all hyperedges that contain it
`remove_hyperedge(idx)`	Remove a hyperedge
`update_vertex_weight(idx, weight)`	Replace a vertex's weight
`update_hyperedge_weight(idx, weight)`	Replace a hyperedge's weight
`update_hyperedge_vertices(idx, vertices)`	Replace a hyperedge's vertex list
`retain_vertices(predicate)`	Remove vertices that fail the predicate
`retain_hyperedges(predicate)`	Remove hyperedges that fail the predicate
`contract_hyperedge_vertices(edge, merge, into)`	Contract a set of vertices to one
`join_hyperedges(edges)`	Merge hyperedges into their union
`reverse_hyperedge(edge)`	Reverse the vertex ordering of a hyperedge
`clear_hyperedges()`	Remove all hyperedges, keeping vertices
`clear()`	Remove everything
`append_vertex_to_hyperedge(edge, vertex)`	Append a vertex to the end of a hyperedge
`prepend_vertex_to_hyperedge(edge, vertex)`	Prepend a vertex to the start of a hyperedge
`insert_vertex_into_hyperedge(edge, vertex, pos)`	Insert a vertex at a given position
`delete_vertex_from_hyperedge(edge, vertex)`	Remove the first occurrence of a vertex from a hyperedge
`split_hyperedge(edge, at, weight)`	Split a hyperedge at an index into two new hyperedges
`split_vertex(vertex, edges, weight)`	Create a new vertex replacing `vertex` in specified hyperedges
`merge_vertices(primary, secondaries, weight)`	Merge multiple vertices into one
`get_k_skeleton(k)`	Subhypergraph of all hyperedges with at most `k` vertices (stable indices)
`get_edge_induced_subhypergraph(edges)`	Subhypergraph induced by specified hyperedges (reassigned indices)

Iterators (`Hypergraph` only)

Method	Description
`iter()`	Borrowing iterator over `(&HE, Vec<&V>)` tuples
`vertices_iter()`	Iterator over `(VertexIndex, &V)` pairs
`hyperedges_iter()`	Iterator over `(HyperedgeIndex, &HE)` pairs
`into_iter()`	Consuming iterator over `(HE, Vec<V>)` tuples

⚗️ Implementation

100% safe Rust
Proper error handling
Stable indexes for each hyperedge and each vertex — identity is the index, not the weight; duplicate weights are allowed on both sides
Parallelism (with Rayon)
HypergraphQuery<V, HE> trait — implement 9 primitives to get all graph algorithms for free; use it for generic functions and trait objects that work with either backend
Optional serde support (features = ["serde"] in Cargo.toml)
Optional persistence support (features = ["persistence"] in Cargo.toml)

🛠️ Installation

Add this to your Cargo.toml (replace current_version with the latest version of the library):

[dependencies]
hypergraph = "current_version"

To enable disk-backed persistent graphs:

[dependencies]
hypergraph = { version = "current_version", features = ["persistence"] }

💾 Persistent graphs

The persistence feature unlocks PersistentHypergraph, a disk-backed variant built on an LSM-tree (via fjall) with an in-memory hot-data cache. It supports graphs that exceed available RAM and survives process restarts without any manual serialization step.

use std::sync::Arc;
use hypergraph::PersistentHypergraph;

// Opens the database directory, or creates it if it doesn't exist.
let g = Arc::new(PersistentHypergraph::<MyVertex, MyEdge>::open("/var/data/my-graph")?);

// All write methods take &self — share freely across threads.
let g2 = Arc::clone(&g);
std::thread::spawn(move || {
    g2.add_vertex(my_vertex)?;
    Ok(())
});

Vertex and hyperedge types must implement serde::Serialize + serde::DeserializeOwned in addition to the usual trait bounds.

A bounded LRU cache (via quick-cache) sits in front of the disk store, keeping hot vertex weights and hyperedges in memory. The default capacity is 10 000 entries per layer; use PersistentHypergraph::open_with_capacity to tune it for your workload.

⚡️ Usage

Please read the documentation to get started.