argumentation/semantics/
ideal.rs

1//! Ideal extension: the largest admissible set contained in every preferred
2//! extension (Dung, Mancarella, Toni 2007).
3
4use super::subset_enum::subset_from_bits;
5use crate::framework::ArgumentationFramework;
6use std::collections::HashSet;
7use std::hash::Hash;
8
9impl<A: Clone + Eq + Hash + Ord> ArgumentationFramework<A> {
10    /// Compute the ideal extension.
11    ///
12    /// Defined as the largest admissible subset of the intersection of all
13    /// preferred extensions. Unique. The grounded extension is always a
14    /// subset of the ideal extension.
15    ///
16    /// Returns [`crate::Error::TooLarge`] for frameworks above the enumeration limit.
17    pub fn ideal_extension(&self) -> Result<HashSet<A>, crate::Error> {
18        let preferred = self.preferred_extensions()?;
19        if preferred.is_empty() {
20            return Ok(HashSet::new());
21        }
22        let mut intersection: HashSet<A> = preferred[0].clone();
23        for ext in &preferred[1..] {
24            intersection = intersection.intersection(ext).cloned().collect();
25        }
26        // Power-set over the intersection. Since `preferred_extensions` already
27        // succeeded, we know the framework is within the enumeration limit, so
28        // the intersection is too. Sort for determinism.
29        let mut args: Vec<A> = intersection.into_iter().collect();
30        args.sort();
31        let n = args.len();
32        let mut best: HashSet<A> = HashSet::new();
33        for bits in 0u64..(1u64 << n) {
34            let s = subset_from_bits(&args, bits);
35            if s.len() <= best.len() {
36                continue;
37            }
38            if self.is_admissible(&s) {
39                best = s;
40            }
41        }
42        Ok(best)
43    }
44}
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49
50    #[test]
51    fn ideal_of_figure_1_is_ac() {
52        let mut af = ArgumentationFramework::new();
53        af.add_argument("a");
54        af.add_argument("b");
55        af.add_argument("c");
56        af.add_attack(&"a", &"b").unwrap();
57        af.add_attack(&"b", &"c").unwrap();
58        let ideal = af.ideal_extension().unwrap();
59        let expected: HashSet<&str> = ["a", "c"].into_iter().collect();
60        assert_eq!(ideal, expected);
61    }
62
63    #[test]
64    fn ideal_of_mutual_attack_is_empty() {
65        let mut af = ArgumentationFramework::new();
66        af.add_argument("a");
67        af.add_argument("b");
68        af.add_attack(&"a", &"b").unwrap();
69        af.add_attack(&"b", &"a").unwrap();
70        assert!(af.ideal_extension().unwrap().is_empty());
71    }
72}
argumentation/semantics/ideal.rs

argumentation/semantics/
ideal.rs
