problemreductions/rules/
analysis.rs

1//! Topology analysis utilities for the reduction graph.
2
3use crate::rules::graph::ReductionGraph;
4use std::collections::{BTreeMap, BTreeSet};
5
6// ────────── Topology checks ──────────
7
8/// Result of checking graph connectivity at the problem-type level.
9#[derive(Debug, Clone)]
10pub struct ConnectivityReport {
11    /// Total number of problem types in the graph.
12    pub total_types: usize,
13    /// Total number of registered reductions.
14    pub total_reductions: usize,
15    /// Problem types with no reductions in or out.
16    pub isolated: Vec<IsolatedProblem>,
17    /// Connected components (sorted largest first). Each component is a sorted
18    /// list of problem type names.
19    pub components: Vec<Vec<&'static str>>,
20}
21
22/// An isolated problem type with its variant count.
23#[derive(Debug, Clone)]
24pub struct IsolatedProblem {
25    pub name: &'static str,
26    pub num_variants: usize,
27    /// Per-variant complexity strings (if available).
28    pub variant_complexities: Vec<(BTreeMap<String, String>, Option<String>)>,
29}
30
31/// Check reduction graph connectivity: find isolated problems and connected components.
32pub fn check_connectivity(graph: &ReductionGraph) -> ConnectivityReport {
33    let mut types = graph.problem_types();
34    types.sort();
35
36    // Build undirected adjacency at the problem-type level
37    let mut adj: BTreeMap<&str, BTreeSet<&str>> = BTreeMap::new();
38    for &name in &types {
39        adj.entry(name).or_default();
40        for edge in graph.outgoing_reductions(name) {
41            adj.entry(name).or_default().insert(edge.target_name);
42            adj.entry(edge.target_name).or_default().insert(name);
43        }
44    }
45
46    // Find connected components via BFS
47    let mut visited: BTreeSet<&str> = BTreeSet::new();
48    let mut components: Vec<Vec<&str>> = Vec::new();
49
50    for &name in &types {
51        if visited.contains(name) {
52            continue;
53        }
54        let mut component = Vec::new();
55        let mut queue = std::collections::VecDeque::new();
56        queue.push_back(name);
57        visited.insert(name);
58
59        while let Some(current) = queue.pop_front() {
60            component.push(current);
61            if let Some(neighbors) = adj.get(current) {
62                for &neighbor in neighbors {
63                    if visited.insert(neighbor) {
64                        queue.push_back(neighbor);
65                    }
66                }
67            }
68        }
69        component.sort();
70        components.push(component);
71    }
72
73    components.sort_by_key(|c| std::cmp::Reverse(c.len()));
74
75    let isolated: Vec<IsolatedProblem> = types
76        .iter()
77        .copied()
78        .filter(|name| adj.get(name).is_some_and(|n| n.is_empty()))
79        .map(|name| {
80            let variants = graph.variants_for(name);
81            let variant_complexities = variants
82                .iter()
83                .map(|v| {
84                    let c = graph.variant_complexity(name, v).map(|e| e.to_string());
85                    (v.clone(), c)
86                })
87                .collect();
88            IsolatedProblem {
89                name,
90                num_variants: variants.len(),
91                variant_complexities,
92            }
93        })
94        .collect();
95
96    ConnectivityReport {
97        total_types: types.len(),
98        total_reductions: graph.num_reductions(),
99        isolated,
100        components,
101    }
102}
103
104/// Classification of a problem type that is unreachable from 3-SAT.
105#[derive(Debug, Clone, PartialEq, Eq)]
106pub enum UnreachableReason {
107    /// Known to be solvable in polynomial time.
108    InP,
109    /// Intermediate complexity (e.g., Factoring — believed neither in P nor NP-complete).
110    Intermediate,
111    /// No reductions at all (orphan).
112    Orphan,
113    /// NP-hard but missing a proof chain from 3-SAT.
114    MissingProofChain,
115}
116
117/// A problem type not reachable from 3-SAT via directed reduction paths.
118#[derive(Debug, Clone)]
119pub struct UnreachableProblem {
120    pub name: &'static str,
121    pub reason: UnreachableReason,
122    pub outgoing_count: usize,
123    pub incoming_count: usize,
124}
125
126/// Result of checking NP-hardness proof chains from 3-SAT.
127#[derive(Debug, Clone)]
128pub struct ReachabilityReport {
129    /// Total number of problem types.
130    pub total_types: usize,
131    /// Problem types reachable from 3-SAT, with minimum hop distance.
132    pub reachable: BTreeMap<&'static str, usize>,
133    /// Problem types not reachable, classified by reason.
134    pub unreachable: Vec<UnreachableProblem>,
135}
136
137impl ReachabilityReport {
138    /// Returns only the problems that are NP-hard but missing a proof chain.
139    pub fn missing_proof_chains(&self) -> Vec<&UnreachableProblem> {
140        self.unreachable
141            .iter()
142            .filter(|p| p.reason == UnreachableReason::MissingProofChain)
143            .collect()
144    }
145}
146
147/// Check which problems are reachable from 3-SAT (KSatisfiability) via directed
148/// reduction paths. Problems without such a path are classified as P-time,
149/// intermediate, orphan, or missing a proof chain.
150pub fn check_reachability_from_3sat(graph: &ReductionGraph) -> ReachabilityReport {
151    const SOURCE: &str = "KSatisfiability";
152
153    let mut types = graph.problem_types();
154    types.sort();
155
156    // Build directed adjacency at the type level
157    let mut adj: BTreeMap<&str, BTreeSet<&str>> = BTreeMap::new();
158    for &name in &types {
159        adj.entry(name).or_default();
160        for edge in graph.outgoing_reductions(name) {
161            adj.entry(name).or_default().insert(edge.target_name);
162        }
163    }
164
165    // BFS from 3-SAT following directed edges
166    let mut reachable: BTreeMap<&'static str, usize> = BTreeMap::new();
167    let mut queue: std::collections::VecDeque<(&str, usize)> = std::collections::VecDeque::new();
168    reachable.insert(SOURCE, 0);
169    queue.push_back((SOURCE, 0));
170
171    while let Some((current, hops)) = queue.pop_front() {
172        if let Some(neighbors) = adj.get(current) {
173            for &neighbor in neighbors {
174                if !reachable.contains_key(neighbor) {
175                    reachable.insert(neighbor, hops + 1);
176                    queue.push_back((neighbor, hops + 1));
177                }
178            }
179        }
180    }
181
182    // Known P-time problems and variants
183    let p_time_checks: &[(&str, Option<(&str, &str)>)] = &[
184        ("MaximumMatching", None),
185        ("KSatisfiability", Some(("k", "K2"))),
186        ("KColoring", Some(("graph", "SimpleGraph"))),
187    ];
188
189    let intermediate_names: &[&str] = &["Factoring"];
190
191    let mut unreachable_problems: Vec<UnreachableProblem> = Vec::new();
192
193    for &name in &types {
194        if reachable.contains_key(name) {
195            continue;
196        }
197
198        let out_count = graph.outgoing_reductions(name).len();
199        let in_count = graph.incoming_reductions(name).len();
200
201        // Orphan?
202        if out_count == 0 && in_count == 0 {
203            unreachable_problems.push(UnreachableProblem {
204                name,
205                reason: UnreachableReason::Orphan,
206                outgoing_count: 0,
207                incoming_count: 0,
208            });
209            continue;
210        }
211
212        // Known P-time?
213        let is_p = p_time_checks.iter().any(|(pname, variant_check)| {
214            if *pname != name {
215                return false;
216            }
217            match variant_check {
218                None => true,
219                Some((key, val)) => {
220                    let variants = graph.variants_for(name);
221                    variants.len() == 1 && variants[0].get(*key).map(|s| s.as_str()) == Some(*val)
222                }
223            }
224        });
225        if is_p {
226            unreachable_problems.push(UnreachableProblem {
227                name,
228                reason: UnreachableReason::InP,
229                outgoing_count: out_count,
230                incoming_count: in_count,
231            });
232            continue;
233        }
234
235        // Known intermediate?
236        if intermediate_names.contains(&name) {
237            unreachable_problems.push(UnreachableProblem {
238                name,
239                reason: UnreachableReason::Intermediate,
240                outgoing_count: out_count,
241                incoming_count: in_count,
242            });
243            continue;
244        }
245
246        // NP-hard but missing proof chain
247        unreachable_problems.push(UnreachableProblem {
248            name,
249            reason: UnreachableReason::MissingProofChain,
250            outgoing_count: out_count,
251            incoming_count: in_count,
252        });
253    }
254
255    ReachabilityReport {
256        total_types: types.len(),
257        reachable,
258        unreachable: unreachable_problems,
259    }
260}
261
262#[cfg(test)]
263#[path = "../unit_tests/rules/analysis.rs"]
264mod tests;
problemreductions/rules/analysis.rs

problemreductions/rules/
analysis.rs
