1use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::topology::DirectedGraph;
9use crate::traits::Problem;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13 ProblemSchemaEntry {
14 name: "IntegralFlowWithMultipliers",
15 display_name: "Integral Flow With Multipliers",
16 aliases: &[],
17 dimensions: &[],
18 category: crate::registry::ProblemCategory::Graph,
19 module_path: module_path!(),
20 description: "Integral flow feasibility on a directed graph with multiplier-scaled conservation at non-terminal vertices",
21 fields: IntegralFlowWithMultipliersCreateSpec::FIELDS,
22 }
23}
24
25#[derive(Debug, Clone, Serialize, Deserialize)]
26#[serde(try_from = "IntegralFlowWithMultipliersData")]
27pub struct IntegralFlowWithMultipliers {
28 graph: DirectedGraph,
29 source: usize,
30 sink: usize,
31 multipliers: Vec<i64>,
32 capacities: Vec<i64>,
33 requirement: i64,
34}
35
36#[derive(Deserialize)]
37struct IntegralFlowWithMultipliersData {
38 graph: DirectedGraph,
39 source: usize,
40 sink: usize,
41 multipliers: Vec<i64>,
42 capacities: Vec<i64>,
43 requirement: i64,
44}
45
46impl TryFrom<IntegralFlowWithMultipliersData> for IntegralFlowWithMultipliers {
47 type Error = crate::registry::ConstructionError;
48 fn try_from(data: IntegralFlowWithMultipliersData) -> Result<Self, Self::Error> {
49 Self::try_new(
50 data.graph,
51 data.source,
52 data.sink,
53 data.multipliers,
54 data.capacities,
55 data.requirement,
56 )
57 }
58}
59
60#[derive(Debug, Deserialize, crate::CreateSpec)]
61struct IntegralFlowWithMultipliersCreateSpec {
62 #[create(codec = "arc-list")]
63 arcs: Vec<(usize, usize)>,
64 num_vertices: Option<usize>,
65 #[create(codec = "comma-separated")]
66 capacities: Vec<i64>,
67 source: usize,
68 sink: usize,
69 #[create(codec = "comma-separated")]
70 multipliers: Vec<i64>,
71 requirement: i64,
72}
73
74impl TryFrom<IntegralFlowWithMultipliersCreateSpec> for IntegralFlowWithMultipliers {
75 type Error = crate::registry::ConstructionError;
76 fn try_from(
77 spec: IntegralFlowWithMultipliersCreateSpec,
78 ) -> Result<Self, crate::registry::ConstructionError> {
79 if spec.arcs.is_empty() {
80 return Err("arcs must be non-empty".into());
81 }
82 let inferred = spec
83 .arcs
84 .iter()
85 .flat_map(|&(u, v)| [u, v])
86 .max()
87 .map(|v| v.checked_add(1).ok_or("vertex count overflows usize"))
88 .transpose()?
89 .unwrap_or(0);
90 let count = spec.num_vertices.unwrap_or(inferred);
91 if count < inferred {
92 return Err("num_vertices is too small".into());
93 }
94 Self::try_new(
95 DirectedGraph::new(count, spec.arcs),
96 spec.source,
97 spec.sink,
98 spec.multipliers,
99 spec.capacities,
100 spec.requirement,
101 )
102 }
103}
104
105impl IntegralFlowWithMultipliers {
106 pub fn new(
107 graph: DirectedGraph,
108 source: usize,
109 sink: usize,
110 multipliers: Vec<i64>,
111 capacities: Vec<i64>,
112 requirement: i64,
113 ) -> Self {
114 Self::try_new(graph, source, sink, multipliers, capacities, requirement)
115 .unwrap_or_else(|error| panic!("{error}"))
116 }
117
118 fn try_new(
119 graph: DirectedGraph,
120 source: usize,
121 sink: usize,
122 multipliers: Vec<i64>,
123 capacities: Vec<i64>,
124 requirement: i64,
125 ) -> Result<Self, crate::registry::ConstructionError> {
126 if capacities.len() != graph.num_arcs() {
127 return Err(crate::registry::ConstructionError::length_mismatch(
128 "capacities",
129 capacities.len(),
130 graph.num_arcs(),
131 ));
132 }
133 if multipliers.len() != graph.num_vertices() {
134 return Err(crate::registry::ConstructionError::length_mismatch(
135 "multipliers",
136 multipliers.len(),
137 graph.num_vertices(),
138 ));
139 }
140
141 let num_vertices = graph.num_vertices();
142 if source >= num_vertices {
143 return Err(format!(
144 "source ({source}) must be less than num_vertices ({num_vertices})"
145 )
146 .into());
147 }
148 if sink >= num_vertices {
149 return Err(
150 format!("sink ({sink}) must be less than num_vertices ({num_vertices})").into(),
151 );
152 }
153 if source == sink {
154 return Err("source and sink must be distinct".into());
155 }
156
157 for (vertex, &multiplier) in multipliers.iter().enumerate() {
158 if vertex != source && vertex != sink && multiplier <= 0 {
159 return Err("non-terminal multipliers must be positive".into());
160 }
161 }
162
163 for &capacity in &capacities {
164 if usize::try_from(capacity)
165 .ok()
166 .and_then(|value| value.checked_add(1))
167 .is_none()
168 {
169 return Err(
170 "capacities must be nonnegative and their domains must fit into usize".into(),
171 );
172 }
173 }
174
175 Ok(Self {
176 graph,
177 source,
178 sink,
179 multipliers,
180 capacities,
181 requirement,
182 })
183 }
184
185 pub fn graph(&self) -> &DirectedGraph {
186 &self.graph
187 }
188
189 pub fn source(&self) -> usize {
190 self.source
191 }
192
193 pub fn sink(&self) -> usize {
194 self.sink
195 }
196
197 pub fn multipliers(&self) -> &[i64] {
198 &self.multipliers
199 }
200
201 pub fn capacities(&self) -> &[i64] {
202 &self.capacities
203 }
204
205 pub fn requirement(&self) -> i64 {
206 self.requirement
207 }
208
209 pub fn max_capacity_bits(&self) -> u64 {
211 crate::types::max_numeric_magnitude_bits(self.capacities.iter().copied())
212 }
213
214 pub fn num_vertices(&self) -> usize {
215 self.graph.num_vertices()
216 }
217
218 pub fn num_arcs(&self) -> usize {
219 self.graph.num_arcs()
220 }
221
222 pub fn max_capacity(&self) -> i64 {
223 self.capacities.iter().copied().max().unwrap_or(0)
224 }
225
226 fn domain_size(capacity: i64) -> usize {
227 usize::try_from(capacity)
228 .ok()
229 .and_then(|value| value.checked_add(1))
230 .expect("capacity already validated to fit into usize")
231 }
232
233 pub fn is_feasible(&self, config: &[usize]) -> Result<bool, crate::traits::EvaluationError> {
234 if config.len() != self.num_arcs() {
235 return Ok(false);
236 }
237
238 let num_vertices = self.num_vertices();
239 let mut inflow = vec![0_i64; num_vertices];
240 let mut outflow = vec![0_i64; num_vertices];
241
242 for (arc_index, ((u, v), &capacity)) in self
243 .graph
244 .arcs()
245 .into_iter()
246 .zip(self.capacities.iter())
247 .enumerate()
248 {
249 let Some(flow_usize) = config.get(arc_index).copied() else {
250 return Ok(false);
251 };
252 let Ok(flow_u64) = i64::try_from(flow_usize) else {
253 return Ok(false);
254 };
255 if flow_u64 > capacity {
256 return Ok(false);
257 }
258 outflow[u] = outflow[u].checked_add(flow_u64).ok_or_else(|| {
259 crate::traits::EvaluationError::IntegerOverflow(
260 "summing outgoing multiplied flow".into(),
261 )
262 })?;
263 inflow[v] = inflow[v].checked_add(flow_u64).ok_or_else(|| {
264 crate::traits::EvaluationError::IntegerOverflow(
265 "summing incoming multiplied flow".into(),
266 )
267 })?;
268 }
269
270 for vertex in 0..num_vertices {
271 if vertex == self.source || vertex == self.sink {
272 continue;
273 }
274 let expected_outflow = inflow[vertex]
275 .checked_mul(self.multipliers[vertex])
276 .ok_or_else(|| {
277 crate::traits::EvaluationError::IntegerOverflow(
278 "multiplying incoming flow by vertex multiplier".into(),
279 )
280 })?;
281 if expected_outflow != outflow[vertex] {
282 return Ok(false);
283 }
284 }
285
286 let sink_net_flow = inflow[self.sink]
287 .checked_sub(outflow[self.sink])
288 .ok_or_else(|| {
289 crate::traits::EvaluationError::IntegerOverflow(
290 "computing net flow into sink".into(),
291 )
292 })?;
293 Ok(sink_net_flow >= self.requirement)
294 }
295}
296
297impl Problem for IntegralFlowWithMultipliers {
298 const NAME: &'static str = "IntegralFlowWithMultipliers";
299 type Solution = Vec<usize>;
300 type Value = crate::types::Or;
301
302 crate::problem_parameters![
303 ("max_capacity", max_capacity),
304 ("max_capacity_bits", max_capacity_bits),
305 ("num_arcs", num_arcs),
306 ("num_vertices", num_vertices),
307 ];
308
309 fn evaluate(
310 &self,
311 config: &Self::Solution,
312 ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
313 if config.len() != self.num_arcs() {
314 return Err(crate::traits::EvaluationError::InvalidConfiguration(
315 "flow vector length does not match the graph arcs".into(),
316 ));
317 }
318 Ok(crate::types::Or(self.is_feasible(config)?))
319 }
320
321 fn variant() -> Vec<(&'static str, &'static str)> {
322 crate::variant_params![]
323 }
324}
325
326impl crate::solvers::BruteForceProblem for IntegralFlowWithMultipliers {
327 fn dimensions(&self) -> Vec<usize> {
328 self.capacities
329 .iter()
330 .map(|&capacity| Self::domain_size(capacity))
331 .collect()
332 }
333}
334
335crate::declare_variants! {
336 default IntegralFlowWithMultipliers => "(max_capacity + 1)^num_arcs" create IntegralFlowWithMultipliersCreateSpec,
337}
338
339crate::register_brute_force! {
340 IntegralFlowWithMultipliers,
341}
342
343#[cfg(feature = "example-db")]
344pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
345 vec![crate::example_db::specs::ModelExampleSpec {
346 id: "integral_flow_with_multipliers",
347 instance: Box::new(IntegralFlowWithMultipliers::new(
348 DirectedGraph::new(
349 8,
350 vec![
351 (0, 1),
352 (0, 2),
353 (0, 3),
354 (0, 4),
355 (0, 5),
356 (0, 6),
357 (1, 7),
358 (2, 7),
359 (3, 7),
360 (4, 7),
361 (5, 7),
362 (6, 7),
363 ],
364 ),
365 0,
366 7,
367 vec![1, 2, 3, 4, 5, 6, 4, 1],
368 vec![1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 4],
369 12,
370 )),
371 optimal_config: serde_json::json!(vec![1, 0, 1, 0, 1, 0, 2, 0, 4, 0, 6, 0]),
372 optimal_value: serde_json::json!(true),
373 }]
374}
375
376#[cfg(test)]
377#[path = "../../unit_tests/models/graph/integral_flow_with_multipliers.rs"]
378mod tests;