assembly_theory/
kernels.rs

1//! Kernelize match-compatibility graphs to improve top-down search efficiency.
2//!
3//! The problem of computing the minimum assembly index of a molecule can be
4//! reduced to finding the maximum weight clique in a compatibility graph over
5//! matches (i.e., pairs of non-overlapping isomorphic subgraphs). Strucutral
6//! properties of this graph can be used to determine match pairs (i.e., nodes)
7//! that *definitely will* or *definitely won't* be used in an optimal
8//! solution. We call the process of identifying these nodes *kernelization*.
9//! Uses the strategies of neighborhood removal, isolated vertex removal, and
10//! domination as described in Section 5.2 of [Lamm et al.
11//! (2019)](https://doi.org/10.1137/1.9781611975499.12). (Note that they solve
12//! the equivalent problem of weighted independent set.)
13
14use clap::ValueEnum;
15
16/// Graph kernelization strategy when searching using the clique reduction.
17#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, ValueEnum)]
18pub enum KernelMode {
19    /// Do not apply any kernelizations.
20    None,
21    /// Apply kernels only after the initial construction of the compatibility
22    /// graph.
23    Once,
24    /// Apply kernels after the initial construction of the compability graph
25    /// and again after any fragmentations of the full molecule.
26    DepthOne,
27    /// Apply kernels after every fragmentation step.
28    Always,
29}