problemreductions/models/graph/
undirected_two_commodity_integral_flow.rs

1//! Undirected two-commodity integral flow problem implementation.
2//!
3//! The problem asks whether two integral commodities can be routed through an
4//! undirected capacitated graph while sharing edge capacities.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "UndirectedTwoCommodityIntegralFlow",
14        display_name: "Undirected Two-Commodity Integral Flow",
15        aliases: &[],
16        dimensions: &[],
17        module_path: module_path!(),
18        description: "Determine whether two integral commodities can satisfy sink demands in an undirected capacitated graph",
19        fields: &[
20            FieldInfo { name: "graph", type_name: "SimpleGraph", description: "Undirected graph G=(V,E)" },
21            FieldInfo { name: "capacities", type_name: "Vec<u64>", description: "Edge capacities c(e) in graph edge order" },
22            FieldInfo { name: "source_1", type_name: "usize", description: "Source vertex s_1 for commodity 1" },
23            FieldInfo { name: "sink_1", type_name: "usize", description: "Sink vertex t_1 for commodity 1" },
24            FieldInfo { name: "source_2", type_name: "usize", description: "Source vertex s_2 for commodity 2" },
25            FieldInfo { name: "sink_2", type_name: "usize", description: "Sink vertex t_2 for commodity 2" },
26            FieldInfo { name: "requirement_1", type_name: "u64", description: "Required net inflow R_1 at sink t_1" },
27            FieldInfo { name: "requirement_2", type_name: "u64", description: "Required net inflow R_2 at sink t_2" },
28        ],
29    }
30}
31
32inventory::submit! {
33    ProblemSizeFieldEntry {
34        name: "UndirectedTwoCommodityIntegralFlow",
35        fields: &["num_vertices", "num_edges", "num_nonterminal_vertices"],
36    }
37}
38
39/// Undirected two-commodity integral flow on a capacitated graph.
40///
41/// For each undirected edge `{u, v}`, a configuration stores four variables in
42/// the graph's edge order:
43/// - `f1(u, v)`
44/// - `f1(v, u)`
45/// - `f2(u, v)`
46/// - `f2(v, u)`
47#[derive(Debug, Clone, Serialize, Deserialize)]
48pub struct UndirectedTwoCommodityIntegralFlow {
49    graph: SimpleGraph,
50    capacities: Vec<u64>,
51    source_1: usize,
52    sink_1: usize,
53    source_2: usize,
54    sink_2: usize,
55    requirement_1: u64,
56    requirement_2: u64,
57}
58
59impl UndirectedTwoCommodityIntegralFlow {
60    #[allow(clippy::too_many_arguments)]
61    pub fn new(
62        graph: SimpleGraph,
63        capacities: Vec<u64>,
64        source_1: usize,
65        sink_1: usize,
66        source_2: usize,
67        sink_2: usize,
68        requirement_1: u64,
69        requirement_2: u64,
70    ) -> Self {
71        assert_eq!(
72            capacities.len(),
73            graph.num_edges(),
74            "capacities length must match graph num_edges"
75        );
76
77        let num_vertices = graph.num_vertices();
78        for (label, vertex) in [
79            ("source_1", source_1),
80            ("sink_1", sink_1),
81            ("source_2", source_2),
82            ("sink_2", sink_2),
83        ] {
84            assert!(
85                vertex < num_vertices,
86                "{label} must be less than num_vertices ({num_vertices})"
87            );
88        }
89
90        for &capacity in &capacities {
91            let domain = usize::try_from(capacity)
92                .ok()
93                .and_then(|value| value.checked_add(1));
94            assert!(
95                domain.is_some(),
96                "edge capacities must fit into usize for dims()"
97            );
98        }
99
100        Self {
101            graph,
102            capacities,
103            source_1,
104            sink_1,
105            source_2,
106            sink_2,
107            requirement_1,
108            requirement_2,
109        }
110    }
111
112    pub fn graph(&self) -> &SimpleGraph {
113        &self.graph
114    }
115
116    pub fn capacities(&self) -> &[u64] {
117        &self.capacities
118    }
119
120    pub fn source_1(&self) -> usize {
121        self.source_1
122    }
123
124    pub fn sink_1(&self) -> usize {
125        self.sink_1
126    }
127
128    pub fn source_2(&self) -> usize {
129        self.source_2
130    }
131
132    pub fn sink_2(&self) -> usize {
133        self.sink_2
134    }
135
136    pub fn requirement_1(&self) -> u64 {
137        self.requirement_1
138    }
139
140    pub fn requirement_2(&self) -> u64 {
141        self.requirement_2
142    }
143
144    pub fn num_vertices(&self) -> usize {
145        self.graph.num_vertices()
146    }
147
148    pub fn num_edges(&self) -> usize {
149        self.graph.num_edges()
150    }
151
152    pub fn num_nonterminal_vertices(&self) -> usize {
153        (0..self.num_vertices())
154            .filter(|&vertex| !self.is_terminal(vertex))
155            .count()
156    }
157
158    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
159        self.evaluate(config).0
160    }
161
162    fn config_len(&self) -> usize {
163        self.num_edges() * 4
164    }
165
166    fn domain_size(capacity: u64) -> usize {
167        usize::try_from(capacity)
168            .ok()
169            .and_then(|value| value.checked_add(1))
170            .expect("capacity already validated to fit into usize")
171    }
172
173    fn edge_flows(&self, config: &[usize], edge_index: usize) -> Option<[usize; 4]> {
174        let start = edge_index.checked_mul(4)?;
175        Some([
176            *config.get(start)?,
177            *config.get(start + 1)?,
178            *config.get(start + 2)?,
179            *config.get(start + 3)?,
180        ])
181    }
182
183    fn is_terminal(&self, vertex: usize) -> bool {
184        [self.source_1, self.sink_1, self.source_2, self.sink_2].contains(&vertex)
185    }
186
187    fn flow_pair_for_commodity(flows: [usize; 4], commodity: usize) -> (usize, usize) {
188        match commodity {
189            1 => (flows[0], flows[1]),
190            2 => (flows[2], flows[3]),
191            _ => unreachable!("commodity must be 1 or 2"),
192        }
193    }
194
195    fn commodity_balance(&self, config: &[usize], commodity: usize, vertex: usize) -> Option<i128> {
196        let mut balance = 0i128;
197        for (edge_index, (u, v)) in self.graph.edges().into_iter().enumerate() {
198            let flows = self.edge_flows(config, edge_index)?;
199            let (uv, vu) = Self::flow_pair_for_commodity(flows, commodity);
200            let uv = i128::from(u64::try_from(uv).ok()?);
201            let vu = i128::from(u64::try_from(vu).ok()?);
202
203            if vertex == u {
204                balance -= uv;
205                balance += vu;
206            } else if vertex == v {
207                balance += uv;
208                balance -= vu;
209            }
210        }
211        Some(balance)
212    }
213
214    fn net_flow_into_sink(&self, config: &[usize], commodity: usize) -> Option<u64> {
215        let sink = match commodity {
216            1 => self.sink_1,
217            2 => self.sink_2,
218            _ => unreachable!("commodity must be 1 or 2"),
219        };
220        let balance = self.commodity_balance(config, commodity, sink)?;
221        u64::try_from(balance).ok()
222    }
223}
224
225impl Problem for UndirectedTwoCommodityIntegralFlow {
226    const NAME: &'static str = "UndirectedTwoCommodityIntegralFlow";
227    type Value = crate::types::Or;
228
229    fn variant() -> Vec<(&'static str, &'static str)> {
230        crate::variant_params![]
231    }
232
233    fn dims(&self) -> Vec<usize> {
234        self.capacities
235            .iter()
236            .flat_map(|&capacity| {
237                let domain = Self::domain_size(capacity);
238                std::iter::repeat_n(domain, 4)
239            })
240            .collect()
241    }
242
243    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
244        crate::types::Or({
245            if config.len() != self.config_len() {
246                return crate::types::Or(false);
247            }
248
249            for (edge_index, &capacity) in self.capacities.iter().enumerate() {
250                let Some(flows) = self.edge_flows(config, edge_index) else {
251                    return crate::types::Or(false);
252                };
253
254                if flows
255                    .iter()
256                    .any(|&value| u64::try_from(value).map_or(true, |value| value > capacity))
257                {
258                    return crate::types::Or(false);
259                }
260
261                if flows[0] > 0 && flows[1] > 0 {
262                    return crate::types::Or(false);
263                }
264                if flows[2] > 0 && flows[3] > 0 {
265                    return crate::types::Or(false);
266                }
267
268                let commodity_1 = u64::try_from(std::cmp::max(flows[0], flows[1]))
269                    .expect("flow values already validated against u64 capacities");
270                let commodity_2 = u64::try_from(std::cmp::max(flows[2], flows[3]))
271                    .expect("flow values already validated against u64 capacities");
272                let Some(shared) = commodity_1.checked_add(commodity_2) else {
273                    return crate::types::Or(false);
274                };
275                if shared > capacity {
276                    return crate::types::Or(false);
277                }
278            }
279
280            for vertex in 0..self.num_vertices() {
281                if self.is_terminal(vertex) {
282                    continue;
283                }
284
285                if self.commodity_balance(config, 1, vertex) != Some(0)
286                    || self.commodity_balance(config, 2, vertex) != Some(0)
287                {
288                    return crate::types::Or(false);
289                }
290            }
291
292            self.net_flow_into_sink(config, 1)
293                .is_some_and(|flow| flow >= self.requirement_1)
294                && self
295                    .net_flow_into_sink(config, 2)
296                    .is_some_and(|flow| flow >= self.requirement_2)
297        })
298    }
299}
300
301crate::declare_variants! {
302    default UndirectedTwoCommodityIntegralFlow => "5^num_edges",
303}
304
305#[cfg(feature = "example-db")]
306pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
307    vec![crate::example_db::specs::ModelExampleSpec {
308        id: "undirected_two_commodity_integral_flow",
309        instance: Box::new(UndirectedTwoCommodityIntegralFlow::new(
310            SimpleGraph::new(4, vec![(0, 2), (1, 2), (2, 3)]),
311            vec![1, 1, 2],
312            0,
313            3,
314            1,
315            3,
316            1,
317            1,
318        )),
319        optimal_config: vec![1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0],
320        optimal_value: serde_json::json!(true),
321    }]
322}
323
324#[cfg(test)]
325#[path = "../../unit_tests/models/graph/undirected_two_commodity_integral_flow.rs"]
326mod tests;
problemreductions/models/graph/undirected_two_commodity_integral_flow.rs

problemreductions/models/graph/
undirected_two_commodity_integral_flow.rs
