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.