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 or 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 and 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

| Tested | 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

| Tested | Link prediction algorithms | | Community |

• Label propagation
• Louvain method
• Girvan–Newman algorithm
• Spectral clustering
• Personalized PageRank
• Infomap
• Connected components

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

| Tested | 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

shell cargo add graphina

Or add this to your Cargo.toml:

toml [dependencies] graphina = "0.3.0-a1"

Graphina requires Rust 1.86 or later.

Documentation

See the docs for the latest documentation.

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

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

} ```

See the examples and tests directories 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).