argumentation/semantics/
complete.rs

1//! Complete extensions: admissible sets that contain every argument they defend.
2//!
3//! Enumerated by subset iteration. Exponential in the number of arguments;
4//! scales to ~20 arguments before becoming impractical.
5
6use super::subset_enum::{sorted_args_or_too_large, subset_from_bits};
7use crate::framework::ArgumentationFramework;
8use std::collections::HashSet;
9use std::hash::Hash;
10
11impl<A: Clone + Eq + Hash + Ord> ArgumentationFramework<A> {
12    /// Enumerate all complete extensions via subset search.
13    ///
14    /// **Performance:** `O(2^n)` in the number of arguments. Frameworks with
15    /// more than the internal enumeration limit are rejected with
16    /// [`crate::Error::TooLarge`]; use a SAT-based semantics entry point
17    /// (future work) for larger instances.
18    pub fn complete_extensions(&self) -> Result<Vec<HashSet<A>>, crate::Error> {
19        let args = sorted_args_or_too_large(self)?;
20        let n = args.len();
21        let mut results = Vec::new();
22        for bits in 0u64..(1u64 << n) {
23            let s = subset_from_bits(&args, bits);
24            if !self.is_admissible(&s) {
25                continue;
26            }
27            let defended: HashSet<A> = self
28                .arguments()
29                .filter(|a| self.defends(&s, *a))
30                .cloned()
31                .collect();
32            if defended == s {
33                results.push(s);
34            }
35        }
36        Ok(results)
37    }
38}
39
40#[cfg(test)]
41mod tests {
42    use super::super::subset_enum::ENUMERATION_LIMIT;
43    use super::*;
44
45    #[test]
46    fn complete_of_figure_1_is_singleton_ac() {
47        let mut af = ArgumentationFramework::new();
48        af.add_argument("a");
49        af.add_argument("b");
50        af.add_argument("c");
51        af.add_attack(&"a", &"b").unwrap();
52        af.add_attack(&"b", &"c").unwrap();
53        let ce = af.complete_extensions().unwrap();
54        assert_eq!(ce.len(), 1);
55        let expected: HashSet<&str> = ["a", "c"].into_iter().collect();
56        assert!(ce.contains(&expected));
57    }
58
59    #[test]
60    fn complete_of_mutual_attack_is_three_extensions() {
61        let mut af = ArgumentationFramework::new();
62        af.add_argument("a");
63        af.add_argument("b");
64        af.add_attack(&"a", &"b").unwrap();
65        af.add_attack(&"b", &"a").unwrap();
66        let ce = af.complete_extensions().unwrap();
67        assert_eq!(ce.len(), 3);
68        let empty: HashSet<&str> = HashSet::new();
69        let a_only: HashSet<&str> = ["a"].into_iter().collect();
70        let b_only: HashSet<&str> = ["b"].into_iter().collect();
71        assert!(ce.contains(&empty));
72        assert!(ce.contains(&a_only));
73        assert!(ce.contains(&b_only));
74    }
75
76    #[test]
77    fn complete_always_contains_grounded() {
78        let mut af = ArgumentationFramework::new();
79        af.add_argument("a");
80        af.add_argument("b");
81        af.add_argument("c");
82        af.add_attack(&"a", &"b").unwrap();
83        af.add_attack(&"b", &"c").unwrap();
84        let grounded = af.grounded_extension();
85        let complete = af.complete_extensions().unwrap();
86        for ext in &complete {
87            assert!(grounded.iter().all(|g| ext.contains(g)));
88        }
89    }
90
91    #[test]
92    fn complete_rejects_frameworks_above_limit() {
93        let mut af = ArgumentationFramework::new();
94        for i in 0..(ENUMERATION_LIMIT + 1) {
95            af.add_argument(format!("a{}", i));
96        }
97        let result = af.complete_extensions();
98        assert!(matches!(result, Err(crate::Error::TooLarge { .. })));
99    }
100}
argumentation/semantics/complete.rs

argumentation/semantics/
complete.rs
