SciRS2 Graph

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

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.0"

For performance features:

[dependencies]
scirs2-graph = { version = "0.1.0", 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 dual-licensed under:

• MIT License
• Apache License Version 2.0

See the LICENSE file for details.