xgraph 2.1.0

 ____   ____._____  .______  .______  ._______ .___.__  
 \   \_/   /:_ ___\ : __   \ :      \ : ____  |:   |  \ 
  \___ ___/ |   |___|  \____||   .   ||    :  ||   :   |
  /   _   \ |   /  ||   :  \ |   :   ||   |___||   .   |
 /___/ \___\|. __  ||   |___\|___|   ||___|    |___|   |
             :/ |. ||___|        |___|             |___|
             :   :/                                     
                 :                                      

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:

[dependencies]
xgraph = "2.1"

Both the graph and hgraph features are enabled by default. To pull in only the homogeneous graph:

[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

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

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

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:

cargo test --all-features

Documentation 📚

Full API documentation is available on docs.rs.

License 📄

MIT License — see LICENSE for details.