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.
[!IMPORTANT] Graphina is in the early stages of development, so breaking changes may occur.
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 designed to be independent of each other, and depend on the core library for the basic graph operations.
Graphina Core
| Module | Features/Algorithms | Status | Notes |
|---|---|---|---|
| Types | Directed and undirected graphsWeighted and unweighted graphs | Tested | Core graph types |
| Exceptions | List of exceptions | Tested | Custom error types for Graphina |
| IO | Edge listAdjacency list | Tested | I/O routines for reading/writing graph data |
| Generators | Erdős–Rényi graphWatts–Strogatz graphBarabási–Albert graphComplete graphBipartite graphStar graphCycle graph | Tested | Graph generators for random and structured graphs |
| Paths | Dijkstra’s algorithmBellman–Ford algorithmFloyd–Warshall algorithmJohnson’s algorithmA* search algorithmIterative deepening A* | Tested | Shortest paths algorithms |
| MST | Prim’s algorithmKruskal’s algorithmBorůvka’s algorithm | Tested | Minimum spanning tree algorithms |
| Traversal | Breadth-first search (BFS)Depth-first search (DFS)Iterative deepening DFSBidirectional search | Tested | Graph traversal algorithms |
Extensions
| Module | Features/Algorithms | Status | Notes |
|---|---|---|---|
| Centrality | Degree centralityCloseness centralityBetweenness centralityEigenvector centralityPageRank centralityKatz centralityHarmonic centralityLocal/global reaching centralityVoteRank centralityLaplacian centrality | Centrality measures | |
| Links | Resource allocation indexJaccard coefficientAdamic–Adar indexPreferential attachmentCN Soundarajan–HopcroftRA Index Soundarajan–HopcroftWithin–inter-cluster ratioCommon neighbor centrality | Link prediction algorithms | |
| Community | Label PropagationLouvain MethodGirvan–Newman algorithmSpectral ClusteringPersonalized PageRankInfomapConnected components | Community detection and clustering algorithms | |
| Approximation | Local node connectivity (BFS-based)Maximum independent set (greedy with neighbor caching)Maximum clique (greedy heuristic)Clique removalLarge clique sizeAverage clustering coefficientDensest subgraph (greedy peeling)Diameter lower boundMinimum weighted vertex cover (greedy re‑evaluated)Minimum maximal matching (greedy)Approximate Ramsey R2TSP 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.
Contributing
See CONTRIBUTING.md for details on how to make a contribution.
License
This project is licensed under either of these:
- MIT License (LICENSE-MIT)
- Apache License, Version 2.0 (LICENSE-APACHE)