SciRS2 Graph

Production-ready graph processing module for the SciRS2 scientific computing library (v0.1.5).

This is Stable Release (stable) featuring SciRS2 POLICY implementation and a comprehensive, high-performance graph theory and network analysis library designed for scientific computing and machine learning applications. Following the SciRS2 POLICY, this module ensures ecosystem consistency through scirs2-core abstractions and zero-warning code quality.

🚀 Production Features

Core Graph Types

Standard Graphs: Efficient directed and undirected graph implementations
Specialized Graphs: Bipartite, multi-graphs with parallel edges, hypergraphs
Temporal Graphs: Time-based graph operations and analysis
Attributed Graphs: Rich metadata support with flexible attribute systems

Comprehensive Algorithm Suite (90+ algorithms implemented)

Graph Traversal & Search

Breadth-first search (BFS), Depth-first search (DFS)
Bidirectional search, Priority-first search, A* pathfinding

Shortest Paths & Connectivity

Dijkstra, Floyd-Warshall, k-shortest paths algorithms
Connected components, strongly connected components
Articulation points, bridges, topological sorting

Network Flow & Matching

Maximum flow (Ford-Fulkerson, Dinic, push-relabel)
Minimum cut algorithms, bipartite matching
Maximum cardinality matching, stable marriage problem

Centrality & Importance

Degree, betweenness, closeness, eigenvector centrality
PageRank, personalized PageRank, Katz centrality, HITS algorithm

Community Detection

Modularity optimization, Louvain method, label propagation
Infomap algorithm, fluid communities, hierarchical clustering

Graph Analytics

Spectral clustering, Laplacian matrix operations
Graph isomorphism (VF2 algorithm), subgraph matching
Motif detection (triangles, cliques, stars), k-core decomposition

Performance & Scale

Multi-threaded: Rayon-powered parallel processing for large graphs
Memory Efficient: Multiple graph representations optimized for different use cases
SIMD Accelerated: Optimized numerical operations where applicable
Large Graph Support: Handles graphs with millions of nodes/edges
Compact Formats: CSR, bit-packed, and compressed representations available
Memory Profiling: Built-in tools to analyze and optimize memory usage

Rich I/O Support

Multiple format support with robust parsing:

GraphML, GML, DOT (Graphviz), JSON
Edge lists, Adjacency lists, Matrix Market format
Bidirectional conversion with comprehensive error handling

Installation

Add to your Cargo.toml:

[dependencies]
scirs2-graph = "0.1.5"

For performance features:

[dependencies]
scirs2-graph = { version = "0.1.5", features = ["parallel"] }

Quick Start

Basic Graph Operations

use scirs2_graph::{Graph, algorithms, measures};
use scirs2_core::error::CoreResult;

fn main() -> CoreResult<()> {
    // Create and populate graph
    let mut graph = Graph::new();
    graph.add_node(1);
    graph.add_node(2); 
    graph.add_node(3);
    graph.add_edge(1, 2, 1.0)?;
    graph.add_edge(2, 3, 2.0)?;
    graph.add_edge(1, 3, 3.0)?;

    // Graph analysis
    println!("Nodes: {}, Edges: {}", graph.node_count(), graph.edge_count());
    
    // Shortest path
    let path = algorithms::shortest_path(&graph, 1, 3)?;
    println!("Shortest path 1→3: {:?}", path);
    
    // Centrality analysis
    let centrality = measures::centrality::degree_centrality(&graph)?;
    println!("Degree centrality: {:?}", centrality);
    
    Ok(())
}

Advanced Analytics

use scirs2_graph::{algorithms, spectral, generators};

fn advanced_analysis() -> CoreResult<()> {
    // Generate test network
    let graph = generators::barabasi_albert_graph(100, 3)?;
    
    // Community detection
    let communities = algorithms::louvain_communities(&graph)?;
    println!("Found {} communities", communities.len());
    
    // Spectral clustering  
    let adj_matrix = graph.adjacency_matrix();
    let clusters = spectral::spectral_clustering(&adj_matrix, 5, None, None)?;
    
    // Centrality analysis
    let pagerank = algorithms::pagerank(&graph, 0.85, None)?;
    let betweenness = algorithms::betweenness_centrality(&graph)?;
    
    Ok(())
}

Graph I/O Operations

use scirs2_graph::io;

fn graph_io_example() -> CoreResult<()> {
    // Read from various formats
    let graph1 = io::read_graphml("network.graphml")?;
    let graph2 = io::read_gml("network.gml")?;
    let graph3 = io::read_edgelist("edges.txt", false)?;
    
    // Write to different formats
    io::write_dot(&graph1, "output.dot")?;
    io::write_json(&graph1, "output.json")?;
    
    Ok(())
}

API Overview

Core Modules

use scirs2_graph::{
    // Graph types
    Graph, DiGraph, BipartiteGraph, Hypergraph, TemporalGraph,
    
    // Algorithms by category
    algorithms::{
        shortest_path::dijkstra,
        connectivity::connected_components,
        community::louvain_communities,
        centrality::pagerank,
        flow::dinic_max_flow,
        matching::maximum_bipartite_matching,
    },
    
    // Graph measures
    measures::{
        degree_centrality,
        clustering_coefficient, 
        graph_density,
    },
    
    // Spectral methods
    spectral::{
        laplacian_matrix,
        spectral_clustering,
        normalized_cut,
    },
    
    // Graph generation
    generators::{
        erdos_renyi_graph,
        barabasi_albert_graph,
        watts_strogatz_graph,
    },
    
    // I/O operations
    io::{
        read_graphml, write_graphml,
        read_gml, write_gml,
        read_edgelist, write_edgelist,
    },
};

Documentation

Algorithm Complexity Reference: Comprehensive time and space complexity for all algorithms
Extended Usage Examples: Complete examples for common graph workflows
NetworkX Migration Guide: Step-by-step guide for migrating from NetworkX
Memory Optimization Guide: Techniques for handling very large graphs efficiently
Stress Testing Guide: Testing with graphs >1M nodes
Numerical Accuracy Report: Validation against reference implementations
Performance Benchmarks: Benchmark suite and comparison with NetworkX
API Documentation: Full API docs available at docs.rs/scirs2-graph

Performance

This library is designed for production use with:

High Performance: Competitive with NetworkX and igraph
Memory Efficiency: Optimized data structures for large graphs
Parallel Processing: Multi-threaded algorithms scale with available cores
Test Coverage: 269+ unit tests ensuring reliability

Compatibility

SciPy Compatibility: API designed to match SciPy's graph functionality where possible
NetworkX Migration: Similar interface patterns for easy migration
Rust Ecosystem: Integrates well with ndarray, rayon, and other scientific Rust crates

Testing & Validation

Unit Tests: 269+ tests ensuring correctness
Numerical Validation: Verified against NetworkX reference implementation
Stress Tests: Validated with graphs up to 5M nodes
Memory Profiling: Optimized representations for different graph types
Performance Benchmarks: 10-50x faster than NetworkX for most operations

Run validation suite:

cd tests
./run_validation.sh

Project Status

✅ Production Ready: Comprehensive feature set with extensive testing
✅ API Stable: Stable Release with stable public interface
✅ Well Documented: Complete API documentation with examples
✅ Performance Optimized: Benchmarked and optimized for real-world use
✅ Numerically Validated: Accuracy verified against reference implementations

Next: Version 1.0 release with additional performance optimizations and extended documentation.

Contributing

See the project root CLAUDE.md for development guidelines and contribution instructions.

License

This project is Licensed under the Apache License 2.0. See LICENSE for details.

See the LICENSE file for details.

scirs2-graph 0.1.5