problemreductions/models/graph/
multiple_copy_file_allocation.rs

1//! Multiple Copy File Allocation problem implementation.
2//!
3//! The Multiple Copy File Allocation problem asks for a placement of file copies
4//! on graph vertices that minimizes the combined storage and access cost.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::{Deserialize, Serialize};
11use std::collections::VecDeque;
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MultipleCopyFileAllocation",
16        display_name: "Multiple Copy File Allocation",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Graph,
20        module_path: module_path!(),
21        description: "Place file copies on graph vertices to minimize total storage plus access cost",
22        fields: MultipleCopyFileAllocationCreateSpec::FIELDS,
23    }
24}
25
26/// Multiple Copy File Allocation problem.
27///
28/// Given an undirected graph G = (V, E), a usage value u(v) for each vertex,
29/// and a storage cost s(v) for each vertex, find a subset V' of copy vertices
30/// that minimizes:
31///
32/// Σ_{v ∈ V'} s(v) + Σ_{v ∈ V} u(v) · d(v, V')
33///
34/// where d(v, V') is the shortest-path distance from v to the nearest copy in V'.
35#[derive(Debug, Clone, Serialize, Deserialize)]
36#[serde(try_from = "MultipleCopyFileAllocationData")]
37pub struct MultipleCopyFileAllocation {
38    graph: SimpleGraph,
39    usage: Vec<i64>,
40    storage: Vec<i64>,
41}
42
43#[derive(Deserialize)]
44struct MultipleCopyFileAllocationData {
45    graph: SimpleGraph,
46    usage: Vec<i64>,
47    storage: Vec<i64>,
48}
49
50impl TryFrom<MultipleCopyFileAllocationData> for MultipleCopyFileAllocation {
51    type Error = crate::registry::ConstructionError;
52    fn try_from(data: MultipleCopyFileAllocationData) -> Result<Self, Self::Error> {
53        Self::try_new(data.graph, data.usage, data.storage)
54    }
55}
56
57#[derive(Debug, Deserialize, crate::CreateSpec)]
58struct MultipleCopyFileAllocationCreateSpec {
59    /// Network graph edges.
60    #[create(codec = "edge-list")]
61    graph: Vec<(usize, usize)>,
62    /// Vertex count, needed for isolated vertices.
63    num_vertices: Option<usize>,
64    /// Usage frequency per vertex.
65    #[create(codec = "comma-separated")]
66    usage: Vec<i64>,
67    /// Storage cost per vertex.
68    #[create(codec = "comma-separated")]
69    storage: Vec<i64>,
70}
71
72impl TryFrom<MultipleCopyFileAllocationCreateSpec> for MultipleCopyFileAllocation {
73    type Error = crate::registry::ConstructionError;
74    fn try_from(spec: MultipleCopyFileAllocationCreateSpec) -> Result<Self, Self::Error> {
75        if spec.graph.is_empty() && spec.num_vertices.is_none() {
76            return Err("num_vertices is required for an empty graph".into());
77        }
78        for &(u, v) in &spec.graph {
79            if u == v {
80                return Err(format!("self-loop {u}-{v} is not allowed").into());
81            }
82        }
83        let inferred = spec
84            .graph
85            .iter()
86            .flat_map(|&(u, v)| [u, v])
87            .max()
88            .map(|v| v.checked_add(1).ok_or("vertex count overflows usize"))
89            .transpose()?
90            .unwrap_or(0);
91        let count = spec.num_vertices.unwrap_or(inferred);
92        if count < inferred {
93            return Err("num_vertices is too small for graph endpoints".into());
94        }
95        Self::try_new(
96            SimpleGraph::new(count, spec.graph),
97            spec.usage,
98            spec.storage,
99        )
100    }
101}
102
103impl MultipleCopyFileAllocation {
104    /// Create a new Multiple Copy File Allocation instance.
105    pub fn new(graph: SimpleGraph, usage: Vec<i64>, storage: Vec<i64>) -> Self {
106        Self::try_new(graph, usage, storage).unwrap_or_else(|error| panic!("{error}"))
107    }
108
109    fn try_new(
110        graph: SimpleGraph,
111        usage: Vec<i64>,
112        storage: Vec<i64>,
113    ) -> Result<Self, crate::registry::ConstructionError> {
114        if usage.len() != graph.num_vertices() {
115            return Err(crate::registry::ConstructionError::length_mismatch(
116                "usage",
117                usage.len(),
118                graph.num_vertices(),
119            ));
120        }
121        if storage.len() != graph.num_vertices() {
122            return Err(crate::registry::ConstructionError::length_mismatch(
123                "storage",
124                storage.len(),
125                graph.num_vertices(),
126            ));
127        }
128        Ok(Self {
129            graph,
130            usage,
131            storage,
132        })
133    }
134
135    /// Get a reference to the underlying graph.
136    pub fn graph(&self) -> &SimpleGraph {
137        &self.graph
138    }
139
140    /// Get the usage values.
141    pub fn usage(&self) -> &[i64] {
142        &self.usage
143    }
144
145    /// Get the storage costs.
146    pub fn storage(&self) -> &[i64] {
147        &self.storage
148    }
149
150    /// Get the number of vertices.
151    pub fn num_vertices(&self) -> usize {
152        self.graph.num_vertices()
153    }
154
155    /// Get the number of edges.
156    pub fn num_edges(&self) -> usize {
157        self.graph.num_edges()
158    }
159
160    fn selected_vertices(&self, config: &[bool]) -> Option<Vec<usize>> {
161        if config.len() != self.graph.num_vertices() {
162            return None;
163        }
164
165        let mut selected = Vec::new();
166        for (vertex, &selected_here) in config.iter().enumerate() {
167            if selected_here {
168                selected.push(vertex);
169            }
170        }
171
172        if selected.is_empty() {
173            None
174        } else {
175            Some(selected)
176        }
177    }
178
179    fn shortest_distances(&self, selected: &[usize]) -> Option<Vec<usize>> {
180        let n = self.graph.num_vertices();
181        let mut distances = vec![usize::MAX; n];
182        let mut queue = VecDeque::new();
183
184        for &vertex in selected {
185            distances[vertex] = 0;
186            queue.push_back(vertex);
187        }
188
189        while let Some(vertex) = queue.pop_front() {
190            let next_distance = distances[vertex] + 1;
191            for neighbor in self.graph.neighbors(vertex) {
192                if distances[neighbor] == usize::MAX {
193                    distances[neighbor] = next_distance;
194                    queue.push_back(neighbor);
195                }
196            }
197        }
198
199        if distances.contains(&usize::MAX) {
200            None
201        } else {
202            Some(distances)
203        }
204    }
205
206    /// Compute the total storage plus access cost for a configuration.
207    ///
208    /// Returns `None` if the configuration is not binary, has the wrong length,
209    /// selects no copy vertices, or leaves some vertex unreachable from every copy.
210    pub fn total_cost(
211        &self,
212        config: &[bool],
213    ) -> Result<Option<i64>, crate::traits::EvaluationError> {
214        let Some(selected) = self.selected_vertices(config) else {
215            return Ok(None);
216        };
217        let Some(distances) = self.shortest_distances(&selected) else {
218            return Ok(None);
219        };
220
221        let mut storage_cost = 0_i64;
222        for vertex in selected {
223            storage_cost = storage_cost
224                .checked_add(self.storage[vertex])
225                .ok_or_else(|| {
226                    crate::traits::EvaluationError::IntegerOverflow(
227                        "summing file-copy storage costs".to_string(),
228                    )
229                })?;
230        }
231
232        let mut access_cost = 0_i64;
233        for (vertex, distance) in distances.into_iter().enumerate() {
234            let distance = i64::try_from(distance).map_err(|_| {
235                crate::traits::EvaluationError::IntegerOverflow(
236                    "converting file-copy access distance".to_string(),
237                )
238            })?;
239            let term = self.usage[vertex].checked_mul(distance).ok_or_else(|| {
240                crate::traits::EvaluationError::IntegerOverflow(
241                    "multiplying file usage by access distance".to_string(),
242                )
243            })?;
244            access_cost = access_cost.checked_add(term).ok_or_else(|| {
245                crate::traits::EvaluationError::IntegerOverflow(
246                    "summing file-copy access costs".to_string(),
247                )
248            })?;
249        }
250
251        Ok(Some(storage_cost.checked_add(access_cost).ok_or_else(
252            || {
253                crate::traits::EvaluationError::IntegerOverflow(
254                    "summing file-copy allocation costs".to_string(),
255                )
256            },
257        )?))
258    }
259
260    /// Check whether a configuration is a valid placement (at least one copy, all reachable).
261    pub fn is_valid_solution(
262        &self,
263        config: &[bool],
264    ) -> Result<bool, crate::traits::EvaluationError> {
265        Ok(self.total_cost(config)?.is_some())
266    }
267}
268
269impl Problem for MultipleCopyFileAllocation {
270    const NAME: &'static str = "MultipleCopyFileAllocation";
271    type Solution = Vec<bool>;
272    type Value = Min<i64>;
273
274    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
275
276    fn variant() -> Vec<(&'static str, &'static str)> {
277        crate::variant_params![]
278    }
279
280    fn evaluate(
281        &self,
282        config: &Self::Solution,
283    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
284        if config.len() != self.graph.num_vertices() {
285            return Err(crate::traits::EvaluationError::InvalidConfiguration(
286                "copy-selection length does not match the graph vertices".into(),
287            ));
288        }
289        Ok(Min(self.total_cost(config)?))
290    }
291}
292
293impl crate::solvers::BruteForceProblem for MultipleCopyFileAllocation {
294    fn dimensions(&self) -> Vec<usize> {
295        vec![2; self.graph.num_vertices()]
296    }
297}
298
299#[cfg(feature = "example-db")]
300pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
301    vec![crate::example_db::specs::ModelExampleSpec {
302        id: "multiple_copy_file_allocation",
303        instance: Box::new(MultipleCopyFileAllocation::new(
304            SimpleGraph::new(6, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]),
305            vec![5, 1, 1, 1, 1, 5],
306            vec![6, 2, 6, 6, 2, 6],
307        )),
308        optimal_config: serde_json::json!(vec![false, true, false, false, true, false]),
309        optimal_value: serde_json::json!(16),
310    }]
311}
312
313crate::declare_variants! {
314    default MultipleCopyFileAllocation => "2^num_vertices" create MultipleCopyFileAllocationCreateSpec,
315}
316
317crate::register_brute_force! {
318    MultipleCopyFileAllocation decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
319}
320
321#[cfg(test)]
322#[path = "../../unit_tests/models/graph/multiple_copy_file_allocation.rs"]
323mod tests;
problemreductions/models/graph/multiple_copy_file_allocation.rs

problemreductions/models/graph/
multiple_copy_file_allocation.rs
