argumentation/semantics/
labelling.rs

1//! Caminada three-valued labellings and their correspondence with extensions.
2//!
3//! Per Caminada 2006: every argument is labelled IN, OUT, or UNDEC.
4//! - IN iff all attackers are OUT
5//! - OUT iff some attacker is IN
6//! - UNDEC otherwise
7//!
8//! Complete labellings correspond to complete extensions.
9
10use crate::framework::ArgumentationFramework;
11use std::collections::{HashMap, HashSet};
12use std::hash::Hash;
13
14/// The label assigned to an argument under a Caminada labelling.
15#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
16pub enum Label {
17    /// Accepted.
18    In,
19    /// Rejected.
20    Out,
21    /// Undecided.
22    Undec,
23}
24
25impl std::fmt::Display for Label {
26    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
27        match self {
28            Label::In => write!(f, "in"),
29            Label::Out => write!(f, "out"),
30            Label::Undec => write!(f, "undec"),
31        }
32    }
33}
34
35/// A complete three-valued labelling.
36#[derive(Debug, Clone, PartialEq, Eq)]
37pub struct Labelling<A: Clone + Eq + Hash> {
38    labels: HashMap<A, Label>,
39}
40
41impl<A: Clone + Eq + Hash> Labelling<A> {
42    /// Get the label for an argument, or `None` if not labelled.
43    pub fn label_of(&self, a: &A) -> Option<Label> {
44        self.labels.get(a).copied()
45    }
46
47    /// Get all arguments with the `In` label (= the extension).
48    #[must_use]
49    pub fn in_set(&self) -> HashSet<A> {
50        self.collect_with(Label::In)
51    }
52
53    /// Get all arguments with the `Out` label (= rejected).
54    #[must_use]
55    pub fn out_set(&self) -> HashSet<A> {
56        self.collect_with(Label::Out)
57    }
58
59    /// Get all arguments with the `Undec` label (= undecided).
60    #[must_use]
61    pub fn undec_set(&self) -> HashSet<A> {
62        self.collect_with(Label::Undec)
63    }
64
65    fn collect_with(&self, want: Label) -> HashSet<A> {
66        self.labels
67            .iter()
68            .filter(|(_, l)| **l == want)
69            .map(|(a, _)| a.clone())
70            .collect()
71    }
72}
73
74impl<A: Clone + Eq + Hash + Ord> ArgumentationFramework<A> {
75    /// Compute the labelling corresponding to a given extension.
76    ///
77    /// An argument is `In` iff in the extension; `Out` iff attacked by
78    /// something in the extension; `Undec` otherwise.
79    pub fn extension_to_labelling(&self, ext: &HashSet<A>) -> Labelling<A> {
80        let mut labels = HashMap::new();
81        for a in self.arguments() {
82            if ext.contains(a) {
83                labels.insert(a.clone(), Label::In);
84            } else if self.attackers(a).iter().any(|att| ext.contains(*att)) {
85                labels.insert(a.clone(), Label::Out);
86            } else {
87                labels.insert(a.clone(), Label::Undec);
88            }
89        }
90        Labelling { labels }
91    }
92
93    /// Return labellings corresponding to all complete extensions.
94    ///
95    /// Propagates [`crate::Error::TooLarge`] from `complete_extensions`.
96    pub fn complete_labellings(&self) -> Result<Vec<Labelling<A>>, crate::Error> {
97        Ok(self
98            .complete_extensions()?
99            .iter()
100            .map(|ext| self.extension_to_labelling(ext))
101            .collect())
102    }
103
104    /// Compute the labelling corresponding to the grounded extension.
105    pub fn grounded_labelling(&self) -> Labelling<A> {
106        let ext = self.grounded_extension();
107        self.extension_to_labelling(&ext)
108    }
109
110    /// Compute labellings corresponding to all preferred extensions.
111    pub fn preferred_labellings(&self) -> Result<Vec<Labelling<A>>, crate::Error> {
112        Ok(self
113            .preferred_extensions()?
114            .iter()
115            .map(|ext| self.extension_to_labelling(ext))
116            .collect())
117    }
118
119    /// Compute labellings corresponding to all stable extensions.
120    pub fn stable_labellings(&self) -> Result<Vec<Labelling<A>>, crate::Error> {
121        Ok(self
122            .stable_extensions()?
123            .iter()
124            .map(|ext| self.extension_to_labelling(ext))
125            .collect())
126    }
127
128    /// Compute the labelling corresponding to the ideal extension.
129    pub fn ideal_labelling(&self) -> Result<Labelling<A>, crate::Error> {
130        let ext = self.ideal_extension()?;
131        Ok(self.extension_to_labelling(&ext))
132    }
133
134    /// Compute labellings corresponding to all semi-stable extensions.
135    pub fn semi_stable_labellings(&self) -> Result<Vec<Labelling<A>>, crate::Error> {
136        Ok(self
137            .semi_stable_extensions()?
138            .iter()
139            .map(|ext| self.extension_to_labelling(ext))
140            .collect())
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147
148    #[test]
149    fn labelling_of_figure_1_is_in_out_in() {
150        let mut af = ArgumentationFramework::new();
151        af.add_argument("a");
152        af.add_argument("b");
153        af.add_argument("c");
154        af.add_attack(&"a", &"b").unwrap();
155        af.add_attack(&"b", &"c").unwrap();
156        let ext: HashSet<&str> = ["a", "c"].into_iter().collect();
157        let lab = af.extension_to_labelling(&ext);
158        assert_eq!(lab.label_of(&"a"), Some(Label::In));
159        assert_eq!(lab.label_of(&"b"), Some(Label::Out));
160        assert_eq!(lab.label_of(&"c"), Some(Label::In));
161    }
162
163    #[test]
164    fn labelling_in_set_matches_extension() {
165        let mut af = ArgumentationFramework::new();
166        af.add_argument("a");
167        af.add_argument("b");
168        af.add_attack(&"a", &"b").unwrap();
169        let ext: HashSet<&str> = ["a"].into_iter().collect();
170        let lab = af.extension_to_labelling(&ext);
171        assert_eq!(lab.in_set(), ext);
172    }
173
174    #[test]
175    fn grounded_labelling_of_chain_is_alternating() {
176        let mut af = ArgumentationFramework::new();
177        af.add_argument("a");
178        af.add_argument("b");
179        af.add_argument("c");
180        af.add_attack(&"a", &"b").unwrap();
181        af.add_attack(&"b", &"c").unwrap();
182        let labelling = af.grounded_labelling();
183        assert_eq!(labelling.label_of(&"a"), Some(Label::In));
184        assert_eq!(labelling.label_of(&"b"), Some(Label::Out));
185        assert_eq!(labelling.label_of(&"c"), Some(Label::In));
186    }
187
188    #[test]
189    fn preferred_labellings_of_mutual_attack_has_two() {
190        // Mutual attack a↔b: preferred extensions = [{a}, {b}], so preferred
191        // labellings = [{a=in,b=out}, {a=out,b=in}]. Two, not three.
192        let mut af = ArgumentationFramework::new();
193        af.add_argument("a");
194        af.add_argument("b");
195        af.add_attack(&"a", &"b").unwrap();
196        af.add_attack(&"b", &"a").unwrap();
197        let labellings = af.preferred_labellings().unwrap();
198        assert_eq!(labellings.len(), 2);
199    }
200
201    #[test]
202    fn stable_labellings_match_stable_extensions() {
203        let mut af = ArgumentationFramework::new();
204        af.add_argument("a");
205        af.add_argument("b");
206        af.add_argument("c");
207        af.add_attack(&"a", &"b").unwrap();
208        af.add_attack(&"b", &"c").unwrap();
209        let extensions = af.stable_extensions().unwrap();
210        let labellings = af.stable_labellings().unwrap();
211        assert_eq!(extensions.len(), labellings.len());
212        for (ext, lab) in extensions.iter().zip(labellings.iter()) {
213            assert_eq!(&lab.in_set(), ext);
214        }
215    }
216
217    #[test]
218    fn ideal_labelling_roundtrip() {
219        let mut af = ArgumentationFramework::new();
220        af.add_argument("a");
221        af.add_argument("b");
222        af.add_argument("c");
223        af.add_attack(&"a", &"b").unwrap();
224        af.add_attack(&"b", &"c").unwrap();
225        let extension = af.ideal_extension().unwrap();
226        let labelling = af.ideal_labelling().unwrap();
227        assert_eq!(labelling.in_set(), extension);
228    }
229
230    #[test]
231    fn semi_stable_labellings_match_semi_stable_extensions() {
232        let mut af = ArgumentationFramework::new();
233        af.add_argument("a");
234        af.add_argument("b");
235        af.add_attack(&"a", &"b").unwrap();
236        af.add_attack(&"b", &"a").unwrap();
237        let ext_count = af.semi_stable_extensions().unwrap().len();
238        let lab_count = af.semi_stable_labellings().unwrap().len();
239        assert_eq!(ext_count, lab_count);
240    }
241
242    #[test]
243    fn label_displays_as_lowercase_word() {
244        assert_eq!(format!("{}", Label::In), "in");
245        assert_eq!(format!("{}", Label::Out), "out");
246        assert_eq!(format!("{}", Label::Undec), "undec");
247    }
248}
argumentation/semantics/labelling.rs

argumentation/semantics/
labelling.rs
