problem-reductions/src/unit_tests/rules/minimumdominatingset_minimumsetcovering.rs at d443ae6342ef03e87e1b52b35db7137382b94cab · CodingThrust/problem-reductions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
use super::*;
use crate::rules::test_helpers::assert_optimization_round_trip_from_optimization_target;
use crate::solvers::BruteForce;
use crate::traits::Problem;
use crate::types::Min;

#[test]
fn test_minimumdominatingset_to_minimumsetcovering_closed_loop() {
    let source = MinimumDominatingSet::new(SimpleGraph::path(5), vec![3, 1, 4, 1, 3]);
    let reduction = ReduceTo::<MinimumSetCovering<i32>>::reduce_to(&source);

    assert_optimization_round_trip_from_optimization_target(
        &source,
        &reduction,
        "MinimumDominatingSet -> MinimumSetCovering weighted path",
    );

    let target_witnesses = BruteForce::new().find_all_witnesses(reduction.target_problem());
    assert_eq!(target_witnesses, vec![vec![0, 1, 0, 1, 0]]);
    assert_eq!(
        reduction.extract_solution(&target_witnesses[0]),
        vec![0, 1, 0, 1, 0]
    );
}

#[test]
fn test_exact_target_structure() {
    let source = MinimumDominatingSet::new(SimpleGraph::path(5), vec![3, 1, 4, 1, 3]);
    let reduction = ReduceTo::<MinimumSetCovering<i32>>::reduce_to(&source);
    let target = reduction.target_problem();

    assert_eq!(target.universe_size(), 5);
    assert_eq!(target.num_sets(), 5);
    assert_eq!(
        target.sets(),
        &[
            vec![0, 1],
            vec![0, 1, 2],
            vec![1, 2, 3],
            vec![2, 3, 4],
            vec![3, 4],
        ]
    );
    assert_eq!(target.weights_ref(), &[3, 1, 4, 1, 3]);
}

#[test]
fn test_infeasible_configuration_preservation() {
    let source = MinimumDominatingSet::new(SimpleGraph::path(5), vec![3, 1, 4, 1, 3]);
    let reduction = ReduceTo::<MinimumSetCovering<i32>>::reduce_to(&source);
    let endpoint_only = vec![1, 0, 0, 0, 0];

    assert_eq!(source.evaluate(&endpoint_only), Min(None));
    assert_eq!(
        reduction.target_problem().evaluate(&endpoint_only),
        Min(None)
    );
}

#[test]
fn test_signed_weight_optimality_and_extraction() {
    let source = MinimumDominatingSet::new(SimpleGraph::path(3), vec![-5, 10, -7]);
    let reduction = ReduceTo::<MinimumSetCovering<i32>>::reduce_to(&source);

    assert_optimization_round_trip_from_optimization_target(
        &source,
        &reduction,
        "MinimumDominatingSet -> MinimumSetCovering signed weights",
    );

    let target_witnesses = BruteForce::new().find_all_witnesses(reduction.target_problem());
    assert_eq!(target_witnesses, vec![vec![1, 0, 1]]);
    assert_eq!(
        reduction.extract_solution(&target_witnesses[0]),
        vec![1, 0, 1]
    );
}

#[test]
fn test_empty_and_isolated_graphs() {
    let empty = MinimumDominatingSet::new(SimpleGraph::empty(0), vec![]);
    let empty_reduction = ReduceTo::<MinimumSetCovering<i32>>::reduce_to(&empty);
    assert_eq!(empty_reduction.target_problem().universe_size(), 0);
    assert!(empty_reduction.target_problem().sets().is_empty());
    assert_optimization_round_trip_from_optimization_target(
        &empty,
        &empty_reduction,
        "empty MinimumDominatingSet",
    );

    let isolated = MinimumDominatingSet::new(SimpleGraph::empty(3), vec![3, 2, 1]);
    let isolated_reduction = ReduceTo::<MinimumSetCovering<i32>>::reduce_to(&isolated);
    assert_eq!(
        isolated_reduction.target_problem().sets(),
        &[vec![0], vec![1], vec![2]]
    );
    assert_eq!(
        BruteForce::new().find_all_witnesses(isolated_reduction.target_problem()),
        vec![vec![1, 1, 1]]
    );
    assert_optimization_round_trip_from_optimization_target(
        &isolated,
        &isolated_reduction,
        "isolated MinimumDominatingSet",
    );
}

#[test]
fn test_self_loops_and_repeated_edges_are_deduplicated() {
    let source = MinimumDominatingSet::new(
        SimpleGraph::new(4, vec![(0, 0), (0, 1), (0, 1), (1, 0), (2, 2)]),
        vec![-4, 2, -1, 7],
    );
    let reduction = ReduceTo::<MinimumSetCovering<i32>>::reduce_to(&source);

    assert_eq!(
        reduction.target_problem().sets(),
        &[vec![0, 1], vec![0, 1], vec![2], vec![3]]
    );
    assert_optimization_round_trip_from_optimization_target(
        &source,
        &reduction,
        "MinimumDominatingSet with loops and repeated edges",
    );
}