problemreductions/rules/unitdiskmapping/
weighted.rs

1//! Weight injection and center tracing for triangular lattice mappings.
2
3use super::ksg::MappingResult;
4use super::triangular::gadgets::{tape_entry_center_transform, tape_entry_size};
5use super::{mapping_integer_overflow, mapping_invalid, mapping_non_finite};
6use crate::rules::ReductionError;
7use crate::types::i64_to_exact_f64;
8use std::collections::HashMap;
9
10/// Trace each original vertex center through the recorded gadget transformations.
11pub fn trace_centers(result: &MappingResult) -> Result<Vec<(usize, usize)>, ReductionError> {
12    let mut centers = result
13        .lines
14        .iter()
15        .map(|line| {
16            let (row, column) = line.center_location(result.padding, result.spacing);
17            column
18                .checked_add(1)
19                .map(|column| (row, column))
20                .ok_or(mapping_integer_overflow(
21                    "offsetting a triangular copy-line center",
22                ))
23        })
24        .collect::<Result<Vec<_>, _>>()?;
25
26    for entry in &result.tape {
27        let (height, width) = tape_entry_size(entry.pattern_idx).ok_or(mapping_invalid(
28            "mapping result contains an unknown triangular gadget",
29        ))?;
30        let row_end = entry
31            .row
32            .checked_add(height)
33            .ok_or(mapping_integer_overflow(
34                "computing triangular gadget bounds",
35            ))?;
36        let column_end = entry
37            .col
38            .checked_add(width)
39            .ok_or(mapping_integer_overflow(
40                "computing triangular gadget bounds",
41            ))?;
42
43        let Some((source, shift)) = tape_entry_center_transform(entry.pattern_idx) else {
44            continue;
45        };
46        for center in &mut centers {
47            if center.0 >= entry.row
48                && center.0 < row_end
49                && center.1 >= entry.col
50                && center.1 < column_end
51                && (center.0 - entry.row + 1, center.1 - entry.col + 1) == source
52            {
53                center.0 = center
54                    .0
55                    .checked_add_signed(shift.0)
56                    .ok_or(mapping_integer_overflow("moving a triangular center row"))?;
57                center.1 = center
58                    .1
59                    .checked_add_signed(shift.1)
60                    .ok_or(mapping_integer_overflow(
61                        "moving a triangular center column",
62                    ))?;
63            }
64        }
65    }
66
67    let mut indexed = result
68        .lines
69        .iter()
70        .zip(centers)
71        .map(|(line, center)| (line.vertex, center))
72        .collect::<Vec<_>>();
73    indexed.sort_by_key(|(vertex, _)| *vertex);
74    Ok(indexed.into_iter().map(|(_, center)| center).collect())
75}
76
77/// Add source weights in `[0, 1]` to the corresponding mapped center nodes.
78pub fn map_weights(
79    result: &MappingResult,
80    source_weights: &[f64],
81) -> Result<Vec<f64>, ReductionError> {
82    if source_weights
83        .iter()
84        .any(|&weight| !weight.is_finite() || !(0.0..=1.0).contains(&weight))
85    {
86        return Err(mapping_invalid(
87            "source weights must be finite and in [0, 1]",
88        ));
89    }
90    if source_weights.len() != result.lines.len() {
91        return Err(mapping_invalid(
92            "source weight count must match the original vertex count",
93        ));
94    }
95
96    let mut weights = result
97        .node_weights
98        .iter()
99        .map(|&weight| {
100            i64_to_exact_f64(weight).map_err(|_| {
101                mapping_invalid("a mapped node weight is not exactly representable as f64")
102            })
103        })
104        .collect::<Result<Vec<_>, _>>()?;
105    let positions = result
106        .positions
107        .iter()
108        .enumerate()
109        .map(|(index, &(row, column))| {
110            let row = usize::try_from(row)
111                .map_err(|_| mapping_invalid("mapping result contains a negative grid row"))?;
112            let column = usize::try_from(column)
113                .map_err(|_| mapping_invalid("mapping result contains a negative grid column"))?;
114            Ok(((row, column), index))
115        })
116        .collect::<Result<HashMap<_, _>, ReductionError>>()?;
117
118    for (center, source_weight) in trace_centers(result)?.into_iter().zip(source_weights) {
119        let index = positions.get(&center).copied().ok_or(mapping_invalid(
120            "a traced center is missing from the mapped graph",
121        ))?;
122        let weight = weights[index] + source_weight;
123        if !weight.is_finite() {
124            return Err(mapping_non_finite(
125                "adding a source weight to a mapped center",
126            ));
127        }
128        weights[index] = weight;
129    }
130
131    Ok(weights)
132}
133
134#[cfg(test)]
135#[path = "../../unit_tests/rules/unitdiskmapping/weighted.rs"]
136mod tests;
problemreductions/rules/unitdiskmapping/weighted.rs

problemreductions/rules/unitdiskmapping/
weighted.rs
