problemreductions/models/graph/
kernel.rs

1//! Kernel problem implementation.
2//!
3//! The Kernel problem asks whether a directed graph contains a kernel, i.e.,
4//! a subset of vertices that is both independent (no arc between any two
5//! selected vertices) and absorbing (every unselected vertex has an arc to
6//! some selected vertex).
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::topology::DirectedGraph;
10use crate::traits::Problem;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "Kernel",
16        display_name: "Kernel",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Graph,
20        module_path: module_path!(),
21        description: "Does the directed graph contain a kernel (independent and absorbing vertex subset)?",
22        fields: &[
23            FieldInfo { name: "graph", type_name: "DirectedGraph", description: "The directed graph G=(V,A)" },
24        ],
25    }
26}
27
28/// The Kernel problem.
29///
30/// Given a directed graph G = (V, A), find a kernel V' ⊆ V such that:
31/// 1. **Independence:** no two vertices in V' are joined by an arc (neither
32///    (u,v) nor (v,u) is in A for any u,v ∈ V').
33/// 2. **Absorption:** every vertex u ∉ V' has an arc to some vertex v ∈ V'
34///    (i.e., (u,v) ∈ A).
35///
36/// # Representation
37///
38/// A configuration is a binary vector of length |V|, where `config[v] = 1`
39/// means vertex v is selected into V'.
40///
41/// # Example
42///
43/// ```
44/// use problemreductions::models::graph::Kernel;
45/// use problemreductions::topology::DirectedGraph;
46/// use problemreductions::{Problem, BruteForce};
47///
48/// let graph = DirectedGraph::new(5, vec![
49///     (0,1),(0,2),(1,3),(2,3),(3,4),(4,0),(4,1),
50/// ]);
51/// let problem = Kernel::new(graph);
52/// let solver = BruteForce::new();
53/// let solution = solver.solve(&problem).unwrap();
54/// assert!(solution.is_some());
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct Kernel {
58    graph: DirectedGraph,
59}
60
61impl Kernel {
62    /// Create a new Kernel problem from a directed graph.
63    pub fn new(graph: DirectedGraph) -> Self {
64        Self { graph }
65    }
66
67    /// Get a reference to the underlying directed graph.
68    pub fn graph(&self) -> &DirectedGraph {
69        &self.graph
70    }
71
72    /// Get the number of vertices in the directed graph.
73    pub fn num_vertices(&self) -> usize {
74        self.graph.num_vertices()
75    }
76
77    /// Get the number of arcs in the directed graph.
78    pub fn num_arcs(&self) -> usize {
79        self.graph.num_arcs()
80    }
81}
82
83impl Problem for Kernel {
84    const NAME: &'static str = "Kernel";
85    type Solution = Vec<bool>;
86    type Value = crate::types::Or;
87
88    crate::problem_parameters![("num_arcs", num_arcs), ("num_vertices", num_vertices),];
89
90    fn variant() -> Vec<(&'static str, &'static str)> {
91        crate::variant_params![]
92    }
93
94    fn evaluate(
95        &self,
96        config: &Self::Solution,
97    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
98        if config.len() != self.graph.num_vertices() {
99            return Err(crate::traits::EvaluationError::InvalidConfiguration(
100                "vertex-selection length does not match the graph".into(),
101            ));
102        }
103        Ok({
104            let n = self.graph.num_vertices();
105
106            // Collect selected vertices
107            let selected = config;
108
109            // Independence: no arc between any two selected vertices
110            for u in 0..n {
111                if !selected[u] {
112                    continue;
113                }
114                // Check that no successor of u is also selected
115                for &v in &self.graph.successors(u) {
116                    if selected[v] {
117                        return Ok(crate::types::Or(false));
118                    }
119                }
120            }
121
122            // Absorption: every unselected vertex must have an arc to some selected vertex
123            for u in 0..n {
124                if selected[u] {
125                    continue;
126                }
127                let has_arc_to_selected = self.graph.successors(u).iter().any(|&v| selected[v]);
128                if !has_arc_to_selected {
129                    return Ok(crate::types::Or(false));
130                }
131            }
132
133            crate::types::Or(true)
134        })
135    }
136}
137
138impl crate::solvers::BruteForceProblem for Kernel {
139    fn dimensions(&self) -> Vec<usize> {
140        vec![2; self.graph.num_vertices()]
141    }
142}
143
144#[cfg(feature = "example-db")]
145pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
146    // 5 vertices, arcs: (0,1),(0,2),(1,3),(2,3),(3,4),(4,0),(4,1)
147    // Kernel: V' = {0, 3}.
148    let graph = DirectedGraph::new(
149        5,
150        vec![(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 0), (4, 1)],
151    );
152    let optimal_config = vec![true, false, false, true, false];
153    vec![crate::example_db::specs::ModelExampleSpec {
154        id: "kernel",
155        instance: Box::new(Kernel::new(graph)),
156        optimal_config: serde_json::to_value(optimal_config)
157            .expect("solution serialization must succeed"),
158        optimal_value: serde_json::json!(true),
159    }]
160}
161
162crate::declare_variants! {
163    default Kernel => "2^num_vertices",
164}
165
166crate::register_brute_force! {
167    Kernel decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
168}
169
170#[cfg(test)]
171#[path = "../../unit_tests/models/graph/kernel.rs"]
172mod tests;
problemreductions/models/graph/kernel.rs

problemreductions/models/graph/
kernel.rs
