problemreductions/models/graph/
directed_two_commodity_integral_flow.rs

1//! Directed Two-Commodity Integral Flow problem implementation.
2//!
3//! Given a directed graph with arc capacities and two source-sink pairs with
4//! flow requirements, determine whether two integral flow functions exist that
5//! jointly satisfy capacity, conservation, and requirement constraints.
6//!
7//! NP-complete even with unit capacities (Even, Itai, and Shamir, 1976).
8
9use crate::registry::{FieldInfo, ProblemSchemaEntry};
10use crate::topology::DirectedGraph;
11use crate::traits::Problem;
12use serde::{Deserialize, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "DirectedTwoCommodityIntegralFlow",
17        display_name: "Directed Two-Commodity Integral Flow",
18        aliases: &["D2CIF"],
19        dimensions: &[],
20        module_path: module_path!(),
21        description: "Two-commodity integral flow feasibility on a directed graph",
22        fields: &[
23            FieldInfo { name: "graph", type_name: "DirectedGraph", description: "Directed graph G = (V, A)" },
24            FieldInfo { name: "capacities", type_name: "Vec<u64>", description: "Capacity c(a) for each arc" },
25            FieldInfo { name: "source_1", type_name: "usize", description: "Source vertex s_1 for commodity 1" },
26            FieldInfo { name: "sink_1", type_name: "usize", description: "Sink vertex t_1 for commodity 1" },
27            FieldInfo { name: "source_2", type_name: "usize", description: "Source vertex s_2 for commodity 2" },
28            FieldInfo { name: "sink_2", type_name: "usize", description: "Sink vertex t_2 for commodity 2" },
29            FieldInfo { name: "requirement_1", type_name: "u64", description: "Flow requirement R_1 for commodity 1" },
30            FieldInfo { name: "requirement_2", type_name: "u64", description: "Flow requirement R_2 for commodity 2" },
31        ],
32    }
33}
34
35/// Directed Two-Commodity Integral Flow problem.
36///
37/// Given a directed graph G = (V, A) with arc capacities c(a), two source-sink
38/// pairs (s_1, t_1) and (s_2, t_2), and requirements R_1, R_2, determine
39/// whether two integral flow functions f_1, f_2: A -> Z_0^+ exist such that:
40/// 1. Joint capacity: f_1(a) + f_2(a) <= c(a) for all a in A
41/// 2. Flow conservation: for each commodity i, flow is conserved at every
42///    vertex except its own source and sink
43/// 3. Requirements: net flow into t_i under f_i is at least R_i
44///
45/// # Variables
46///
47/// 2|A| variables: first |A| for commodity 1's flow on each arc,
48/// next |A| for commodity 2's flow on each arc. Variable j for arc a
49/// of commodity i ranges over {0, ..., c(a)}.
50///
51/// # Example
52///
53/// ```
54/// use problemreductions::models::graph::DirectedTwoCommodityIntegralFlow;
55/// use problemreductions::topology::DirectedGraph;
56/// use problemreductions::{Problem, Solver, BruteForce};
57///
58/// // 6-vertex network: s1=0, s2=1, t1=4, t2=5
59/// let graph = DirectedGraph::new(6, vec![
60///     (0, 2), (0, 3), (1, 2), (1, 3),
61///     (2, 4), (2, 5), (3, 4), (3, 5),
62/// ]);
63/// let problem = DirectedTwoCommodityIntegralFlow::new(
64///     graph, vec![1; 8], 0, 4, 1, 5, 1, 1,
65/// );
66/// let solver = BruteForce::new();
67/// assert!(solver.find_witness(&problem).is_some());
68/// ```
69#[derive(Debug, Clone, Serialize, Deserialize)]
70pub struct DirectedTwoCommodityIntegralFlow {
71    /// The directed graph G = (V, A).
72    graph: DirectedGraph,
73    /// Capacity c(a) for each arc.
74    capacities: Vec<u64>,
75    /// Source vertex s_1 for commodity 1.
76    source_1: usize,
77    /// Sink vertex t_1 for commodity 1.
78    sink_1: usize,
79    /// Source vertex s_2 for commodity 2.
80    source_2: usize,
81    /// Sink vertex t_2 for commodity 2.
82    sink_2: usize,
83    /// Flow requirement R_1 for commodity 1.
84    requirement_1: u64,
85    /// Flow requirement R_2 for commodity 2.
86    requirement_2: u64,
87}
88
89impl DirectedTwoCommodityIntegralFlow {
90    /// Create a new Directed Two-Commodity Integral Flow problem.
91    ///
92    /// # Panics
93    ///
94    /// Panics if:
95    /// - `capacities.len() != graph.num_arcs()`
96    /// - Any terminal vertex index >= `graph.num_vertices()`
97    #[allow(clippy::too_many_arguments)]
98    pub fn new(
99        graph: DirectedGraph,
100        capacities: Vec<u64>,
101        source_1: usize,
102        sink_1: usize,
103        source_2: usize,
104        sink_2: usize,
105        requirement_1: u64,
106        requirement_2: u64,
107    ) -> Self {
108        let n = graph.num_vertices();
109        assert_eq!(
110            capacities.len(),
111            graph.num_arcs(),
112            "capacities length must match graph num_arcs"
113        );
114        assert!(source_1 < n, "source_1 ({source_1}) >= num_vertices ({n})");
115        assert!(sink_1 < n, "sink_1 ({sink_1}) >= num_vertices ({n})");
116        assert!(source_2 < n, "source_2 ({source_2}) >= num_vertices ({n})");
117        assert!(sink_2 < n, "sink_2 ({sink_2}) >= num_vertices ({n})");
118        Self {
119            graph,
120            capacities,
121            source_1,
122            sink_1,
123            source_2,
124            sink_2,
125            requirement_1,
126            requirement_2,
127        }
128    }
129
130    /// Get a reference to the underlying directed graph.
131    pub fn graph(&self) -> &DirectedGraph {
132        &self.graph
133    }
134
135    /// Get a reference to the capacities.
136    pub fn capacities(&self) -> &[u64] {
137        &self.capacities
138    }
139
140    /// Get source vertex for commodity 1.
141    pub fn source_1(&self) -> usize {
142        self.source_1
143    }
144
145    /// Get sink vertex for commodity 1.
146    pub fn sink_1(&self) -> usize {
147        self.sink_1
148    }
149
150    /// Get source vertex for commodity 2.
151    pub fn source_2(&self) -> usize {
152        self.source_2
153    }
154
155    /// Get sink vertex for commodity 2.
156    pub fn sink_2(&self) -> usize {
157        self.sink_2
158    }
159
160    /// Get requirement for commodity 1.
161    pub fn requirement_1(&self) -> u64 {
162        self.requirement_1
163    }
164
165    /// Get requirement for commodity 2.
166    pub fn requirement_2(&self) -> u64 {
167        self.requirement_2
168    }
169
170    /// Get the number of vertices.
171    pub fn num_vertices(&self) -> usize {
172        self.graph.num_vertices()
173    }
174
175    /// Get the number of arcs.
176    pub fn num_arcs(&self) -> usize {
177        self.graph.num_arcs()
178    }
179
180    /// Get the maximum capacity across all arcs.
181    pub fn max_capacity(&self) -> u64 {
182        self.capacities.iter().copied().max().unwrap_or(0)
183    }
184
185    /// Check whether a flow assignment is feasible.
186    ///
187    /// `config` has 2*|A| entries: first |A| for commodity 1, next |A| for commodity 2.
188    pub fn is_feasible(&self, config: &[usize]) -> bool {
189        let m = self.graph.num_arcs();
190        if config.len() != 2 * m {
191            return false;
192        }
193        let arcs = self.graph.arcs();
194        // (1) Joint capacity constraint
195        for a in 0..m {
196            let f1 = config[a] as u64;
197            let f2 = config[m + a] as u64;
198            if f1 + f2 > self.capacities[a] {
199                return false;
200            }
201        }
202
203        // (2) Flow conservation for each commodity at non-terminal vertices
204        let n = self.graph.num_vertices();
205        let mut balances = [vec![0_i128; n], vec![0_i128; n]];
206        for (a, &(u, w)) in arcs.iter().enumerate() {
207            let flow_1 = config[a] as i128;
208            let flow_2 = config[m + a] as i128;
209
210            balances[0][u] -= flow_1;
211            balances[0][w] += flow_1;
212            balances[1][u] -= flow_2;
213            balances[1][w] += flow_2;
214        }
215
216        for (commodity, commodity_balances) in balances.iter().enumerate() {
217            let src = if commodity == 0 {
218                self.source_1
219            } else {
220                self.source_2
221            };
222            for (v, &balance) in commodity_balances.iter().enumerate() {
223                let snk = if commodity == 0 {
224                    self.sink_1
225                } else {
226                    self.sink_2
227                };
228                if v != src && v != snk && balance != 0 {
229                    return false;
230                }
231            }
232
233            let snk = if commodity == 0 {
234                self.sink_1
235            } else {
236                self.sink_2
237            };
238            let req = if commodity == 0 {
239                self.requirement_1
240            } else {
241                self.requirement_2
242            };
243
244            if commodity_balances[snk] < i128::from(req) {
245                return false;
246            }
247        }
248
249        true
250    }
251}
252
253impl Problem for DirectedTwoCommodityIntegralFlow {
254    const NAME: &'static str = "DirectedTwoCommodityIntegralFlow";
255    type Value = crate::types::Or;
256
257    fn dims(&self) -> Vec<usize> {
258        self.capacities
259            .iter()
260            .chain(self.capacities.iter())
261            .map(|&c| (c as usize) + 1)
262            .collect()
263    }
264
265    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
266        crate::types::Or(self.is_feasible(config))
267    }
268
269    fn variant() -> Vec<(&'static str, &'static str)> {
270        crate::variant_params![]
271    }
272}
273
274crate::declare_variants! {
275    default DirectedTwoCommodityIntegralFlow => "(max_capacity + 1)^(2 * num_arcs)",
276}
277
278#[cfg(feature = "example-db")]
279pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
280    vec![crate::example_db::specs::ModelExampleSpec {
281        id: "directed_two_commodity_integral_flow",
282        instance: Box::new(DirectedTwoCommodityIntegralFlow::new(
283            DirectedGraph::new(
284                6,
285                vec![
286                    (0, 2),
287                    (0, 3),
288                    (1, 2),
289                    (1, 3),
290                    (2, 4),
291                    (2, 5),
292                    (3, 4),
293                    (3, 5),
294                ],
295            ),
296            vec![1; 8],
297            0,
298            4,
299            1,
300            5,
301            1,
302            1,
303        )),
304        optimal_config: vec![1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
305        optimal_value: serde_json::json!(true),
306    }]
307}
308
309#[cfg(test)]
310#[path = "../../unit_tests/models/graph/directed_two_commodity_integral_flow.rs"]
311mod tests;
problemreductions/models/graph/directed_two_commodity_integral_flow.rs

problemreductions/models/graph/
directed_two_commodity_integral_flow.rs
