View on GitHub

netoptim-rs

🌊 Network Flow Optimization in Rust

🌊 netoptim-rs

Crates.io Docs.rs CI codecov

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

📋 Features

🚀 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

🏃 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
cargo test

# Run tests with output
cargo test -- --nocapture

# Run specific test
cargo test test_dijkstra_simple

📊 Running Benchmarks

The library includes benchmarks using criterion:

# Run all benchmarks
cargo bench

# Run specific benchmark
cargo bench diijkstra_sparse

🔧 Features

Default Features

No features are enabled by default.

Optional Features

🎯 Use Cases

📈 Performance Characteristics

Algorithm Time Complexity Space Complexity Notes
Bellman-Ford O(VE) O(V) Handles negative weights
Dijkstra O(E + V log V) O(V) Requires non-negative weights
Howard’s Algorithm O(V³) worst case O(V) Fast in practice for negative cycles
Parametric Solver O(k · V³) O(V) k = number of iterations

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

at your option.

🙏 Acknowledgments

📚 References

🗺️ Roadmap

💬 Support

Made with ❤️ in Rust