payback/
exact_partitioning.rs

1use itertools::Itertools;
2use log::debug;
3use std::collections::HashMap;
4
5use crate::graph::{Edge, Graph, NamedNode};
6use crate::probleminstance::{ProblemInstance, Solution};
7
8/// Algorithm solving the payback problem naivly by iteration all possible partitionings of the
9/// vertices. Has a runtime of O*(n^n / (ln n)^n). Should not be used.
10///
11/// * `instance` - The problem instance which should be solved
12/// * `approx_solver` - Approximation algorithm used to solve partition, which have no zero sum
13/// subset
14///
15/// Example:
16/// ```
17/// use payback::graph::Graph;
18/// use payback::probleminstance::{ProblemInstance, Solution, SolvingMethods};
19///
20/// let instance: ProblemInstance = Graph::from(vec![-2, -1, 1, 2]).into();
21/// let solution: Solution = instance.solve_with(SolvingMethods::PartitioningStarExpand);
22/// ```
23pub(crate) fn naive_all_partitioning(
24    instance: &ProblemInstance,
25    approx_solver: &dyn Fn(&ProblemInstance) -> Solution,
26) -> Solution {
27    let mut partitionings = collect_all_partitionigns(&instance.g.vertices);
28    partitionings.sort_by_key(|a| std::cmp::Reverse(a.len()));
29    let solution = partitionings
30        .iter()
31        .find_map(|x| partition_solver(x, approx_solver));
32    solution
33}
34
35fn partition_solver(
36    partitioning: &Vec<Vec<&NamedNode>>,
37    approx_solver: &dyn Fn(&ProblemInstance) -> Solution,
38) -> Solution {
39    let mut acc: HashMap<Edge, f64> = HashMap::new();
40    for partition in partitioning {
41        let instance: ProblemInstance = Graph::from(partition.to_vec()).into();
42        let result: Solution = approx_solver(&instance);
43        match result {
44            Some(map) => {
45                acc.extend(map);
46            }
47            None => {
48                debug!(
49                    "Partitioning {:?} failed due to partition {:?}",
50                    partitioning, partition
51                );
52                return None;
53            }
54        }
55    }
56    debug!(
57        "Found solution for partitioning {:?}. Edges: {:?}",
58        partitioning, acc
59    );
60    Some(acc)
61}
62
63fn collect_all_partitionigns<'a, T>(items: &'a [T]) -> Vec<Vec<Vec<&'a T>>> {
64    let mut acc: Vec<Vec<Vec<&'a T>>> = Vec::new();
65    iterate_all_partitionings(&mut Vec::new(), items, &mut |x| {
66        acc.push(x.to_owned());
67    });
68    acc
69}
70
71fn iterate_all_partitionings<'a, T, F>(head: &mut Vec<Vec<&'a T>>, rest: &'a [T], f: &mut F)
72where
73    F: FnMut(&mut Vec<Vec<&'a T>>),
74{
75    if rest.is_empty() {
76        f(head)
77    } else {
78        let (first, tail) = rest.split_at(1);
79        for i in 0..head.len() {
80            if let Some(x) = head.get_mut(i) {
81                x.append(&mut first.iter().collect_vec());
82            }
83            iterate_all_partitionings(head, tail, f);
84            if let Some(x) = head.get_mut(i) {
85                x.pop();
86            }
87        }
88        head.push(first.iter().collect_vec());
89        iterate_all_partitionings(head, tail, f);
90        head.pop();
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use std::collections::HashSet;
97
98    use crate::approximation::{greedy_satisfaction, star_expand};
99    use crate::exact_partitioning::collect_all_partitionigns;
100    use crate::exact_partitioning::naive_all_partitioning;
101    use crate::graph::Graph;
102    use crate::probleminstance::ProblemInstance;
103    use env_logger::Env;
104    use log::debug;
105
106    fn init() {
107        let _ = env_logger::Builder::from_env(Env::default().default_filter_or("debug"))
108            .is_test(true)
109            .try_init();
110    }
111
112    #[test]
113    fn test_naive_all_partitioning() {
114        init();
115        debug!("Running 'test_perfect_matching_sol'");
116        let graph: Graph = vec![-1, -1, 1, 1, 2, -2, 3, -3].into();
117        debug!("Using graph: {:?}", graph);
118        let instance = ProblemInstance::from(graph);
119        let sol = naive_all_partitioning(&instance, &greedy_satisfaction);
120        assert!(sol.is_some());
121        debug!("Proposed solution by solver: {:?}", sol);
122        assert!(sol.unwrap().len() == 4);
123
124        let graph: Graph = vec![6, 3, 2, 1, -4, -8].into();
125        debug!("Using graph: {:?}", graph);
126        let instance = ProblemInstance::from(graph);
127        let sol = naive_all_partitioning(&instance, &star_expand);
128        assert!(sol.is_some());
129        debug!("Proposed solution by solver: {:?}", sol);
130        assert_eq!(sol.unwrap().len(), 4);
131
132        let graph: Graph = vec![6, 3, 2, 1, -4, -8, 0].into();
133        debug!("Using graph: {:?}", graph);
134        let instance = ProblemInstance::from(graph);
135        let sol = naive_all_partitioning(&instance, &star_expand);
136        assert!(sol.is_some());
137        debug!("Proposed solution by solver: {:?}", sol);
138        assert_eq!(sol.unwrap().len(), 4);
139
140        let graph: Graph = vec![1, 1, 1, 1, 1, 1, -6].into();
141        debug!("Using graph: {:?}", graph);
142        let instance = ProblemInstance::from(graph);
143        let sol = naive_all_partitioning(&instance, &star_expand);
144        assert!(sol.is_some());
145        debug!("Proposed solution by solver: {:?}", sol);
146        assert_eq!(sol.unwrap().len(), 6);
147
148        let graph: Graph = vec![9, 4, 1, -6, -6, -2].into();
149        debug!("Using graph: {:?}", graph);
150        let instance = ProblemInstance::from(graph);
151        let sol = naive_all_partitioning(&instance, &star_expand);
152        assert!(sol.is_some());
153        debug!("Proposed solution by solver: {:?}", sol);
154        assert_eq!(sol.unwrap().len(), 5);
155    }
156
157    #[test]
158    fn test_partitionings() {
159        init();
160        debug!("Running 'test_partitionings'");
161        let v: Vec<i64> = vec![1, 2, 3];
162        let acc = collect_all_partitionigns(&v);
163        debug!("All partitionings of '{:?}': {:?}", v, acc);
164        assert!(acc.len() == 5);
165        let calulated: HashSet<Vec<Vec<&i64>>> = acc.into_iter().collect();
166        let res: HashSet<Vec<Vec<&i64>>> = vec![
167            vec![vec![&1, &2, &3]],
168            vec![vec![&1], vec![&2, &3]],
169            vec![vec![&1, &2], vec![&3]],
170            vec![vec![&1, &3], vec![&2]],
171            vec![vec![&1], vec![&2], vec![&3]],
172        ]
173        .into_iter()
174        .collect();
175        assert_eq!(calulated, res);
176
177        let v: Vec<i64> = vec![1, 2, 3, 4];
178        let acc = collect_all_partitionigns(&v);
179        debug!("All partitionings of '{:?}': {:?}", v, acc);
180        let res: HashSet<Vec<Vec<&i64>>> = vec![
181            vec![vec![&1, &2, &3, &4]],
182            vec![vec![&1], vec![&2, &3, &4]],
183            vec![vec![&1, &2], vec![&3, &4]],
184            vec![vec![&1, &3, &4], vec![&2]],
185            vec![vec![&1], vec![&2], vec![&3, &4]],
186            vec![vec![&1, &2, &3], vec![&4]],
187            vec![vec![&1, &4], vec![&2, &3]],
188            vec![vec![&1], vec![&2, &3], vec![&4]],
189            vec![vec![&1, &3], vec![&2, &4]],
190            vec![vec![&1, &2, &4], vec![&3]],
191            vec![vec![&1], vec![&2, &4], vec![&3]],
192            vec![vec![&1, &2], vec![&3], vec![&4]],
193            vec![vec![&1, &3], vec![&2], vec![&4]],
194            vec![vec![&1, &4], vec![&2], vec![&3]],
195            vec![vec![&1], vec![&2], vec![&3], vec![&4]],
196        ]
197        .into_iter()
198        .collect();
199        let calulated: HashSet<Vec<Vec<&i64>>> = acc.into_iter().collect();
200        assert_eq!(calulated, res);
201    }
202}
payback/exact_partitioning.rs

payback/
exact_partitioning.rs
