converge_optimization/packs/network_flow/
solver.rs

1//! Solver for Network Flow pack
2//!
3//! Delegates to `crate::graph::flow::min_cost_flow` (Successive Shortest Paths
4//! with Bellman-Ford) for the actual computation.
5
6use super::types::*;
7use crate::graph::flow::{FlowNetwork, MinCostFlowProblem, min_cost_flow};
8use converge_pack::gate::GateResult as Result;
9use converge_pack::gate::{ProblemSpec, ReplayEnvelope, SolverReport, StopReason};
10
11/// Min-cost flow solver delegating to `crate::graph::flow`
12pub struct MinCostFlowSolver;
13
14impl MinCostFlowSolver {
15    pub fn solve(
16        &self,
17        input: &NetworkFlowInput,
18        spec: &ProblemSpec,
19    ) -> Result<(NetworkFlowOutput, SolverReport)> {
20        // Scale f64 costs/capacities to i64 (multiply by 1000 for 3 decimal places)
21        let scale = 1000i64;
22
23        let mut network = FlowNetwork::new(input.nodes);
24        for edge in &input.edges {
25            let cap = (edge.capacity * scale as f64).round() as i64;
26            let cost = (edge.cost * scale as f64).round() as i64;
27            network.add_edge(edge.from, edge.to, cap, cost);
28        }
29
30        let demand = (input.demand * scale as f64).round() as i64;
31        let problem = MinCostFlowProblem::source_sink(network, input.source, input.sink, demand)
32            .map_err(|e| converge_pack::GateError::invalid_input(e.to_string()))?;
33
34        match min_cost_flow(&problem) {
35            Ok(result) => {
36                // Convert flows back to f64
37                let flows: Vec<f64> = result
38                    .edge_flows
39                    .iter()
40                    .map(|&f| f as f64 / scale as f64)
41                    .collect();
42                let total_flow = result.flow as f64 / scale as f64;
43                // Cost was scaled twice (flow * cost), so divide by scale²
44                let total_cost = result.cost as f64 / (scale as f64 * scale as f64);
45
46                let output = NetworkFlowOutput {
47                    flows,
48                    total_cost,
49                    total_flow,
50                };
51
52                let replay = ReplayEnvelope::minimal(spec.seed());
53                let report = if total_flow >= input.demand - 1e-9 {
54                    SolverReport::optimal("min-cost-flow-v1", total_cost, replay)
55                } else {
56                    SolverReport::infeasible(
57                        "min-cost-flow-v1",
58                        vec![],
59                        StopReason::NoFeasible,
60                        replay,
61                    )
62                };
63
64                Ok((output, report))
65            }
66            Err(_) => {
67                let replay = ReplayEnvelope::minimal(spec.seed());
68                let report = SolverReport::infeasible(
69                    "min-cost-flow-v1",
70                    vec![],
71                    StopReason::NoFeasible,
72                    replay,
73                );
74                let output = NetworkFlowOutput {
75                    flows: vec![0.0; input.edges.len()],
76                    total_cost: 0.0,
77                    total_flow: 0.0,
78                };
79                Ok((output, report))
80            }
81        }
82    }
83}
converge_optimization/packs/network_flow/solver.rs

converge_optimization/packs/network_flow/
solver.rs
