argumentation/semantics/
preferred.rs

1//! Preferred extensions: maximal (subset-maximal) admissible sets.
2
3use super::subset_enum::{sorted_args_or_too_large, subset_from_bits};
4use crate::framework::ArgumentationFramework;
5use std::collections::HashSet;
6use std::hash::Hash;
7
8impl<A: Clone + Eq + Hash + Ord> ArgumentationFramework<A> {
9    /// Enumerate all preferred extensions.
10    ///
11    /// A preferred extension is a subset-maximal admissible set.
12    /// Every argumentation framework has at least one preferred extension.
13    ///
14    /// Returns [`crate::Error::TooLarge`] for frameworks above the
15    /// enumeration limit.
16    pub fn preferred_extensions(&self) -> Result<Vec<HashSet<A>>, crate::Error> {
17        let args = sorted_args_or_too_large(self)?;
18        let n = args.len();
19        let mut admissible: Vec<HashSet<A>> = Vec::new();
20        for bits in 0u64..(1u64 << n) {
21            let s = subset_from_bits(&args, bits);
22            if self.is_admissible(&s) {
23                admissible.push(s);
24            }
25        }
26        Ok(admissible
27            .iter()
28            .filter(|s| {
29                !admissible
30                    .iter()
31                    .any(|t| t.len() > s.len() && s.is_subset(t))
32            })
33            .cloned()
34            .collect())
35    }
36}
37
38#[cfg(test)]
39mod tests {
40    use super::*;
41
42    #[test]
43    fn preferred_of_figure_1_is_singleton_ac() {
44        let mut af = ArgumentationFramework::new();
45        af.add_argument("a");
46        af.add_argument("b");
47        af.add_argument("c");
48        af.add_attack(&"a", &"b").unwrap();
49        af.add_attack(&"b", &"c").unwrap();
50        let pe = af.preferred_extensions().unwrap();
51        assert_eq!(pe.len(), 1);
52        let expected: HashSet<&str> = ["a", "c"].into_iter().collect();
53        assert!(pe.contains(&expected));
54    }
55
56    #[test]
57    fn preferred_of_mutual_attack_is_two() {
58        let mut af = ArgumentationFramework::new();
59        af.add_argument("a");
60        af.add_argument("b");
61        af.add_attack(&"a", &"b").unwrap();
62        af.add_attack(&"b", &"a").unwrap();
63        let pe = af.preferred_extensions().unwrap();
64        assert_eq!(pe.len(), 2);
65    }
66
67    #[test]
68    fn every_framework_has_a_preferred_extension() {
69        let mut af = ArgumentationFramework::new();
70        af.add_argument("a");
71        af.add_argument("b");
72        af.add_argument("c");
73        af.add_attack(&"a", &"b").unwrap();
74        af.add_attack(&"b", &"c").unwrap();
75        af.add_attack(&"c", &"a").unwrap();
76        let pe = af.preferred_extensions().unwrap();
77        assert!(!pe.is_empty());
78    }
79}
argumentation/semantics/preferred.rs

argumentation/semantics/
preferred.rs
