argumentation/semantics/
semi_stable.rs

1//! Semi-stable extensions: complete extensions with maximal range.
2//!
3//! Range of a set S = S ∪ {a | a is attacked by some member of S}.
4//! Semi-stable extensions are complete extensions with subset-maximal range
5//! (Caminada 2006).
6
7use crate::framework::ArgumentationFramework;
8use std::collections::HashSet;
9use std::hash::Hash;
10
11impl<A: Clone + Eq + Hash + Ord> ArgumentationFramework<A> {
12    /// Enumerate all semi-stable extensions.
13    ///
14    /// Returns [`crate::Error::TooLarge`] for frameworks above the enumeration limit.
15    pub fn semi_stable_extensions(&self) -> Result<Vec<HashSet<A>>, crate::Error> {
16        let complete = self.complete_extensions()?;
17        if complete.is_empty() {
18            return Ok(Vec::new());
19        }
20        let ranges: Vec<(HashSet<A>, HashSet<A>)> = complete
21            .into_iter()
22            .map(|ext| {
23                let mut range = ext.clone();
24                for a in &ext {
25                    for target in self.attacked_by(a) {
26                        range.insert(target.clone());
27                    }
28                }
29                (ext, range)
30            })
31            .collect();
32        Ok(ranges
33            .iter()
34            .filter(|(_, r)| {
35                !ranges
36                    .iter()
37                    .any(|(_, other)| other.len() > r.len() && r.is_subset(other))
38            })
39            .map(|(ext, _)| ext.clone())
40            .collect())
41    }
42}
43
44#[cfg(test)]
45mod tests {
46    use super::*;
47
48    #[test]
49    fn semi_stable_of_figure_1_is_ac() {
50        let mut af = ArgumentationFramework::new();
51        af.add_argument("a");
52        af.add_argument("b");
53        af.add_argument("c");
54        af.add_attack(&"a", &"b").unwrap();
55        af.add_attack(&"b", &"c").unwrap();
56        let sse = af.semi_stable_extensions().unwrap();
57        assert_eq!(sse.len(), 1);
58        let expected: HashSet<&str> = ["a", "c"].into_iter().collect();
59        assert!(sse.contains(&expected));
60    }
61
62    #[test]
63    fn semi_stable_exists_even_without_stable() {
64        let mut af = ArgumentationFramework::new();
65        af.add_argument("a");
66        af.add_argument("b");
67        af.add_argument("c");
68        af.add_attack(&"a", &"b").unwrap();
69        af.add_attack(&"b", &"c").unwrap();
70        af.add_attack(&"c", &"a").unwrap();
71        let sse = af.semi_stable_extensions().unwrap();
72        assert!(!sse.is_empty());
73    }
74}
argumentation/semantics/semi_stable.rs

argumentation/semantics/
semi_stable.rs
