proof_engine/graph/
hypergraph.rs

1use glam::Vec2;
2use std::collections::{HashMap, HashSet};
3use super::graph_core::{Graph, GraphKind, NodeId};
4
5#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
6pub struct HyperedgeId(pub u32);
7
8#[derive(Debug, Clone)]
9pub struct HypernodeData<N> {
10    pub id: NodeId,
11    pub data: N,
12    pub position: Vec2,
13}
14
15#[derive(Debug, Clone)]
16pub struct HyperedgeData {
17    pub id: HyperedgeId,
18    pub members: Vec<NodeId>,
19    pub color: [f32; 4], // RGBA
20}
21
22#[derive(Debug, Clone)]
23pub struct Hypergraph<N> {
24    nodes: HashMap<NodeId, HypernodeData<N>>,
25    hyperedges: HashMap<HyperedgeId, HyperedgeData>,
26    next_node_id: u32,
27    next_edge_id: u32,
28}
29
30impl<N> Hypergraph<N> {
31    pub fn new() -> Self {
32        Self {
33            nodes: HashMap::new(),
34            hyperedges: HashMap::new(),
35            next_node_id: 0,
36            next_edge_id: 0,
37        }
38    }
39
40    pub fn add_node(&mut self, data: N, position: Vec2) -> NodeId {
41        let id = NodeId(self.next_node_id);
42        self.next_node_id += 1;
43        self.nodes.insert(id, HypernodeData { id, data, position });
44        id
45    }
46
47    pub fn add_hyperedge(&mut self, members: Vec<NodeId>) -> HyperedgeId {
48        self.add_hyperedge_colored(members, [0.3, 0.5, 0.8, 0.3])
49    }
50
51    pub fn add_hyperedge_colored(&mut self, members: Vec<NodeId>, color: [f32; 4]) -> HyperedgeId {
52        let id = HyperedgeId(self.next_edge_id);
53        self.next_edge_id += 1;
54        self.hyperedges.insert(id, HyperedgeData { id, members, color });
55        id
56    }
57
58    pub fn remove_node(&mut self, id: NodeId) {
59        self.nodes.remove(&id);
60        // Remove from all hyperedges
61        for he in self.hyperedges.values_mut() {
62            he.members.retain(|&m| m != id);
63        }
64        // Remove empty hyperedges
65        self.hyperedges.retain(|_, he| !he.members.is_empty());
66    }
67
68    pub fn remove_hyperedge(&mut self, id: HyperedgeId) {
69        self.hyperedges.remove(&id);
70    }
71
72    pub fn node_count(&self) -> usize {
73        self.nodes.len()
74    }
75
76    pub fn hyperedge_count(&self) -> usize {
77        self.hyperedges.len()
78    }
79
80    pub fn get_node(&self, id: NodeId) -> Option<&HypernodeData<N>> {
81        self.nodes.get(&id)
82    }
83
84    pub fn get_hyperedge(&self, id: HyperedgeId) -> Option<&HyperedgeData> {
85        self.hyperedges.get(&id)
86    }
87
88    pub fn node_ids(&self) -> Vec<NodeId> {
89        let mut ids: Vec<NodeId> = self.nodes.keys().copied().collect();
90        ids.sort();
91        ids
92    }
93
94    pub fn hyperedge_ids(&self) -> Vec<HyperedgeId> {
95        let mut ids: Vec<HyperedgeId> = self.hyperedges.keys().copied().collect();
96        ids.sort();
97        ids
98    }
99
100    /// Compute convex hull of member node positions for rendering a hyperedge.
101    pub fn convex_hull(&self, he_id: HyperedgeId) -> Vec<Vec2> {
102        let he = match self.hyperedges.get(&he_id) {
103            Some(he) => he,
104            None => return Vec::new(),
105        };
106
107        let points: Vec<Vec2> = he.members.iter()
108            .filter_map(|nid| self.nodes.get(nid).map(|n| n.position))
109            .collect();
110
111        if points.len() <= 2 {
112            return points;
113        }
114
115        convex_hull_2d(&points)
116    }
117
118    /// Convert hypergraph to bipartite graph representation.
119    /// Each hyperedge becomes a node, connected to all its member nodes.
120    pub fn to_bipartite(&self) -> Graph<String, ()>
121    where
122        N: std::fmt::Debug,
123    {
124        let mut g = Graph::new(GraphKind::Undirected);
125        let mut node_map: HashMap<NodeId, NodeId> = HashMap::new();
126        let mut hedge_map: HashMap<HyperedgeId, NodeId> = HashMap::new();
127
128        // Add original nodes
129        for (&nid, nd) in &self.nodes {
130            let gid = g.add_node_with_pos(format!("node_{}", nid.0), nd.position);
131            node_map.insert(nid, gid);
132        }
133
134        // Add hyperedge nodes
135        for (&hid, _) in &self.hyperedges {
136            let gid = g.add_node(format!("hedge_{}", hid.0));
137            hedge_map.insert(hid, gid);
138        }
139
140        // Connect hyperedge nodes to their members
141        for (&hid, he) in &self.hyperedges {
142            let hedge_gid = hedge_map[&hid];
143            for &member in &he.members {
144                if let Some(&member_gid) = node_map.get(&member) {
145                    g.add_edge(hedge_gid, member_gid, ());
146                }
147            }
148        }
149
150        g
151    }
152
153    /// Create a hypergraph from a bipartite graph.
154    /// Nodes labeled "hedge_*" become hyperedges, others become nodes.
155    pub fn from_bipartite(graph: &Graph<String, ()>) -> Hypergraph<String> {
156        let mut hg = Hypergraph::new();
157        let mut node_map: HashMap<NodeId, NodeId> = HashMap::new();
158        let mut hedge_nodes: Vec<NodeId> = Vec::new();
159
160        for nd in graph.nodes() {
161            if nd.data.starts_with("hedge_") {
162                hedge_nodes.push(nd.id);
163            } else {
164                let hid = hg.add_node(nd.data.clone(), nd.position);
165                node_map.insert(nd.id, hid);
166            }
167        }
168
169        for &hn in &hedge_nodes {
170            let members: Vec<NodeId> = graph.neighbors(hn)
171                .iter()
172                .filter_map(|&nbr| node_map.get(&nbr).copied())
173                .collect();
174            if !members.is_empty() {
175                hg.add_hyperedge(members);
176            }
177        }
178
179        hg
180    }
181}
182
183/// Compute 2D convex hull using Graham scan.
184fn convex_hull_2d(points: &[Vec2]) -> Vec<Vec2> {
185    if points.len() <= 2 {
186        return points.to_vec();
187    }
188
189    let mut pts = points.to_vec();
190
191    // Find lowest point (and leftmost if tie)
192    let mut lowest = 0;
193    for i in 1..pts.len() {
194        if pts[i].y < pts[lowest].y || (pts[i].y == pts[lowest].y && pts[i].x < pts[lowest].x) {
195            lowest = i;
196        }
197    }
198    pts.swap(0, lowest);
199    let pivot = pts[0];
200
201    // Sort by polar angle
202    pts[1..].sort_by(|a, b| {
203        let da = *a - pivot;
204        let db = *b - pivot;
205        let angle_a = da.y.atan2(da.x);
206        let angle_b = db.y.atan2(db.x);
207        angle_a.partial_cmp(&angle_b).unwrap_or(std::cmp::Ordering::Equal)
208    });
209
210    let mut hull: Vec<Vec2> = Vec::new();
211    for &p in &pts {
212        while hull.len() >= 2 {
213            let a = hull[hull.len() - 2];
214            let b = hull[hull.len() - 1];
215            let cross = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
216            if cross <= 0.0 {
217                hull.pop();
218            } else {
219                break;
220            }
221        }
222        hull.push(p);
223    }
224
225    hull
226}
227
228#[cfg(test)]
229mod tests {
230    use super::*;
231
232    #[test]
233    fn test_basic_hypergraph() {
234        let mut hg: Hypergraph<&str> = Hypergraph::new();
235        let a = hg.add_node("A", Vec2::new(0.0, 0.0));
236        let b = hg.add_node("B", Vec2::new(10.0, 0.0));
237        let c = hg.add_node("C", Vec2::new(5.0, 10.0));
238        let he = hg.add_hyperedge(vec![a, b, c]);
239        assert_eq!(hg.node_count(), 3);
240        assert_eq!(hg.hyperedge_count(), 1);
241        assert_eq!(hg.get_hyperedge(he).unwrap().members.len(), 3);
242    }
243
244    #[test]
245    fn test_remove_node_from_hyperedge() {
246        let mut hg: Hypergraph<()> = Hypergraph::new();
247        let a = hg.add_node((), Vec2::ZERO);
248        let b = hg.add_node((), Vec2::ZERO);
249        let c = hg.add_node((), Vec2::ZERO);
250        let he = hg.add_hyperedge(vec![a, b, c]);
251        hg.remove_node(b);
252        assert_eq!(hg.node_count(), 2);
253        assert_eq!(hg.get_hyperedge(he).unwrap().members.len(), 2);
254    }
255
256    #[test]
257    fn test_remove_all_members_removes_hyperedge() {
258        let mut hg: Hypergraph<()> = Hypergraph::new();
259        let a = hg.add_node((), Vec2::ZERO);
260        let he = hg.add_hyperedge(vec![a]);
261        hg.remove_node(a);
262        assert_eq!(hg.hyperedge_count(), 0);
263    }
264
265    #[test]
266    fn test_convex_hull() {
267        let mut hg: Hypergraph<()> = Hypergraph::new();
268        let a = hg.add_node((), Vec2::new(0.0, 0.0));
269        let b = hg.add_node((), Vec2::new(10.0, 0.0));
270        let c = hg.add_node((), Vec2::new(10.0, 10.0));
271        let d = hg.add_node((), Vec2::new(0.0, 10.0));
272        let e = hg.add_node((), Vec2::new(5.0, 5.0)); // interior point
273        let he = hg.add_hyperedge(vec![a, b, c, d, e]);
274        let hull = hg.convex_hull(he);
275        assert_eq!(hull.len(), 4); // interior point excluded
276    }
277
278    #[test]
279    fn test_bipartite_roundtrip() {
280        let mut hg: Hypergraph<String> = Hypergraph::new();
281        let a = hg.add_node("a".into(), Vec2::new(0.0, 0.0));
282        let b = hg.add_node("b".into(), Vec2::new(1.0, 0.0));
283        let c = hg.add_node("c".into(), Vec2::new(0.0, 1.0));
284        hg.add_hyperedge(vec![a, b, c]);
285        hg.add_hyperedge(vec![a, b]);
286
287        let bip = hg.to_bipartite();
288        assert_eq!(bip.node_count(), 5); // 3 nodes + 2 hyperedge nodes
289        // 3 + 2 = 5 edges
290        assert_eq!(bip.edge_count(), 5);
291
292        let hg2 = Hypergraph::from_bipartite(&bip);
293        assert_eq!(hg2.node_count(), 3);
294        assert_eq!(hg2.hyperedge_count(), 2);
295    }
296
297    #[test]
298    fn test_convex_hull_degenerate() {
299        let hull = convex_hull_2d(&[Vec2::new(1.0, 1.0)]);
300        assert_eq!(hull.len(), 1);
301        let hull = convex_hull_2d(&[Vec2::new(0.0, 0.0), Vec2::new(1.0, 1.0)]);
302        assert_eq!(hull.len(), 2);
303    }
304
305    #[test]
306    fn test_multiple_hyperedges() {
307        let mut hg: Hypergraph<()> = Hypergraph::new();
308        let a = hg.add_node((), Vec2::ZERO);
309        let b = hg.add_node((), Vec2::ZERO);
310        let c = hg.add_node((), Vec2::ZERO);
311        let d = hg.add_node((), Vec2::ZERO);
312        hg.add_hyperedge(vec![a, b, c]);
313        hg.add_hyperedge(vec![b, c, d]);
314        hg.add_hyperedge(vec![a, d]);
315        assert_eq!(hg.hyperedge_count(), 3);
316    }
317}
proof_engine/graph/hypergraph.rs

proof_engine/graph/
hypergraph.rs
