tide-maxflow 0.1.0

//! Randomized correctness test: compare Tide vs rs-graph Dinic
//! on thousands of random graphs.

use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
use rs_graph::linkedlistgraph::LinkedListGraph;
use rs_graph::maxflow::dinic;
use rs_graph::{Buildable, Builder};
use tide_maxflow::{max_flow, max_flow_adaptive, max_flow_hybrid};

/// Generate a random graph with `n` vertices, edge probability `p`,
/// and capacities in [1, max_cap]. No parallel edges.
fn random_graph(rng: &mut StdRng, n: usize, p: f64, max_cap: i64) -> Vec<(usize, usize, i64)> {
    let mut edges = Vec::new();
    for u in 0..n {
        for v in 0..n {
            if u != v && rng.gen::<f64>() < p {
                let cap = rng.gen_range(1..=max_cap);
                edges.push((u, v, cap));
            }
        }
    }
    edges
}

/// Compute max flow using rs-graph's Dinic as reference.
fn rs_graph_dinic(n: usize, source: usize, sink: usize, edges: &[(usize, usize, i64)]) -> i64 {
    let mut builder = LinkedListGraph::<usize>::new_builder();
    let nodes: Vec<_> = (0..n).map(|_| builder.add_node()).collect();
    let mut caps = Vec::new();
    for &(u, v, cap) in edges {
        let e = builder.add_edge(nodes[u], nodes[v]);
        caps.push((e, cap));
    }
    let graph = builder.into_graph();
    let cap_map: std::collections::HashMap<_, _> = caps.into_iter().collect();
    let (flow, _, _) = dinic(&graph, nodes[source], nodes[sink], |e| {
        *cap_map.get(&e).unwrap_or(&0)
    });
    flow
}

#[test]
fn test_random_sparse_graphs() {
    let mut rng = StdRng::seed_from_u64(42);
    let total = 10_000;

    for i in 0..total {
        let n = rng.gen_range(4..=30);
        let p = rng.gen_range(0.05..0.5);
        let max_cap = rng.gen_range(1..=1000);
        let source = 0;
        let sink = n - 1;

        let edges = random_graph(&mut rng, n, p, max_cap);

        let tide_result = max_flow(n, source, sink, &edges).flow;
        let dinic_flow = rs_graph_dinic(n, source, sink, &edges);

        assert_eq!(
            tide_result,
            dinic_flow,
            "Sparse mismatch #{}: n={}, |E|={}, tide={}, dinic={}",
            i,
            n,
            edges.len(),
            tide_result,
            dinic_flow
        );
    }

    eprintln!("{}/{} sparse random graphs passed", total, total);
}

#[test]
fn test_random_dense_graphs() {
    let mut rng = StdRng::seed_from_u64(123);
    let total = 1_000;

    for i in 0..total {
        let n = rng.gen_range(4..=20);
        let p = rng.gen_range(0.5..1.0);
        let max_cap = rng.gen_range(1..=10000);
        let source = 0;
        let sink = n - 1;

        let edges = random_graph(&mut rng, n, p, max_cap);

        let tide_result = max_flow(n, source, sink, &edges).flow;
        let dinic_flow = rs_graph_dinic(n, source, sink, &edges);

        assert_eq!(
            tide_result,
            dinic_flow,
            "Dense mismatch #{}: n={}, |E|={}, tide={}, dinic={}",
            i,
            n,
            edges.len(),
            tide_result,
            dinic_flow
        );
    }

    eprintln!("{}/{} dense random graphs passed", total, total);
}

#[test]
fn test_random_layered_graphs() {
    let mut rng = StdRng::seed_from_u64(456);
    let total = 1_000;

    for i in 0..total {
        let layers = rng.gen_range(2..=8);
        let width = rng.gen_range(2..=8);
        let max_cap = rng.gen_range(1..=100);
        let n = layers * width + 2;
        let source = 0;
        let sink = n - 1;

        let mut edges = Vec::new();
        let mut seen = std::collections::HashSet::new();

        // Source to first layer
        for w in 0..width {
            let cap = rng.gen_range(1..=max_cap);
            if seen.insert((source, 1 + w)) {
                edges.push((source, 1 + w, cap));
            }
        }
        // Inter-layer
        for l in 0..layers - 1 {
            for w in 0..width {
                let u = 1 + l * width + w;
                let num_conn = rng.gen_range(1..=width.min(3));
                for _ in 0..num_conn {
                    let w2 = rng.gen_range(0..width);
                    let v = 1 + (l + 1) * width + w2;
                    let cap = rng.gen_range(1..=max_cap);
                    if seen.insert((u, v)) {
                        edges.push((u, v, cap));
                    }
                }
            }
        }
        // Last layer to sink
        for w in 0..width {
            let u = 1 + (layers - 1) * width + w;
            let cap = rng.gen_range(1..=max_cap);
            if seen.insert((u, sink)) {
                edges.push((u, sink, cap));
            }
        }

        let tide_result = max_flow(n, source, sink, &edges).flow;
        let dinic_flow = rs_graph_dinic(n, source, sink, &edges);

        assert_eq!(
            tide_result,
            dinic_flow,
            "Layered mismatch #{}: layers={}, width={}, |E|={}, tide={}, dinic={}",
            i,
            layers,
            width,
            edges.len(),
            tide_result,
            dinic_flow
        );
    }

    eprintln!("{}/{} random layered graphs passed", total, total);
}

#[test]
fn test_hybrid_vs_standard() {
    use std::time::Instant;
    let mut rng = StdRng::seed_from_u64(789);
    let total = 5_000;

    for i in 0..total {
        let n = rng.gen_range(4..=30);
        let p = rng.gen_range(0.05..1.0);
        let max_cap = rng.gen_range(1..=10000);
        let source = 0;
        let sink = n - 1;

        let edges = random_graph(&mut rng, n, p, max_cap);

        let standard = max_flow(n, source, sink, &edges);

        let t0 = Instant::now();
        let hybrid = max_flow_hybrid(n, source, sink, &edges);
        let elapsed = t0.elapsed();

        if elapsed.as_millis() > 2000 {
            eprintln!(
                "SLOW graph #{}: n={}, |E|={}, p={:.2}, max_cap={}, took {:.1}s, std_steps={}, hyb_steps={}",
                i, n, edges.len(), p, max_cap, elapsed.as_secs_f64(),
                standard.steps, hybrid.steps
            );
        }

        assert_eq!(
            standard.flow,
            hybrid.flow,
            "Hybrid mismatch #{}: n={}, |E|={}, standard={}, hybrid={}",
            i,
            n,
            edges.len(),
            standard.flow,
            hybrid.flow
        );

        if (i + 1) % 500 == 0 {
            eprintln!("{}/{} hybrid vs standard passed", i + 1, total);
        }
    }

    eprintln!(
        "{}/{} hybrid vs standard random graphs passed",
        total, total
    );
}

#[test]
fn test_adaptive_vs_standard() {
    let mut rng = StdRng::seed_from_u64(101);
    let total = 5_000;

    for i in 0..total {
        let n = rng.gen_range(4..=30);
        let p = rng.gen_range(0.05..1.0);
        let max_cap = rng.gen_range(1..=10000);
        let source = 0;
        let sink = n - 1;

        let edges = random_graph(&mut rng, n, p, max_cap);

        let standard = max_flow(n, source, sink, &edges).flow;
        let adaptive = max_flow_adaptive(n, source, sink, &edges).flow;

        assert_eq!(
            standard,
            adaptive,
            "Adaptive mismatch #{}: n={}, |E|={}, standard={}, adaptive={}",
            i,
            n,
            edges.len(),
            standard,
            adaptive
        );

        if (i + 1) % 500 == 0 {
            eprintln!("{}/{} adaptive vs standard passed", i + 1, total);
        }
    }

    eprintln!(
        "{}/{} adaptive vs standard random graphs passed",
        total, total
    );
}