Graphina

Graphina is a graph data science library for Rust. It provides common data structures and algorithms for analyzing 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. Graphina aims to be as feature-rich as NetworkX but with the speed and performance benefits of Rust.

Additionally, the PyGraphina Python library allows using Graphina from Python. Check out the pygraphina directory for more details.

---

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.

Extensions are independent of each other but depend on the core library. To use an extension, you must enable it in your Cargo.toml file as a feature (see Installation section below).

Graphina Core

Module	Feature or Algorithm	Notes
Types	Directed and undirected graphs Weighted and unweighted graphs NodeId and EdgeId wrappers NodeMap and EdgeMap type aliases OrderedNodeMap for deterministic iteration	Base types (graph, node, and edge) that Graphina supports
Error Handling	Unified GraphinaError for all Graphina modules Result type alias Error conversion helpers	Error handling utilities for Graphina
Builders	AdvancedGraphBuilder with validation TopologyBuilder (path, cycle, star, and complete graph builders) Type aliases (DirectedGraphBuilder, UndirectedGraphBuilder)	Ergonomic graph construction utilities
IO	Edge list (read and write) Adjacency list (read and write)	I/O routines for reading and writing graph data
Serialization	JSON serialization Binary serialization GraphML export SerializableGraph format	Multiple serialization formats for interoperability
Generators	Erdős–Rényi graph Watts–Strogatz graph Barabási–Albert graph Complete graph (directed and undirected) Bipartite graph Star graph Cycle graph Path graph Random tree	Graph generators for random and structured graphs
Paths	Dijkstra's algorithm Bellman-Ford algorithm Floyd-Warshall algorithm Johnson's algorithm A* search algorithm	Shortest paths algorithms
Validation	Graph connectivity check DAG validation Bipartite check Negative weights detection Self-loops detection Component counting Algorithm precondition validators	Graph property validation utilities

Extensions

Module	Feature/Algorithm	Notes
Centrality	Degree Closeness Betweenness (node and edge) Eigenvector PageRank (standard and personalized) Katz Harmonic Local reaching Global reaching VoteRank (seed selector) Laplacian	Centrality and influence measures
Metrics	Diameter Radius Average clustering coefficient Clustering coefficient (local) Average path length Transitivity Triangles count Assortativity coefficient	Graph-level and node-level metrics
MST	Prim's algorithm Kruskal's algorithm Borůvka's algorithm	Minimum spanning tree algorithms
Traversal	Breadth-first search (BFS) Depth-first search (DFS) Iterative deepening DFS (IDDFS) Bidirectional search	Graph traversal algorithms
Subgraphs	Subgraph extraction Induced subgraph Ego graph K-hop neighbors Filter nodes or edges Connected component extraction Component subgraph	Subgraph operations and filtering
Links	Resource allocation index Jaccard coefficient Adamic-Adar index Preferential attachment Common neighbors 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 Infomap Connected components	Community detection and clustering algorithms
Approximation	Node connectivity (BFS-based) Maximum independent set (greedy) Maximum clique (greedy heuristic) Clique removal Large clique size Average clustering coefficient (approximate) Densest subgraph (greedy peeling) Minimum weighted vertex cover (greedy) Minimum maximal matching (greedy) Ramsey number R(2,t) approximation TSP approximation (greedy nearest-neighbor) Treewidth decompositions (min degree, and min fill-in)	Approximation algorithms for NP-hard problems
Parallel	Parallel BFS Parallel degree computation Parallel clustering coefficients Parallel triangles counting Parallel PageRank Parallel shortest paths Parallel connected components	Parallel implementations of popular graph algorithms

Installation

cargo add graphina

Or add this to your Cargo.toml:

[dependencies]
graphina = "0.4.0-alpha.4"

Or enable all features with:

[dependencies]
graphina = { version = "0.4.0-alpha.4", features = ["centrality", "community", "approximation", "mst", "traversal", "subgraphs", "parallel", "links", "metrics"] }

Note

Graphina requires Rust 1.85 or later.

WebAssembly Support

Graphina compiles for the wasm32-unknown-unknown target with all features enabled and needs no extra configuration.

Note

In Wasm build, the parallel algorithms run sequentially because the target has no threads, and the file-based IO and serialization functions return an error at runtime because the target has no filesystem.

Documentation

See the documentation and docs.rs/graphina for detailed examples and API references.

API Examples

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());
    }
}

Graph Builder API

use graphina::core::builders::UndirectedGraphBuilder;

// Use graph builder API to create an undirected graph
let g = UndirectedGraphBuilder::<i32, f64>::undirected()
.with_capacity(4, 3)
.add_node(1)
.add_node(2)
.add_node(3)
.add_edge(0, 1, 1.0)
.add_edge(1, 2, 2.0)
.build()
.unwrap();

Seeded Generators

use graphina::core::generators::{erdos_renyi_graph, barabasi_albert_graph};
use graphina::core::types::Undirected;

// Use 68 for the seed to generate reproducible random graphs
let er = erdos_renyi_graph::<Undirected>(100, 0.2, 68).unwrap();
let ba = barabasi_albert_graph::<Undirected>(1000, 3, 68).unwrap();

---

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).