argumentation_bipolar/
coalition.rs

1//! Coalition detection on the support graph.
2//!
3//! A **coalition** is a strongly-connected component of the support
4//! graph: a set of arguments where every pair mutually supports each
5//! other, directly or transitively. Singleton SCCs (arguments with no
6//! mutual support) are also returned as coalitions of size 1.
7//!
8//! Uses petgraph's Tarjan SCC implementation, which is O(V + E).
9
10use crate::framework::BipolarFramework;
11use crate::types::CoalitionId;
12use petgraph::algo::tarjan_scc;
13use petgraph::graph::DiGraph;
14use std::collections::HashMap;
15use std::hash::Hash;
16
17/// A detected coalition with its member arguments.
18#[derive(Debug, Clone)]
19pub struct Coalition<A: Clone + Eq + Hash> {
20    /// Assigned identifier — stable only within a single
21    /// [`detect_coalitions`] call.
22    pub id: CoalitionId,
23    /// The arguments in this coalition. For a singleton coalition this
24    /// has exactly one element.
25    pub members: Vec<A>,
26}
27
28/// Detect all coalitions in a bipolar framework.
29///
30/// Builds a petgraph `DiGraph` from the support edges (ignoring
31/// attacks), runs Tarjan's SCC algorithm, and returns one [`Coalition`]
32/// per SCC with a freshly-assigned [`CoalitionId`].
33///
34/// Coalition ids are assigned in the order petgraph's SCC iterator
35/// returns them, which is a reverse topological order over the
36/// condensation. Consumers should treat ids as opaque and use
37/// [`Coalition::members`] to identify coalitions semantically.
38pub fn detect_coalitions<A>(framework: &BipolarFramework<A>) -> Vec<Coalition<A>>
39where
40    A: Clone + Eq + Hash,
41{
42    let mut graph: DiGraph<A, ()> = DiGraph::new();
43    let mut index: HashMap<A, petgraph::graph::NodeIndex> = HashMap::new();
44
45    for arg in framework.arguments() {
46        let idx = graph.add_node(arg.clone());
47        index.insert(arg.clone(), idx);
48    }
49    for (sup, supd) in framework.supports() {
50        let (Some(&a), Some(&b)) = (index.get(sup), index.get(supd)) else {
51            continue;
52        };
53        graph.add_edge(a, b, ());
54    }
55
56    tarjan_scc(&graph)
57        .into_iter()
58        .enumerate()
59        .map(|(i, component)| Coalition {
60            id: CoalitionId(i as u32),
61            members: component.into_iter().map(|n| graph[n].clone()).collect(),
62        })
63        .collect()
64}
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn isolated_arguments_are_singleton_coalitions() {
72        let mut bf = BipolarFramework::new();
73        bf.add_argument("a");
74        bf.add_argument("b");
75        bf.add_argument("c");
76        let coalitions = detect_coalitions(&bf);
77        assert_eq!(coalitions.len(), 3);
78        for c in &coalitions {
79            assert_eq!(c.members.len(), 1);
80        }
81    }
82
83    #[test]
84    fn mutual_support_produces_one_coalition_of_two() {
85        let mut bf = BipolarFramework::new();
86        bf.add_support("alice", "bob").unwrap();
87        bf.add_support("bob", "alice").unwrap();
88        let coalitions = detect_coalitions(&bf);
89        // Expect one coalition {alice, bob}, no other singletons.
90        assert_eq!(coalitions.len(), 1);
91        assert_eq!(coalitions[0].members.len(), 2);
92        assert!(coalitions[0].members.contains(&"alice"));
93        assert!(coalitions[0].members.contains(&"bob"));
94    }
95
96    #[test]
97    fn one_way_support_is_two_singletons() {
98        // a → b support (but no b → a) is NOT a coalition under SCC.
99        let mut bf = BipolarFramework::new();
100        bf.add_support("a", "b").unwrap();
101        let coalitions = detect_coalitions(&bf);
102        assert_eq!(coalitions.len(), 2);
103        for c in &coalitions {
104            assert_eq!(c.members.len(), 1);
105        }
106    }
107
108    #[test]
109    fn attack_edges_do_not_create_coalitions() {
110        let mut bf = BipolarFramework::new();
111        bf.add_attack("alice", "bob");
112        bf.add_attack("bob", "alice"); // mutual attack, not mutual support
113        let coalitions = detect_coalitions(&bf);
114        assert_eq!(coalitions.len(), 2);
115    }
116
117    #[test]
118    fn three_way_mutual_support_forms_one_coalition() {
119        let mut bf = BipolarFramework::new();
120        bf.add_support("a", "b").unwrap();
121        bf.add_support("b", "c").unwrap();
122        bf.add_support("c", "a").unwrap();
123        let coalitions = detect_coalitions(&bf);
124        assert_eq!(coalitions.len(), 1);
125        assert_eq!(coalitions[0].members.len(), 3);
126    }
127
128    #[test]
129    fn coalition_ids_are_distinct() {
130        let mut bf = BipolarFramework::new();
131        bf.add_argument("a");
132        bf.add_argument("b");
133        bf.add_argument("c");
134        let coalitions = detect_coalitions(&bf);
135        let ids: std::collections::HashSet<_> = coalitions.iter().map(|c| c.id).collect();
136        assert_eq!(ids.len(), coalitions.len());
137    }
138}
argumentation_bipolar/coalition.rs

argumentation_bipolar/
coalition.rs
