1use crate::exact::{QuickBB, TamakiPid};
2use crate::graph::{BaseGraph, HashMapGraph};
3use crate::heuristic_elimination_order::{
4 HeuristicEliminationDecomposer, MinDegreeSelector, MinFillDegreeSelector, MinFillSelector,
5 Selector,
6};
7use crate::lowerbound::{LowerboundHeuristic, MinorMinWidth};
8use crate::meta_heuristics::TabuLocalSearch;
9use crate::rule_based_reducer::RuleBasedPreprocessor;
10use crate::safe_separator_framework::{SafeSeparatorFramework, SafeSeparatorLimits};
11use crate::tree_decomposition::TreeDecomposition;
12#[cfg(feature = "log")]
13use log::info;
14use std::cmp::max;
15
16pub trait DynamicUpperboundHeuristic: AtomSolver {}
17impl<S: Selector> DynamicUpperboundHeuristic for HeuristicEliminationDecomposer<S> {}
18
19pub type Lowerbound = usize;
20pub type Upperbound = usize;
21pub type DynamicUpperbound = fn(&HashMapGraph, Lowerbound, Upperbound) -> ComputationResult;
22pub type DynamicExact = fn(&HashMapGraph, Lowerbound, Upperbound) -> ComputationResult;
23pub type DynamicLowerbound = fn(&HashMapGraph) -> usize;
24
25#[derive(Clone, Copy)]
26pub enum LowerboundHeuristicType {
27 None,
28 MinorMinWidth(usize),
29 Custom(DynamicLowerbound),
30}
31
32impl Default for LowerboundHeuristicType {
33 fn default() -> Self {
34 Self::MinorMinWidth(10_000)
35 }
36}
37
38impl LowerboundHeuristicType {
39 pub(crate) fn compute(&self, graph: &HashMapGraph) -> Lowerbound {
40 match self {
41 LowerboundHeuristicType::None => {
42 graph.vertices().map(|v| graph.degree(v)).min().unwrap_or(0)
43 }
44 LowerboundHeuristicType::MinorMinWidth(limit) => {
45 if limit > &graph.order() {
46 graph.vertices().map(|v| graph.degree(v)).min().unwrap_or(0)
47 } else {
48 MinorMinWidth::with_graph(graph).compute()
49 }
50 }
51 LowerboundHeuristicType::Custom(heuristic) => heuristic(graph),
52 }
53 }
54}
55
56#[derive(Clone, Copy)]
57pub enum UpperboundHeuristicType {
58 None,
59 MinFill,
60 MinDegree,
61 MinFillDegree,
62 All,
63 Custom(DynamicUpperbound),
64}
65
66impl Default for UpperboundHeuristicType {
67 fn default() -> Self {
68 Self::All
69 }
70}
71
72impl UpperboundHeuristicType {
73 pub(crate) fn compute(
74 &self,
75 graph: &HashMapGraph,
76 lowerbound: usize,
77 ) -> Option<TreeDecomposition> {
78 match self {
79 UpperboundHeuristicType::None => None,
80 UpperboundHeuristicType::MinFill => {
81 let decomposer: HeuristicEliminationDecomposer<MinFillSelector> =
82 HeuristicEliminationDecomposer::with_bounds(graph, lowerbound, graph.order());
83 Some(decomposer.compute().computed_tree_decomposition().unwrap())
84 }
85 UpperboundHeuristicType::MinDegree => {
86 let decomposer: HeuristicEliminationDecomposer<MinDegreeSelector> =
87 HeuristicEliminationDecomposer::with_bounds(graph, lowerbound, graph.order());
88 Some(decomposer.compute().computed_tree_decomposition().unwrap())
89 }
90 UpperboundHeuristicType::MinFillDegree => {
91 let decomposer: HeuristicEliminationDecomposer<MinFillDegreeSelector> =
92 HeuristicEliminationDecomposer::with_bounds(graph, lowerbound, graph.order());
93 Some(decomposer.compute().computed_tree_decomposition().unwrap())
94 }
95 UpperboundHeuristicType::All => {
96 let a = HeuristicEliminationDecomposer::<MinFillSelector>::with_bounds(
97 graph,
98 lowerbound,
99 graph.order(),
100 )
101 .compute()
102 .computed_tree_decomposition()
103 .unwrap();
104 let b = HeuristicEliminationDecomposer::<MinDegreeSelector>::with_bounds(
105 graph,
106 lowerbound,
107 graph.order(),
108 )
109 .compute()
110 .computed_tree_decomposition()
111 .unwrap();
112 let c = HeuristicEliminationDecomposer::<MinFillDegreeSelector>::with_bounds(
113 graph,
114 lowerbound,
115 graph.order(),
116 )
117 .compute()
118 .computed_tree_decomposition()
119 .unwrap();
120 let mut best = a;
121 if best.max_bag_size > b.max_bag_size {
122 best = b;
123 }
124 if best.max_bag_size > c.max_bag_size {
125 best = c;
126 }
127 Some(best)
128 }
129 UpperboundHeuristicType::Custom(decomposer) => {
130 decomposer(graph, lowerbound, graph.order() - 1).computed_tree_decomposition()
131 }
132 }
133 }
134}
135
136#[derive(Clone, Copy)]
137pub enum AtomSolverType {
138 None,
139 MinFill,
140 MinDegree,
141 MinFillDegree,
142 Tamaki,
143 TabuLocalSearch,
144 TabuLocalSearchInfinite,
145 QuickBB,
146 Custom(DynamicExact),
147}
148
149impl Default for AtomSolverType {
150 fn default() -> Self {
151 Self::Tamaki
152 }
153}
154
155impl AtomSolverType {
156 pub(crate) fn compute(
157 &self,
158 sub_graph: &HashMapGraph,
159 lowerbound: usize,
160 upperbound: usize,
161 seed: u64,
162 ) -> ComputationResult {
163 match self {
164 AtomSolverType::None => ComputationResult::Bounds(Bounds {
165 lowerbound,
166 upperbound,
167 }),
168 AtomSolverType::MinFill => {
169 HeuristicEliminationDecomposer::<MinFillSelector>::with_bounds(
170 sub_graph, lowerbound, upperbound,
171 )
172 .compute()
173 }
174 AtomSolverType::MinDegree => {
175 HeuristicEliminationDecomposer::<MinDegreeSelector>::with_bounds(
176 sub_graph, lowerbound, upperbound,
177 )
178 .compute()
179 }
180 AtomSolverType::MinFillDegree => {
181 HeuristicEliminationDecomposer::<MinFillDegreeSelector>::with_bounds(
182 sub_graph, lowerbound, upperbound,
183 )
184 .compute()
185 }
186 AtomSolverType::Tamaki => {
187 TamakiPid::with_bounds(sub_graph, lowerbound, upperbound).compute()
188 }
189 AtomSolverType::TabuLocalSearch => {
190 TabuLocalSearch::with_bounds(sub_graph, lowerbound, upperbound)
191 .seed(seed)
192 .compute()
193 }
194 AtomSolverType::TabuLocalSearchInfinite => {
195 TabuLocalSearch::with_bounds(sub_graph, lowerbound, upperbound)
196 .seed(seed)
197 .epochs(usize::MAX)
198 .compute()
199 }
200 AtomSolverType::QuickBB => {
201 QuickBB::with_bounds(sub_graph, lowerbound, upperbound).compute()
202 }
203 AtomSolverType::Custom(solver) => solver(sub_graph, lowerbound, upperbound),
204 }
205 }
206}
207
208#[derive(Clone, Copy, Default)]
209pub struct AlgorithmTypes {
210 pub atom_solver: AtomSolverType,
211 pub upperbound: UpperboundHeuristicType,
212 pub lowerbound: LowerboundHeuristicType,
213}
214
215impl AlgorithmTypes {
216 impl_setter!(self, atom_solver, AtomSolverType);
217 impl_setter!(self, upperbound, UpperboundHeuristicType);
218 impl_setter!(self, lowerbound, LowerboundHeuristicType);
219}
220
221pub struct Solver {
222 algorithm_types: AlgorithmTypes,
223 safe_separator_limits: SafeSeparatorLimits,
224 apply_reduction_rules: bool,
225 use_atom_width_as_lower_bound: bool,
226 seed: Option<u64>,
227}
228
229impl Default for Solver {
230 fn default() -> Self {
231 Self {
232 algorithm_types: AlgorithmTypes::default(),
233 safe_separator_limits: SafeSeparatorLimits::default(),
234 apply_reduction_rules: true,
235 use_atom_width_as_lower_bound: true,
236 seed: None,
237 }
238 }
239}
240
241impl Solver {
242 pub fn default_heuristic() -> Self {
243 Self {
244 algorithm_types: AlgorithmTypes::default().atom_solver(AtomSolverType::None),
245 safe_separator_limits: SafeSeparatorLimits::default(),
246 apply_reduction_rules: true,
247 use_atom_width_as_lower_bound: true,
248 seed: None,
249 }
250 }
251
252 pub fn auto(graph: &HashMapGraph) -> Self {
253 match graph.order() {
254 0..=3000 => {
255 Self::default_heuristic().algorithm_types(AlgorithmTypes::default().atom_solver(
256 AtomSolverType::Custom(|graph, lowerbound, upperbound| {
257 if graph.order() <= 100 {
258 #[cfg(feature = "log")]
259 info!("Attempting to solve atom exactly");
260 TamakiPid::with_bounds(graph, lowerbound, upperbound).compute()
261 } else {
262 #[cfg(feature = "log")]
263 info!("Atom too large to be solved exactly, trying tabu local search");
264 TabuLocalSearch::with_bounds(graph, lowerbound, upperbound)
265 .epochs(250)
266 .compute();
267
268 ComputationResult::Bounds(Bounds {
269 lowerbound,
270 upperbound,
271 })
272 }
273 }),
274 ))
275 }
276 3001..=10000 => Self::default_heuristic(),
277 10001..=50000 => {
278 let lowerbound = LowerboundHeuristicType::None;
279 let upperbound = UpperboundHeuristicType::MinDegree;
280 let atom_solver = AtomSolverType::None;
281 let algorithm_types = AlgorithmTypes {
282 atom_solver,
283 upperbound,
284 lowerbound,
285 };
286 let limits = SafeSeparatorLimits::only_cut_vertex();
287 Self::default()
288 .algorithm_types(algorithm_types)
289 .safe_separator_limits(limits)
290 .apply_reduction_rules(true)
291 }
292 _ => {
293 let lowerbound = LowerboundHeuristicType::None;
294 let upperbound = UpperboundHeuristicType::MinDegree;
295 let atom_solver = AtomSolverType::None;
296 let algorithm_types = AlgorithmTypes {
297 atom_solver,
298 upperbound,
299 lowerbound,
300 };
301 let limits = SafeSeparatorLimits::skip_all();
302 Self::default()
303 .algorithm_types(algorithm_types)
304 .safe_separator_limits(limits)
305 .apply_reduction_rules(false)
306 }
307 }
308 }
309
310 pub fn default_exact() -> Self {
311 Self::default()
312 }
313
314 impl_setter!(self, algorithm_types, AlgorithmTypes);
315 impl_setter!(self, safe_separator_limits, SafeSeparatorLimits);
316 impl_setter!(self, apply_reduction_rules, bool);
317 impl_setter!(self, use_atom_width_as_lower_bound, bool);
318 impl_setter!(self, seed, Option<u64>);
319
320 pub fn solve(&self, graph: &HashMapGraph) -> TreeDecomposition {
321 #[cfg(feature = "log")]
322 info!("attempting to solve graph with {} vertices", graph.order());
323 let mut td = TreeDecomposition::default();
324 if graph.order() == 0 {
325 return td;
326 } else if graph.order() <= 2 {
327 td.add_bag(graph.vertices().collect());
328 return td;
329 } else {
330 let mut lowerbound = 0;
331 let components = graph.connected_components();
332 #[cfg(feature = "log")]
333 info!("obtained {} components", components.len());
334 if components.len() > 1 {
335 td.add_bag(Default::default());
336 }
337 for sub_graph in components.iter().map(|c| graph.vertex_induced(c)) {
338 #[cfg(feature = "log")]
339 info!(
340 "attempting to solve subgraph with {} vertices",
341 sub_graph.order()
342 );
343 if sub_graph.order() <= 2 {
344 let idx = td.add_bag(sub_graph.vertices().collect());
345 if td.bags.len() > 1 {
346 td.add_edge(0, idx);
347 }
348 continue;
349 }
350 lowerbound = max(lowerbound, 1);
351
352 let reducer: Option<_> = if self.apply_reduction_rules {
353 #[cfg(feature = "log")]
354 info!("applying reduction rules");
355 let mut tmp = RuleBasedPreprocessor::new(&sub_graph);
356 tmp.preprocess();
357
358 #[cfg(feature = "log")]
359 info!("reduced graph to: {}", tmp.graph().order());
360
361 if tmp.graph().order() <= lowerbound + 1 {
362 let tmp_g = tmp.graph().clone();
363 let mut tmp_td = tmp.into_td();
364 tmp_td.flatten();
365 match tmp_td.verify(&tmp_g) {
366 Ok(_) => {
367 #[cfg(feature = "log")]
368 info!("partial td computed after reduction rules is valid!");
369 }
370 Err(e) => {
371 panic!(
372 " partial td computed after reduction rules is invalid: {}",
373 e
374 );
375 }
376 }
377 td.combine_with_or_replace(0, tmp_td);
378 continue;
379 }
380 Some(tmp)
381 } else {
382 None
383 };
384
385 let (reduced_graph, new_lowerbound) = match reducer.as_ref() {
386 None => (&sub_graph, 0),
387 Some(reducer) => (reducer.graph(), reducer.lower_bound),
388 };
389 lowerbound = max(lowerbound, new_lowerbound);
390
391 #[cfg(feature = "log")]
392 info!("solving reduced graph");
393
394 let result = SafeSeparatorFramework::default()
395 .algorithms(self.algorithm_types)
396 .seed(self.seed)
397 .safe_separator_limits(self.safe_separator_limits)
398 .use_atom_width_as_lower_bound(self.use_atom_width_as_lower_bound)
399 .compute(reduced_graph, lowerbound);
400 lowerbound = max(lowerbound, result.lowerbound);
401 let mut partial_td = result.tree_decomposition;
402 partial_td.flatten();
403 if self.use_atom_width_as_lower_bound {
404 lowerbound = max(lowerbound, partial_td.max_bag_size - 1);
405 }
406 match partial_td.verify(reduced_graph) {
407 Ok(_) => {
408 #[cfg(feature = "log")]
409 info!("partial td computed after reduction rules is valid!");
410 }
411 Err(e) => {
412 panic!(
413 " partial td computed after reduction rules is invalid: {}",
414 e
415 );
416 }
417 }
418
419 #[cfg(feature = "log")]
420 info!("root bag before: {:?}!", td.bags[0]);
421 match reducer {
422 None => td.combine_with_or_replace(0, partial_td),
423 Some(reducer) => {
424 td.combine_with_or_replace(0, reducer.combine_into_td(partial_td))
425 }
426 };
427 #[cfg(feature = "log")]
428 info!("root bag after: {:?}!", td.bags[0]);
429 }
430 }
431 td
432 }
433}
434
435pub trait AtomSolver {
436 fn with_graph(graph: &HashMapGraph) -> Self
437 where
438 Self: Sized;
439 fn with_bounds(graph: &HashMapGraph, lowerbound: usize, upperbound: usize) -> Self
440 where
441 Self: Sized;
442 fn compute(self) -> ComputationResult;
443}
444
445pub struct Bounds {
446 pub lowerbound: usize,
447 pub upperbound: usize,
448}
449
450pub enum ComputationResult {
451 ComputedTreeDecomposition(TreeDecomposition),
452 Bounds(Bounds),
453}
454
455impl ComputationResult {
456 pub fn computed_tree_decomposition(self) -> Option<TreeDecomposition> {
457 match self {
458 ComputationResult::ComputedTreeDecomposition(td) => Some(td),
459 _ => None,
460 }
461 }
462}