<div align="center">
<picture>
<img alt="Graphina the Dinosaur" src="logo.png" height="50%" width="50%">
</picture>
</div>
<br>
## Graphina
[](https://github.com/habedi/graphina/actions/workflows/tests.yml)
[](https://codecov.io/gh/habedi/graphina)
[](https://crates.io/crates/graphina)
[](https://docs.rs/graphina)
[](https://habedi.github.io/graphina)
[](https://github.com/habedi/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](https://github.com/petgraph/petgraph)
and [rustworkx](https://www.rustworkx.org/), 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](https://networkx.org/) but with the speed and performance benefits of
Rust.
Additionally, [PyGraphina](https://pypi.org/project/pygraphina/) Python library allows users to use Graphina in Python.
Check out [pygraphina](pygraphina/README.md) directory for more details.
See [ROADMAP.md](ROADMAP.md) for the list of implemented and planned features.
> [!IMPORTANT]
> This project is in early development, so bugs and breaking changes are expected.
> Please use the [issues page](https://github.com/habedi/graphina/issues) to report bugs or request features.
---
### 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**](src/core/types.rs) | <ul><li>Directed and undirected graphs</li><li>Weighted and unweighted graphs</li><li>NodeId and EdgeId wrappers</li><li>NodeMap and EdgeMap type aliases</li><li>OrderedNodeMap for deterministic iteration</li></ul> | Base types (graph, node, and edge) that Graphina supports |
| [**Error Handling**](src/core/error.rs) | <ul><li>Unified GraphinaError for all Graphina modules</li><li>Result type alias</li><li>Error conversion helpers</li></ul> | Error handling utilities for Graphina |
| [**Builders**](src/core/builders.rs) | <ul><li>AdvancedGraphBuilder with validation</li><li>TopologyBuilder (path, cycle, star, and complete graph builders)</li><li>Type aliases (DirectedGraphBuilder, UndirectedGraphBuilder)</li></ul> | Ergonomic graph construction utilities |
| [**IO**](src/core/io.rs) | <ul><li>Edge list (read and write)</li><li>Adjacency list (read and write)</li></ul> | I/O routines for reading and writing graph data |
| [**Serialization**](src/core/serialization.rs) | <ul><li>JSON serialization</li><li>Binary serialization</li><li>GraphML export</li><li>SerializableGraph format</li></ul> | Multiple serialization formats for interoperability |
| [**Generators**](src/core/generators.rs) | <ul><li>Erdős–Rényi graph</li><li>Watts–Strogatz graph</li><li>Barabási–Albert graph</li><li>Complete graph (directed and undirected)</li><li>Bipartite graph</li><li>Star graph</li><li>Cycle graph</li><li>Path graph</li><li>Random tree</li></ul> | Graph generators for random and structured graphs |
| [**Paths**](src/core/paths.rs) | <ul><li>Dijkstra's algorithm</li><li>Bellman-Ford algorithm</li><li>Floyd-Warshall algorithm</li><li>Johnson's algorithm</li><li>A* search algorithm</li><li>Iterative deepening A* (IDA*)</li></ul> | Shortest paths algorithms |
| [**Validation**](src/core/validation.rs) | <ul><li>Graph connectivity check</li><li>DAG validation</li><li>Bipartite check</li><li>Negative weights detection</li><li>Self-loops detection</li><li>Component counting</li><li>Algorithm precondition validators</li></ul> | Graph property validation utilities |
| [**Pool**](src/core/pool.rs) | <ul><li>NodeSet pool</li><li>NodeMap pool</li><li>NodeQueue pool</li><li>Thread-local default pools</li></ul> | Experimental memory pooling utilities |
#### Extensions
| Module | Feature/Algorithm | Notes |
|-----------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------|
| [**Centrality**](src/centrality/) | <ul><li>Degree</li><li>Closeness</li><li>Betweenness (node and edge)</li><li>Eigenvector</li><li>PageRank (standard and personalized)</li><li>Katz</li><li>Harmonic</li><li>Local reaching</li><li>Global reaching</li><li>VoteRank (seed selector)</li><li>Laplacian</li><li><em>Percolation (planned)</em></li></ul> | Centrality and influence measures |
| [**Metrics**](src/metrics/) | <ul><li>Diameter</li><li>Radius</li><li>Average clustering coefficient</li><li>Clustering coefficient (local)</li><li>Average path length</li><li>Transitivity</li><li>Triangles count</li><li>Assortativity coefficient</li></ul> | Graph-level and node-level metrics |
| [**MST**](src/mst/) | <ul><li>Prim's algorithm</li><li>Kruskal's algorithm</li><li>Borůvka's algorithm</li></ul> | Minimum spanning tree algorithms |
| [**Traversal**](src/traversal/) | <ul><li>Breadth-first search (BFS)</li><li>Depth-first search (DFS)</li><li>Iterative deepening DFS (IDDFS)</li><li>Bidirectional search</li></ul> | Graph traversal algorithms |
| [**Subgraphs**](src/subgraphs/) | <ul><li>Subgraph extraction</li><li>Induced subgraph</li><li>Ego graph</li><li>K-hop neighbors</li><li>Filter nodes or edges</li><li>Connected component extraction</li><li>Component subgraph</li></ul> | Subgraph operations and filtering |
| [**Links**](src/links/) | <ul><li>Resource allocation index</li><li>Jaccard coefficient</li><li>Adamic-Adar index</li><li>Preferential attachment</li><li>Common neighbors</li><li>CN Soundarajan-Hopcroft</li><li>RA index Soundarajan-Hopcroft</li><li>Within-inter-cluster ratio</li><li>Common neighbor centrality</li></ul> | Link prediction algorithms |
| [**Community**](src/community/) | <ul><li>Label propagation</li><li>Louvain method</li><li>Girvan-Newman algorithm</li><li>Spectral clustering</li><li>Personalized PageRank</li><li>Infomap</li><li>Connected components</li></ul> | Community detection and clustering algorithms |
| [**Approximation**](src/approximation/) | <ul><li>Node connectivity (BFS-based)</li><li>Maximum independent set (greedy)</li><li>Maximum clique (greedy heuristic)</li><li>Clique removal</li><li>Large clique size</li><li>Average clustering coefficient (approximate)</li><li>Densest subgraph (greedy peeling)</li><li>Diameter lower bound</li><li>Minimum weighted vertex cover (greedy)</li><li>Minimum maximal matching (greedy)</li><li>Ramsey number R(2,t) approximation</li><li>TSP approximations (greedy, simulated annealing, threshold accepting, and Christofides)</li><li>Treewidth decompositions (min degree, and min fill-in)</li></ul> | Approximation algorithms for NP-hard problems |
| [**Parallel**](src/parallel/) | <ul><li>Parallel BFS</li><li>Parallel degree computation</li><li>Parallel clustering coefficients</li><li>Parallel triangles counting</li><li>Parallel PageRank</li><li>Parallel shortest paths</li><li>Parallel connected components</li></ul> | Parallel implementations of popular graph algorithms |
| [**Visualization**](src/visualization/) | <ul><li>ASCII art visualization</li><li>Force-directed layout</li><li>Circular layout</li><li>Grid layout</li><li>Hierarchical layout</li><li>HTML generation</li><li>SVG export</li><li>PNG export</li><li>D3.js JSON format</li></ul> | Graph visualization algorithms |
### Installation
```shell
cargo add graphina
```
Or add this to your `Cargo.toml`:
```toml
[dependencies]
graphina = "0.3.0-alpha.4"
```
Or enable all features with:
```toml
[dependencies]
graphina = { version = "0.3.0-alpha.4", features = ["centrality", "community", "approximation", "mst", "traversal", "subgraphs", "visualization", "parallel", "pool"] }
```
> [!NOTE]
> Graphina requires Rust 1.86 or later.
### Documentation
See [docs](https://habedi.github.io/graphina) and [docs.rs/graphina](https://docs.rs/graphina) for more information for the detailed documentation
including examples and API references.
#### API Examples
##### Simple Example
```rust
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
```rust
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
```rust
use graphina::core::generators::{erdos_renyi_graph, barabasi_albert_graph};
use graphina::core::types::Undirected;
// Use 42 for pseudo-random seed (for deterministic results)
let er = erdos_renyi_graph::<Undirected>(100, 0.2, 42).unwrap();
let ba = barabasi_albert_graph::<Undirected>(1000, 3, 42).unwrap();
```
---
### Contributing
See [CONTRIBUTING.md](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](LICENSE-MIT))
* Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE))
PyGraphina is licensed under the MIT License ([LICENSE](pygraphina/LICENSE)).