```
____ ____._____ .______ .______ ._______ .___.__
\ \_/ /:_ ___\ : __ \ : \ : ____ |: | \
\___ ___/ | |___| \____|| . || : || : |
/ _ \ | / || : \ | : || |___|| . |
/___/ \___\|. __ || |___\|___| ||___| |___| |
:/ |. ||___| |___| |___|
: :/
:
```
[](https://crates.io/crates/xgraph)
[](https://docs.rs/xgraph)
## XGraph: Advanced Graph Algorithms in Rust
XGraph is a Rust library providing high-performance graph algorithms for real-world
problems such as social network analysis, transportation network optimization, and
recommendation systems.
It offers both a generic homogeneous `Graph` and a `HeterogeneousGraph` multigraph in
which nodes and edges can carry multiple distinct types — letting you model intricate
systems featuring:
- *Diverse node types (e.g. users, items, or locations)*
- *Multiple edge types between the same pair of nodes (e.g. friendships, transactions, or routes)*
## 🌟 Why XGraph?
- **High performance**: efficient algorithms backed by slab-based storage and an edge index for fast lookups.
- **Flexible data model**: custom node/edge data, weighted edges, and arbitrary string attributes, for both homogeneous and heterogeneous multigraphs.
- **Practical algorithms**: connectivity, shortest paths, centrality, community detection, bridges, dominating sets, and cycle detection.
- **Easy integration**: a small API with CSV import/export.
## 💼 Applications
- **Social network analysis**: detect key influencers and communities.
- **Logistics & routing**: find shortest and most reliable paths.
- **Telecommunication networks**: identify critical nodes and links.
- **Recommendation systems**: analyze user–item interaction graphs.
## 📦 Installation
Add XGraph to your `Cargo.toml`:
```toml
[dependencies]
xgraph = "2.1"
```
Both the `graph` and `hgraph` features are enabled by default. To pull in only the
homogeneous graph:
```toml
[dependencies]
xgraph = { version = "2.1", default-features = false, features = ["graph"] }
```
## Features 🌟
### Flexible Graph Structure
- Directed and undirected graphs
- Custom node/edge data types and weighted edges
- Arbitrary string attributes on nodes and edges
- Heterogeneous multigraphs: multiple node/edge types and parallel edges between the same pair of nodes
### Heterogeneous Multigraph Support
`HeterogeneousGraph` (in the `hgraph` module) extends the core graph with:
- **Heterogeneous nodes**: nodes can hold different data types within the same graph, representing distinct entity types (e.g. users and items in a recommendation system).
- **Multiple edge types**: several edges between the same pair of nodes are allowed, each with its own data type and attributes (e.g. "friendship" and "colleague" relationships).
- **Static typing**: node and edge types are defined through the `NodeType` and `EdgeType` traits, so all core functionality is preserved while adding multigraph capabilities.
This is ideal for modeling multi-modal transportation networks (roads, rails, flights)
or social networks with varied interaction types.
### Core Algorithms
- **Bridge detection**: identifies critical edges whose removal would disconnect the graph; heterogeneous support via `hgraph::h_bridges::HeteroBridges`.
- **Centrality measures**: degree, betweenness, and closeness centrality to evaluate node importance.
- **Connectivity analysis**: strongly and weakly connected components (Kosaraju), plus connectivity checks.
- **Leiden community detection**: deterministic and non-deterministic variants, including clustering restricted to selected edge types.
- **Shortest paths (Dijkstra)**: single-source distances, extensible to multigraphs with type-specific weights.
- **Dominating set finding**: greedy minimal dominating sets.
- **Cycle detection**: for directed and undirected graphs.
### Advanced Operations
- Adjacency matrix conversion
- Graph validation
- Batch node/edge operations
- Attribute management
- CSV import/export
## Quick Start 🚀
### Homogeneous graph
```rust
use xgraph::graph::graph::Graph;
use xgraph::graph::algorithms::shortest_path::ShortestPath;
let mut graph = Graph::<u32, &str, &str>::new(false);
let a = graph.add_node("A");
let b = graph.add_node("B");
let c = graph.add_node("C");
graph.add_edge(a, b, 5, "road").unwrap();
graph.add_edge(b, c, 3, "road").unwrap();
let distances = graph.dijkstra(a).unwrap();
assert_eq!(distances[&c], 8);
```
### Heterogeneous multigraph
```rust
use xgraph::hgraph::h_graph::HeterogeneousGraph;
use xgraph::hgraph::h_node::NodeType;
use xgraph::hgraph::h_edge::EdgeType;
#[derive(Clone, Eq, PartialEq, Hash, Debug)]
struct City(String);
impl NodeType for City {
fn as_string(&self) -> String {
self.0.clone()
}
}
#[derive(Clone, Debug, Default, PartialEq)]
struct Route(String);
impl EdgeType for Route {
fn as_string(&self) -> String {
self.0.clone()
}
}
let mut graph = HeterogeneousGraph::<f64, City, Route>::new(false);
let oslo = graph.add_node(City("Oslo".into()));
let bergen = graph.add_node(City("Bergen".into()));
// Parallel edges of different types between the same pair of nodes.
graph.add_edge(oslo, bergen, 500.0, Route("rail".into())).unwrap();
graph.add_edge(oslo, bergen, 460.0, Route("road".into())).unwrap();
assert_eq!(graph.get_edges_between(oslo, bergen).len(), 2);
```
### Runnable examples
The repository ships two complete, runnable examples (both features are on by default):
```bash
cargo run --example basic_usage # homogeneous Graph
cargo run --example h_basic_usage # heterogeneous multigraph (Viking trade routes)
```
## Cargo Features
- `graph` (default): the homogeneous `Graph` type and its algorithms.
- `hgraph` (default): the `HeterogeneousGraph` multigraph type and its algorithms.
## Testing & Validation ✅
Test coverage includes:
- Graph manipulation invariants (including non-contiguous node IDs after removals)
- Algorithm correctness checks
- Edge case handling
- CSV round-trip serialization
Run the suite with:
```bash
cargo test --all-features
```
## Documentation 📚
Full API documentation is available on [docs.rs](https://docs.rs/xgraph).
## License 📄
MIT License — see [LICENSE](LICENSE) for details.