problemreductions/rules/
optimallineararrangement_consecutiveonesmatrixaugmentation.rs

1//! Incidence-matrix reduction from decision linear arrangement to consecutive
2//! ones augmentation (Booth, 1975, Theorem 4.19, with the matrix transposed).
3//! For every ordering, augmentation cost equals total edge length minus the
4//! number of non-loop edges. Loops contribute zero to both costs; parallel
5//! edges contribute separately.
6
7use crate::models::algebraic::ConsecutiveOnesMatrixAugmentation;
8use crate::models::decision::Decision;
9use crate::models::graph::OptimalLinearArrangement;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::topology::{Graph, SimpleGraph};
13
14/// The target incidence matrix, or a fixed infeasible matrix when the source
15/// bound is below the universal lower bound on arrangement length.
16#[derive(Debug, Clone)]
17pub struct ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation {
18    target: ConsecutiveOnesMatrixAugmentation,
19}
20
21impl ReductionResult for ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation {
22    type Source = Decision<OptimalLinearArrangement<SimpleGraph>>;
23    type Target = ConsecutiveOnesMatrixAugmentation;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_witness(
34            self.target_problem(),
35            target_solution,
36            |value| value.0,
37            "target column order is not a satisfying augmentation certificate",
38        )?;
39        // Validation establishes a permutation within the augmentation budget.
40        // The NO sentinel has no such certificate; all remaining columns are
41        // source vertices, including the empty permutation for an empty graph.
42        let mut arrangement = vec![0; target_solution.len()];
43        for (position, &vertex) in target_solution.iter().enumerate() {
44            arrangement[vertex] = position;
45        }
46        Ok(arrangement)
47    }
48}
49
50#[crate::aggregate_reduction(identity)]
51impl crate::rules::AggregateReductionResult
52    for ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation
53{
54}
55
56#[reduction(
57    transform = upper_bound {
58        num_rows = "num_edges + 3",
59        num_cols = "num_vertices + 3",
60    }
61)]
62impl ReduceTo<ConsecutiveOnesMatrixAugmentation>
63    for Decision<OptimalLinearArrangement<SimpleGraph>>
64{
65    type Result = ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation;
66
67    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
68        let n = self.num_vertices();
69        let edges = self.inner().graph().edges();
70        let non_loops = <Self as ReduceTo<ConsecutiveOnesMatrixAugmentation>>::exact_i64(
71            edges.iter().filter(|(u, v)| u != v).count(),
72            "converting the number of non-loop edges to i64",
73        )?;
74        let k = *self.bound();
75        let (matrix, bound) = if k < non_loops {
76            // Every non-loop edge has length at least one. The three pairs of
77            // columns cannot all be adjacent, so this matrix is genuinely NO.
78            (
79                vec![
80                    vec![true, true, false],
81                    vec![false, true, true],
82                    vec![true, false, true],
83                ],
84                0,
85            )
86        } else {
87            // A zero row preserves the vertex columns when there are no edges.
88            // An empty graph is represented by one empty row, with no columns.
89            let mut matrix = vec![vec![false; n]; edges.len().max(1)];
90            for (row, (u, v)) in edges.into_iter().enumerate() {
91                matrix[row][u] = true;
92                matrix[row][v] = true;
93            }
94            // 0 <= non_loops <= k <= i64::MAX, so subtraction is exact.
95            (matrix, k - non_loops)
96        };
97        Ok(
98            ReductionOptimalLinearArrangementToConsecutiveOnesMatrixAugmentation {
99                target: ConsecutiveOnesMatrixAugmentation::try_new(matrix, bound).map_err(
100                    <Self as ReduceTo<ConsecutiveOnesMatrixAugmentation>>::target_construction,
101                )?,
102            },
103        )
104    }
105}
106
107#[cfg(feature = "example-db")]
108pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
109    use crate::export::SolutionPair;
110
111    vec![crate::example_db::specs::RuleExampleSpec {
112        id: "optimallineararrangement_to_consecutiveonesmatrixaugmentation",
113        build: || {
114            use crate::example_db::specs::assemble_rule_example;
115
116            // 6 vertices, 7 edges (path + two chords). Optimal arrangement
117            // [0,1,2,3,4,5] has total edge length 11; with k = 11 the target
118            // bound is 11 - 7 = 4 and the identity column permutation works.
119            let source = Decision::new(
120                OptimalLinearArrangement::new(SimpleGraph::new(
121                    6,
122                    vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (0, 3), (2, 5)],
123                )),
124                11,
125            );
126            let reduction = ReduceTo::<ConsecutiveOnesMatrixAugmentation>::reduce_to(&source)
127                .expect("reduction should succeed");
128            // Source arrangement f(v) = v <=> target column permutation = identity.
129            let source_config = vec![0, 1, 2, 3, 4, 5];
130            let target_config = vec![0, 1, 2, 3, 4, 5];
131            assemble_rule_example(
132                &source,
133                reduction.target_problem(),
134                vec![SolutionPair {
135                    source_config: serde_json::to_value(source_config)
136                        .expect("solution serialization must succeed"),
137                    target_config: serde_json::to_value(target_config)
138                        .expect("solution serialization must succeed"),
139                }],
140            )
141        },
142    }]
143}
144
145#[cfg(test)]
146#[path = "../unit_tests/rules/optimallineararrangement_consecutiveonesmatrixaugmentation.rs"]
147mod tests;
problemreductions/rules/optimallineararrangement_consecutiveonesmatrixaugmentation.rs

problemreductions/rules/
optimallineararrangement_consecutiveonesmatrixaugmentation.rs
