problemreductions/rules/
minimumfeedbackarcset_maximumlikelihoodranking.rs

1//! Reduction from MinimumFeedbackArcSet to MaximumLikelihoodRanking.
2//!
3//! On unit-weight instances, a ranking induces exactly the feedback arc set of
4//! backward arcs. The target matrix uses the skew-symmetric `c = 0` encoding:
5//! one-way arcs become `+/-1`, while bidirectional pairs and missing pairs map
6//! to `0`.
7
8use crate::models::graph::MinimumFeedbackArcSet;
9use crate::models::misc::MaximumLikelihoodRanking;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13#[allow(clippy::needless_range_loop)]
14fn build_skew_symmetric_matrix(problem: &MinimumFeedbackArcSet<i32>) -> Vec<Vec<i32>> {
15    let n = problem.num_vertices();
16    let graph = problem.graph();
17    let mut matrix = vec![vec![0i32; n]; n];
18
19    for i in 0..n {
20        for j in (i + 1)..n {
21            let ij = graph.has_arc(i, j);
22            let ji = graph.has_arc(j, i);
23            if ij && !ji {
24                matrix[i][j] = 1;
25                matrix[j][i] = -1;
26            } else if ji && !ij {
27                matrix[i][j] = -1;
28                matrix[j][i] = 1;
29            }
30        }
31    }
32
33    matrix
34}
35
36/// Result of reducing MinimumFeedbackArcSet to MaximumLikelihoodRanking.
37#[derive(Debug, Clone)]
38pub struct ReductionFASToMLR {
39    target: MaximumLikelihoodRanking,
40    source_arcs: Vec<(usize, usize)>,
41}
42
43impl ReductionResult for ReductionFASToMLR {
44    type Source = MinimumFeedbackArcSet<i32>;
45    type Target = MaximumLikelihoodRanking;
46
47    fn target_problem(&self) -> &Self::Target {
48        &self.target
49    }
50
51    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
52        self.source_arcs
53            .iter()
54            .map(|&(u, v)| usize::from(target_solution[u] > target_solution[v]))
55            .collect()
56    }
57}
58
59#[reduction(
60    overhead = {
61        num_items = "num_vertices",
62    }
63)]
64impl ReduceTo<MaximumLikelihoodRanking> for MinimumFeedbackArcSet<i32> {
65    type Result = ReductionFASToMLR;
66
67    fn reduce_to(&self) -> Self::Result {
68        assert!(
69            self.weights().iter().all(|&weight| weight == 1),
70            "MinimumFeedbackArcSet -> MaximumLikelihoodRanking requires unit arc weights"
71        );
72
73        ReductionFASToMLR {
74            target: MaximumLikelihoodRanking::new(build_skew_symmetric_matrix(self)),
75            source_arcs: self.graph().arcs(),
76        }
77    }
78}
79
80#[cfg(feature = "example-db")]
81pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
82    use crate::export::SolutionPair;
83    use crate::solvers::BruteForce;
84
85    vec![crate::example_db::specs::RuleExampleSpec {
86        id: "minimumfeedbackarcset_to_maximumlikelihoodranking",
87        build: || {
88            let source = MinimumFeedbackArcSet::new(
89                crate::topology::DirectedGraph::new(
90                    5,
91                    vec![(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2), (0, 4)],
92                ),
93                vec![1i32; 7],
94            );
95            let reduction = ReduceTo::<MaximumLikelihoodRanking>::reduce_to(&source);
96            let target_witness = BruteForce::new()
97                .find_witness(reduction.target_problem())
98                .expect("target should have an optimum");
99            let source_witness = reduction.extract_solution(&target_witness);
100
101            crate::example_db::specs::rule_example_with_witness::<_, MaximumLikelihoodRanking>(
102                source,
103                SolutionPair {
104                    source_config: source_witness,
105                    target_config: target_witness,
106                },
107            )
108        },
109    }]
110}
111
112#[cfg(test)]
113#[path = "../unit_tests/rules/minimumfeedbackarcset_maximumlikelihoodranking.rs"]
114mod tests;
problemreductions/rules/minimumfeedbackarcset_maximumlikelihoodranking.rs

problemreductions/rules/
minimumfeedbackarcset_maximumlikelihoodranking.rs
