problemreductions/models/graph/
mod.rs

1//! Graph-based optimization problems.
2//!
3//! This module contains NP-hard problems defined on graphs:
4//! - [`IndependentSet`]: Maximum weight independent set
5//! - [`MaximalIS`]: Maximal independent set
6//! - [`VertexCovering`]: Minimum weight vertex cover
7//! - [`DominatingSet`]: Minimum dominating set
8//! - [`MaxCut`]: Maximum cut on weighted graphs
9//! - [`Coloring`]: K-vertex coloring
10//! - [`Matching`]: Maximum weight matching
11//!
12//! ## Using the Template
13//!
14//! New graph problems can be defined using the [`GraphProblem`] template by
15//! implementing the [`GraphConstraint`] trait:
16//!
17//! ```rust,ignore
18//! use problemreductions::models::graph::{GraphProblem, GraphConstraint};
19//!
20//! // Define a new graph problem constraint
21//! struct MyConstraint;
22//! impl GraphConstraint for MyConstraint {
23//!     // ... implement required methods
24//! }
25//!
26//! // Create a type alias for convenience
27//! type MyProblem<W = i32> = GraphProblem<MyConstraint, W>;
28//! ```
29
30mod coloring;
31mod dominating_set;
32mod independent_set;
33mod matching;
34mod max_cut;
35mod maximal_is;
36pub mod template;
37mod vertex_covering;
38
39pub use coloring::{is_valid_coloring, Coloring};
40pub use dominating_set::{is_dominating_set, DominatingSet};
41pub use independent_set::{is_independent_set, IndependentSet};
42pub use matching::{is_matching, Matching};
43pub use max_cut::{cut_size, MaxCut};
44pub use maximal_is::{is_maximal_independent_set, MaximalIS};
45pub use template::{
46    CliqueConstraint, CliqueT, GraphConstraint, GraphProblem, IndependentSetConstraint,
47    IndependentSetT, VertexCoverConstraint, VertexCoverT,
48};
49pub use vertex_covering::{is_vertex_cover, VertexCovering};