Graphina

Graphina is a graph data science library for Rust. It provides the common data structures and algorithms used for analyzing the graphs of real-world networks such as social, transportation, and biological networks.

Compared to other Rust graph libraries like petgraph and rustworkx, Graphina aims to provide a more high-level API and a wide range of ready-to-use algorithms for network analysis and graph mining tasks. The main goal is to make Graphina as feature-rich as NetworkX, but with the performance of Rust.

Additionally, PyGraphina Python library allows users to use Graphina in Python. Check out pygraphina directory for more details.

[!IMPORTANT] Graphina is in the early stages of development, so breaking changes may occur. Bugs and API inconsistencies are also expected, and the algorithms may not yet be optimized for performance.

Structure

Graphina consists of two main parts: a core library and extensions. The core library provides the basic data structures and algorithms for working with graphs. The extensions are modules outside the core library that contain more advanced algorithms for specific tasks like community detection, link prediction, and calculating node and edge centrality scores.

The extensions are independent of each other. However, they depend on the core library for the basic graph operations.

Graphina Core

Module	Feature/Algorithm	Status	Notes
Types	Directed and undirected graphs Weighted and unweighted graphs	Tested	Graph types that Graphina supports
Exceptions	List of exceptions	Tested	Custom error types for Graphina
IO	Edge list Adjacency list	Tested	I/O routines for reading/writing graph data
Generators	Erdős–Rényi graph Watts–Strogatz graph Barabási–Albert graph Complete graph Bipartite graph Star graph Cycle graph	Tested	Graph generators for random and structured graphs
Paths	Dijkstra’s algorithm Bellman–Ford algorithm Floyd–Warshall algorithm Johnson’s algorithm A* search algorithm Iterative deepening A*	Tested	Shortest paths algorithms
MST	Prim’s algorithm Kruskal’s algorithm Borůvka’s algorithm	Tested	Minimum spanning tree algorithms
Traversal	Breadth-first search (BFS) Depth-first search (DFS) Iterative deepening DFS Bidirectional search	Tested	Graph traversal algorithms

Extensions

Module	Feature/Algorithm	Status	Notes
Centrality	Degree centrality Closeness centrality Betweenness centrality Eigenvector centrality PageRank centrality Katz centrality Harmonic centrality Local/global reaching centrality Voterank centrality Laplacian centrality		Centrality measures
Links	Resource allocation index Jaccard coefficient Adamic–Adar index Preferential attachment CN Soundarajan–Hopcroft RA index Soundarajan–Hopcroft Within–inter-cluster ratio Common neighbor centrality		Link prediction algorithms
Community	Label propagation Louvain method Girvan–Newman algorithm Spectral clustering Personalized PageRank Infomap Connected components		Community detection and clustering algorithms
Approximation	Local node connectivity (BFS-based) Maximum independent set (greedy with neighbor caching) Maximum clique (greedy heuristic) Clique removal Large clique size Average clustering coefficient Densest subgraph (greedy peeling) Diameter lower bound Minimum weighted vertex cover (greedy re‑evaluated) Minimum maximal matching (greedy) Approximate Ramsey R2 TSP approximations (greedy, simulated annealing, threshold accepting, Christofides placeholder) Treewidth decompositions (min degree, min fill-in)		Approximations and heuristic methods for NP‑hard problems

[!NOTE] Status shows whether the module is Tested and Benchmarked. Empty status means the module is implemented but not tested and benchmarked yet.

Installation

cargo add graphina

Graphina requires Rust 1.83 or later.

Documentation

See the docs for the latest documentation.

Check out the docs.rs/graphina for the latest API documentation.

Simple Example

use graphina::core::types::Graph;

fn main() {
    // Create a new undirected graph
    let mut graph = Graph::new();

    // Add nodes and edges to the graph
    let n0 = graph.add_node(1);
    let n1 = graph.add_node(1);
    let n2 = graph.add_node(2);
    let n3 = graph.add_node(3);
    graph.add_edge(n0, n1, 1.0);
    graph.add_edge(n1, n2, 1.0);
    graph.add_edge(n2, n3, 1.0);

    // Get the neighbors of node 1
    for neighbor in graph.neighbors(n1) {
        println!("Node 1 has neighbor: {}", neighbor.index());
    }
}

See the tests directory for more usage examples.

Contributing

See CONTRIBUTING.md for details on how to make a contribution.

Logo

The mascot is named "Graphina the Dinosaur". As the name implies, she's a dinosaur, however, she herself thinks she's a dragon. The logo was created using Gimp, ComfyUI, and a Flux Schnell v2 model.

Licensing

Graphina is licensed under either of these:

• MIT License (LICENSE-MIT)
• Apache License, Version 2.0 (LICENSE-APACHE)

PyGraphina is licensed under the MIT License (LICENSE).