problemreductions/models/graph/

directed_two_commodity_integral_flow.rs

//! Directed Two-Commodity Integral Flow problem implementation.
//!
//! Given a directed graph with arc capacities and two source-sink pairs with
//! flow requirements, determine whether two integral flow functions exist that
//! jointly satisfy capacity, conservation, and requirement constraints.
//!
//! NP-complete even with unit capacities (Even, Itai, and Shamir, 1976).

use crate::registry::{FieldInfo, ProblemSchemaEntry};
use crate::topology::DirectedGraph;
use crate::traits::Problem;
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "DirectedTwoCommodityIntegralFlow",
        display_name: "Directed Two-Commodity Integral Flow",
        aliases: &["D2CIF"],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Graph,
        module_path: module_path!(),
        description: "Two-commodity integral flow feasibility on a directed graph",
        fields: &[
            FieldInfo { name: "graph", type_name: "DirectedGraph", description: "Directed graph G = (V, A)" },
            FieldInfo { name: "capacities", type_name: "Vec<i64>", description: "Capacity c(a) for each arc" },
            FieldInfo { name: "source_1", type_name: "usize", description: "Source vertex s_1 for commodity 1" },
            FieldInfo { name: "sink_1", type_name: "usize", description: "Sink vertex t_1 for commodity 1" },
            FieldInfo { name: "source_2", type_name: "usize", description: "Source vertex s_2 for commodity 2" },
            FieldInfo { name: "sink_2", type_name: "usize", description: "Sink vertex t_2 for commodity 2" },
            FieldInfo { name: "requirement_1", type_name: "i64", description: "Flow requirement R_1 for commodity 1" },
            FieldInfo { name: "requirement_2", type_name: "i64", description: "Flow requirement R_2 for commodity 2" },
        ],
    }
}

/// Directed Two-Commodity Integral Flow problem.
///
/// Given a directed graph G = (V, A) with arc capacities c(a), two source-sink
/// pairs (s_1, t_1) and (s_2, t_2), and requirements R_1, R_2, determine
/// whether two integral flow functions f_1, f_2: A -> Z_0^+ exist such that:
/// 1. Joint capacity: f_1(a) + f_2(a) <= c(a) for all a in A
/// 2. Flow conservation: for each commodity i, flow is conserved at every
///    vertex except its own source and sink
/// 3. Requirements: net flow into t_i under f_i is at least R_i
///
/// # Variables
///
/// 2|A| variables: first |A| for commodity 1's flow on each arc,
/// next |A| for commodity 2's flow on each arc. Variable j for arc a
/// of commodity i ranges over {0, ..., c(a)}.
///
/// # Example
///
/// ```
/// use problemreductions::models::graph::DirectedTwoCommodityIntegralFlow;
/// use problemreductions::topology::DirectedGraph;
/// use problemreductions::{Problem, BruteForce};
///
/// // 6-vertex network: s1=0, s2=1, t1=4, t2=5
/// let graph = DirectedGraph::new(6, vec![
///     (0, 2), (0, 3), (1, 2), (1, 3),
///     (2, 4), (2, 5), (3, 4), (3, 5),
/// ]);
/// let problem = DirectedTwoCommodityIntegralFlow::new(
///     graph, vec![1; 8], 0, 4, 1, 5, 1, 1,
/// );
/// let solver = BruteForce::new();
/// assert!(solver.solve(&problem).unwrap().is_some());
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(try_from = "DirectedTwoCommodityIntegralFlowData")]
pub struct DirectedTwoCommodityIntegralFlow {
    /// The directed graph G = (V, A).
    graph: DirectedGraph,
    /// Capacity c(a) for each arc.
    capacities: Vec<i64>,
    /// Source vertex s_1 for commodity 1.
    source_1: usize,
    /// Sink vertex t_1 for commodity 1.
    sink_1: usize,
    /// Source vertex s_2 for commodity 2.
    source_2: usize,
    /// Sink vertex t_2 for commodity 2.
    sink_2: usize,
    /// Flow requirement R_1 for commodity 1.
    requirement_1: i64,
    /// Flow requirement R_2 for commodity 2.
    requirement_2: i64,
}

#[derive(Deserialize)]
struct DirectedTwoCommodityIntegralFlowData {
    graph: DirectedGraph,
    capacities: Vec<i64>,
    source_1: usize,
    sink_1: usize,
    source_2: usize,
    sink_2: usize,
    requirement_1: i64,
    requirement_2: i64,
}

impl TryFrom<DirectedTwoCommodityIntegralFlowData> for DirectedTwoCommodityIntegralFlow {
    type Error = crate::registry::ConstructionError;
    fn try_from(data: DirectedTwoCommodityIntegralFlowData) -> Result<Self, Self::Error> {
        Self::try_new(
            data.graph,
            data.capacities,
            data.source_1,
            data.sink_1,
            data.source_2,
            data.sink_2,
            data.requirement_1,
            data.requirement_2,
        )
    }
}

impl DirectedTwoCommodityIntegralFlow {
    /// Create a new Directed Two-Commodity Integral Flow problem.
    ///
    /// # Panics
    ///
    /// Panics if:
    /// - `capacities.len() != graph.num_arcs()`
    /// - Any terminal vertex index >= `graph.num_vertices()`
    #[allow(clippy::too_many_arguments)]
    pub fn new(
        graph: DirectedGraph,
        capacities: Vec<i64>,
        source_1: usize,
        sink_1: usize,
        source_2: usize,
        sink_2: usize,
        requirement_1: i64,
        requirement_2: i64,
    ) -> Self {
        Self::try_new(
            graph,
            capacities,
            source_1,
            sink_1,
            source_2,
            sink_2,
            requirement_1,
            requirement_2,
        )
        .unwrap_or_else(|error| panic!("{error}"))
    }

    #[allow(clippy::too_many_arguments)]
    fn try_new(
        graph: DirectedGraph,
        capacities: Vec<i64>,
        source_1: usize,
        sink_1: usize,
        source_2: usize,
        sink_2: usize,
        requirement_1: i64,
        requirement_2: i64,
    ) -> Result<Self, crate::registry::ConstructionError> {
        let n = graph.num_vertices();
        if capacities.len() != graph.num_arcs() {
            return Err(crate::registry::ConstructionError::length_mismatch(
                "capacities",
                capacities.len(),
                graph.num_arcs(),
            ));
        }
        if capacities.iter().any(|&capacity| capacity < 0) {
            return Err("capacities must be nonnegative".into());
        }
        if requirement_1 < 0 || requirement_2 < 0 {
            return Err("flow requirements must be nonnegative".into());
        }
        if source_1 >= n {
            return Err(format!("source_1 ({source_1}) >= num_vertices ({n})").into());
        }
        if sink_1 >= n {
            return Err(format!("sink_1 ({sink_1}) >= num_vertices ({n})").into());
        }
        if source_2 >= n {
            return Err(format!("source_2 ({source_2}) >= num_vertices ({n})").into());
        }
        if sink_2 >= n {
            return Err(format!("sink_2 ({sink_2}) >= num_vertices ({n})").into());
        }
        Ok(Self {
            graph,
            capacities,
            source_1,
            sink_1,
            source_2,
            sink_2,
            requirement_1,
            requirement_2,
        })
    }

    /// Get a reference to the underlying directed graph.
    pub fn graph(&self) -> &DirectedGraph {
        &self.graph
    }

    /// Get a reference to the capacities.
    pub fn capacities(&self) -> &[i64] {
        &self.capacities
    }

    /// Get source vertex for commodity 1.
    pub fn source_1(&self) -> usize {
        self.source_1
    }

    /// Get sink vertex for commodity 1.
    pub fn sink_1(&self) -> usize {
        self.sink_1
    }

    /// Get source vertex for commodity 2.
    pub fn source_2(&self) -> usize {
        self.source_2
    }

    /// Get sink vertex for commodity 2.
    pub fn sink_2(&self) -> usize {
        self.sink_2
    }

    /// Get requirement for commodity 1.
    pub fn requirement_1(&self) -> i64 {
        self.requirement_1
    }

    /// Get requirement for commodity 2.
    pub fn requirement_2(&self) -> i64 {
        self.requirement_2
    }

    /// Get the number of vertices.
    pub fn num_vertices(&self) -> usize {
        self.graph.num_vertices()
    }

    /// Get the number of arcs.
    pub fn num_arcs(&self) -> usize {
        self.graph.num_arcs()
    }

    /// Get the maximum capacity across all arcs.
    pub fn max_capacity(&self) -> i64 {
        self.capacities.iter().copied().max().unwrap_or(0)
    }

    /// Check whether a flow assignment is feasible.
    ///
    /// `config` has 2*|A| entries: first |A| for commodity 1, next |A| for commodity 2.
    pub fn is_feasible(&self, config: &[usize]) -> Result<bool, crate::traits::EvaluationError> {
        let m = self.graph.num_arcs();
        if config.len() != 2 * m {
            return Ok(false);
        }
        let arcs = self.graph.arcs();
        // (1) Joint capacity constraint
        for a in 0..m {
            let f1 = i64::try_from(config[a]).map_err(|_| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "converting first commodity flow to i64".into(),
                )
            })?;
            let f2 = i64::try_from(config[m + a]).map_err(|_| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "converting second commodity flow to i64".into(),
                )
            })?;
            if f1.checked_add(f2).ok_or_else(|| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "summing two-commodity arc flow".into(),
                )
            })? > self.capacities[a]
            {
                return Ok(false);
            }
        }

        // (2) Flow conservation for each commodity at non-terminal vertices
        let n = self.graph.num_vertices();
        let mut balances = [vec![0_i64; n], vec![0_i64; n]];
        for (a, &(u, w)) in arcs.iter().enumerate() {
            let flow_1 = i64::try_from(config[a]).map_err(|_| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "converting first commodity flow to i64".into(),
                )
            })?;
            let flow_2 = i64::try_from(config[m + a]).map_err(|_| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "converting second commodity flow to i64".into(),
                )
            })?;

            for (commodity, flow) in [(0, flow_1), (1, flow_2)] {
                balances[commodity][u] =
                    balances[commodity][u].checked_sub(flow).ok_or_else(|| {
                        crate::traits::EvaluationError::IntegerOverflow(
                            "subtracting outgoing commodity flow".into(),
                        )
                    })?;
                balances[commodity][w] =
                    balances[commodity][w].checked_add(flow).ok_or_else(|| {
                        crate::traits::EvaluationError::IntegerOverflow(
                            "adding incoming commodity flow".into(),
                        )
                    })?;
            }
        }

        for (commodity, commodity_balances) in balances.iter().enumerate() {
            let src = if commodity == 0 {
                self.source_1
            } else {
                self.source_2
            };
            for (v, &balance) in commodity_balances.iter().enumerate() {
                let snk = if commodity == 0 {
                    self.sink_1
                } else {
                    self.sink_2
                };
                if v != src && v != snk && balance != 0 {
                    return Ok(false);
                }
            }

            let snk = if commodity == 0 {
                self.sink_1
            } else {
                self.sink_2
            };
            let req = if commodity == 0 {
                self.requirement_1
            } else {
                self.requirement_2
            };

            if commodity_balances[snk] < req {
                return Ok(false);
            }
        }

        Ok(true)
    }
}

impl Problem for DirectedTwoCommodityIntegralFlow {
    const NAME: &'static str = "DirectedTwoCommodityIntegralFlow";
    type Solution = Vec<usize>;
    type Value = crate::types::Or;

    crate::problem_parameters![
        ("max_capacity", max_capacity),
        ("num_arcs", num_arcs),
        ("num_vertices", num_vertices),
    ];

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
        if config.len() != 2 * self.graph.num_arcs() {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "two-commodity flow vector length does not match the graph arcs".into(),
            ));
        }
        Ok(crate::types::Or(self.is_feasible(config)?))
    }

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![]
    }
}

impl crate::solvers::BruteForceProblem for DirectedTwoCommodityIntegralFlow {
    fn dimensions(&self) -> Vec<usize> {
        self.capacities
            .iter()
            .chain(self.capacities.iter())
            .map(|&c| (c as usize) + 1)
            .collect()
    }
}

crate::declare_variants! {
    default DirectedTwoCommodityIntegralFlow => "(max_capacity + 1)^(2 * num_arcs)",
}

crate::register_brute_force! {
    DirectedTwoCommodityIntegralFlow,
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "directed_two_commodity_integral_flow",
        instance: Box::new(DirectedTwoCommodityIntegralFlow::new(
            DirectedGraph::new(
                6,
                vec![
                    (0, 2),
                    (0, 3),
                    (1, 2),
                    (1, 3),
                    (2, 4),
                    (2, 5),
                    (3, 4),
                    (3, 5),
                ],
            ),
            vec![1; 8],
            0,
            4,
            1,
            5,
            1,
            1,
        )),
        optimal_config: serde_json::json!(vec![1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]),
        optimal_value: serde_json::json!(true),
    }]
}

#[cfg(test)]
#[path = "../../unit_tests/models/graph/directed_two_commodity_integral_flow.rs"]
mod tests;