problemreductions/models/set/
mod.rs

1//! Set-based problems.
2//!
3//! This module contains NP-hard problems based on set operations:
4//! - [`ConsecutiveSets`]: Consecutive arrangement of subset elements in a string
5//! - [`ExactCoverBy3Sets`]: Exact cover by 3-element subsets (X3C)
6//! - [`ComparativeContainment`]: Compare containment-weight sums for two set families
7//! - [`IntegerKnapsack`]: Maximize value with integer multiplicities subject to capacity
8//! - [`MaximumSetPacking`]: Maximum weight set packing
9//! - [`MinimumHittingSet`]: Minimum-size universe subset hitting every set
10//! - [`MinimumSetCovering`]: Minimum weight set cover
11//! - [`PrimeAttributeName`]: Determine if an attribute belongs to any candidate key
12//! - [`RootedTreeStorageAssignment`]: Extend subsets to directed tree paths within a total-cost bound
13//! - [`SetBasis`]: Minimum-cardinality basis generating all sets by union
14//! - [`SetSplitting`]: 2-color universe so every specified subset is non-monochromatic
15//! - [`ThreeDimensionalMatching`]: Perfect matching in a tripartite 3-uniform hypergraph
16//! - [`TwoDimensionalConsecutiveSets`]: 2D consecutive arrangement of subset elements
17//! - [`MinimumCardinalityKey`]: Smallest attribute set that uniquely identifies tuples
18
19pub(crate) mod comparative_containment;
20pub(crate) mod consecutive_sets;
21pub(crate) mod exact_cover_by_3_sets;
22pub(crate) mod integer_knapsack;
23pub(crate) mod maximum_set_packing;
24pub(crate) mod minimum_cardinality_key;
25pub(crate) mod minimum_hitting_set;
26pub(crate) mod minimum_set_covering;
27pub(crate) mod prime_attribute_name;
28pub(crate) mod rooted_tree_storage_assignment;
29pub(crate) mod set_basis;
30pub(crate) mod set_splitting;
31pub(crate) mod three_dimensional_matching;
32pub(crate) mod two_dimensional_consecutive_sets;
33
34pub use comparative_containment::ComparativeContainment;
35pub use consecutive_sets::ConsecutiveSets;
36pub use exact_cover_by_3_sets::ExactCoverBy3Sets;
37pub use integer_knapsack::IntegerKnapsack;
38pub use maximum_set_packing::MaximumSetPacking;
39pub use minimum_cardinality_key::MinimumCardinalityKey;
40pub use minimum_hitting_set::MinimumHittingSet;
41pub use minimum_set_covering::MinimumSetCovering;
42pub use prime_attribute_name::PrimeAttributeName;
43pub use rooted_tree_storage_assignment::RootedTreeStorageAssignment;
44pub use set_basis::SetBasis;
45pub use set_splitting::SetSplitting;
46pub use three_dimensional_matching::ThreeDimensionalMatching;
47pub use two_dimensional_consecutive_sets::TwoDimensionalConsecutiveSets;
48
49#[cfg(feature = "example-db")]
50pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
51    let mut specs = Vec::new();
52    specs.extend(comparative_containment::canonical_model_example_specs());
53    specs.extend(consecutive_sets::canonical_model_example_specs());
54    specs.extend(exact_cover_by_3_sets::canonical_model_example_specs());
55    specs.extend(integer_knapsack::canonical_model_example_specs());
56    specs.extend(maximum_set_packing::canonical_model_example_specs());
57    specs.extend(minimum_cardinality_key::canonical_model_example_specs());
58    specs.extend(minimum_hitting_set::canonical_model_example_specs());
59    specs.extend(minimum_set_covering::canonical_model_example_specs());
60    specs.extend(prime_attribute_name::canonical_model_example_specs());
61    specs.extend(rooted_tree_storage_assignment::canonical_model_example_specs());
62    specs.extend(set_basis::canonical_model_example_specs());
63    specs.extend(set_splitting::canonical_model_example_specs());
64    specs.extend(three_dimensional_matching::canonical_model_example_specs());
65    specs.extend(two_dimensional_consecutive_sets::canonical_model_example_specs());
66    specs
67}
problemreductions/models/set/mod.rs

problemreductions/models/set/
mod.rs
