Skip to content
Proyectos

yamafaktory/hypergraph has 356 GitHub stars and 14 forks. Star changes are not measured yet. Last checked 2026-11-16 01:55 UTC. Last push 2026-05-25.

Cómo se miden estas cifras

What you can do

  • 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
  • Graph traversal: BFS, DFS, reachability, topological sort, random walks

Crecimiento de estrellas medido

in 24h
Actualización retrasada
in 7 days
Actualización retrasada
in 15 days
Actualización retrasada
in 1 month
Actualización retrasada

Cambios netos en períodos que se solapan, no totales diarios. Los datos no disponibles se dejan en blanco. Las estrellas indican interés, no calidad.

Acerca de

Hypergraph is a data structure library to create a directed hypergraph in which a hyperedge can join any number of vertices.

Datos

README.md

Original

graph


GitHub Workflow Status Crates.io docs.rs

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.