🌊 netoptim-rs

A comprehensive Rust library for network optimization algorithms, built on top of the excellent petgraph library.

📋 Features

• Bellman-Ford Algorithm: Shortest paths with negative edge weight support
• Negative Cycle Detection: Efficient detection of negative cycles in directed graphs
• Parametric Optimization: Maximum parametric optimization for ratio-based problems
• Dijkstra's Algorithm: Fast shortest path computation for non-negative weights
• Howard's Algorithm: Polynomial-time negative cycle finding
• Graph Utilities: Comprehensive utilities for graph analysis and manipulation
• Serialization: JSON-based graph serialization and deserialization
• Visualization: DOT format export for Graphviz visualization

🚀 Installation

Add this to your Cargo.toml:

[dependencies]
netoptim-rs = "0.1"

Or install via cargo:

cargo install netoptim-rs

📚 Quick Start

Bellman-Ford Algorithm

use petgraph::Graph;
use petgraph::prelude::*;
use netoptim_rs::bellman_ford;

let mut g = Graph::new();
let a = g.add_node(());
let b = g.add_node(());
let c = g.add_node(());
g.extend_with_edges(&[
    (0, 1, 2.0),
    (1, 2, 1.0),
    (2, 0, -3.0), // Negative edge
]);

match bellman_ford(&g, a) {
    Ok(paths) => {
        println!("Shortest paths: {:?}", paths.distances);
    }
    Err(_) => {
        println!("Negative cycle detected!");
    }
}

Dijkstra's Algorithm

use petgraph::Graph;
use petgraph::prelude::*;
use netoptim_rs::dijkstra::{dijkstra, dijkstra_path};

let mut g = Graph::new();
let a = g.add_node(());
let b = g.add_node(());
let c = g.add_node(());
g.extend_with_edges(&[(0, 1, 2.0), (1, 2, 3.0)]);

// Compute all shortest paths from node A
let result = dijkstra(&g, a).unwrap();
println!("Distances: {:?}", result.distances);

// Find shortest path from A to C
let path = dijkstra_path(&g, a, c);
println!("Path: {:?}", path);

Negative Cycle Detection

use petgraph::graph::DiGraph;
use netoptim_rs::neg_cycle::NegCycleFinder;
use num::rational::Ratio;

let digraph = DiGraph::<(), Ratio<i32>>::from_edges(&[
    (0, 1, Ratio::new(1, 1)),
    (1, 2, Ratio::new(1, 1)),
    (2, 0, Ratio::new(-3, 1)), // Negative cycle
]);

let mut ncf = NegCycleFinder::new(&digraph);
let mut dist = [Ratio::new(0, 1); 3];

if let Some(cycle) = ncf.howard(&mut dist, |e| *e.weight()) {
    println!("Negative cycle found!");
    for edge in cycle {
        println!("  {} -> {}", edge.source().index(), edge.target().index());
    }
}

Parametric Optimization

use petgraph::graph::DiGraph;
use netoptim_rs::parametric::{MaxParametricSolver, ParametricAPI};
use num::rational::Ratio;
use petgraph::graph::EdgeReference;

struct MyParametricAPI;

impl ParametricAPI<(), Ratio<i32>> for MyParametricAPI {
    fn distance(&self, ratio: &Ratio<i32>, edge: &EdgeReference<Ratio<i32>>) -> Ratio<i32> {
        *edge.weight() - *ratio
    }

    fn zero_cancel(&self, cycle: &[EdgeReference<Ratio<i32>>]) -> Ratio<i32> {
        let sum_a: Ratio<i32> = cycle.iter().map(|e| *e.weight()).sum();
        let sum_b = Ratio::new(cycle.len() as i32, 1);
        sum_a / sum_b
    }
}

let digraph = DiGraph::<(), Ratio<i32>>::from_edges(&[
    (0, 1, Ratio::new(1, 1)),
    (1, 2, Ratio::new(1, 1)),
    (2, 0, Ratio::new(-3, 1)),
]);

let mut solver = MaxParametricSolver::new(&digraph, MyParametricAPI);
let mut dist = [Ratio::new(0, 1); 3];
let mut ratio = Ratio::new(0, 1);

let cycle = solver.run(&mut dist, &mut ratio);
println!("Optimal ratio: {}", ratio);

Graph Utilities

use netoptim_rs::utils::*;
use petgraph::Graph;

let g = Graph::<&str, i32>::from_edges(&[
    (0, 1, 5, "A-B"),
    (1, 2, 3, "B-C"),
]);

// Check for cycles
println!("Has cycle: {}", has_cycle(&g));

// Serialize to JSON
let json = serialize_graph(&g).unwrap();
println!("{}", json);

// Export to DOT for visualization
let dot = to_dot(&g);
println!("{}", dot);

📖 API Documentation

The complete API documentation is available on docs.rs.

Main Modules

• bellman_ford: Bellman-Ford shortest path algorithm
• dijkstra: Dijkstra's shortest path algorithm
• neg_cycle: Negative cycle detection using Howard's algorithm
• parametric: Maximum parametric optimization
• utils: Graph utility functions
• error: Error types for the library

🏃 Running Examples

The repository includes several examples demonstrating various features:

# Dijkstra algorithm examples
cargo run --example dijkstra_example

# Negative cycle detection examples
cargo run --example neg_cycle_example

# Graph utilities examples
cargo run --example utils_example

# Find negative cycles
cargo run --example find_negative_cycle

# Property-based tests
cargo run --example quickcheck_tests

🧪 Running Tests

Run the test suite:

# Run all tests (include --all-features for full CI)
cargo test --all-features --workspace

# Run tests with output
cargo test --all-features --workspace -- --nocapture

# Run specific test
cargo test test_dijkstra_simple --all-features

📊 Running Benchmarks

The library includes benchmarks using criterion:

# Run all benchmarks
cargo bench

# Run specific benchmark
cargo bench dijkstra_sparse

🔧 Features

Default Features

std is enabled by default (includes logging support).

Optional Features

• std: Use standard library (enabled by default, includes logging)

🎯 Use Cases

• Network Routing: Finding optimal paths in communication networks
• Transportation Planning: Route optimization for logistics
• Currency Arbitrage: Detecting profitable currency exchange cycles
• Circuit Design: Finding negative cycles in circuit networks
• Game Development: Pathfinding and AI decision-making
• Scientific Computing: Network flow optimization problems

📈 Performance Characteristics

Where V = number of vertices, E = number of edges

🤝 Contributing

Contributions are welcome! Please see CONTRIBUTING.md for guidelines.

Development Setup

# Clone the repository
git clone https://github.com/luk036/netoptim-rs.git
cd netoptim-rs

# Run tests
cargo test

# Run clippy
cargo clippy

# Format code
cargo fmt

# Run benchmarks
cargo bench

📜 License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

🙏 Acknowledgments

• Built on top of the excellent petgraph library
• Inspired by NetworkX and other graph algorithm libraries
• Uses num crate for numerical operations

📚 References

• Cormen, T. H., et al. "Introduction to Algorithms" (3rd ed.)
• Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. "Network Flows"
• Karp, R. M. "A characterization of the minimum cycle mean in a digraph"

🗺️ Roadmap

• Additional shortest path algorithms (Floyd-Warshall, A*)
• Maximum flow algorithms (Edmonds-Karp, Push-Relabel)
• Minimum spanning tree algorithms (Kruskal, Prim)
• Parallel algorithm implementations
• More comprehensive examples and tutorials
• Performance optimizations for large graphs

💬 Support

• 📖 Documentation
• 🐛 Issue Tracker
• 💬 Discussions

Made with ❤️ in Rust