matrix_sdk_ui/spaces/
graph.rs

1// Copyright 2025 The Matrix.org Foundation C.I.C.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for that specific language governing permissions and
13// limitations under the License.
14
15use std::collections::{BTreeMap, BTreeSet};
16
17use ruma::{OwnedRoomId, RoomId};
18
19#[derive(Debug)]
20struct SpaceGraphNode {
21    id: OwnedRoomId,
22    parents: BTreeSet<OwnedRoomId>,
23    children: BTreeSet<OwnedRoomId>,
24}
25
26impl SpaceGraphNode {
27    fn new(id: OwnedRoomId) -> Self {
28        Self { id, parents: BTreeSet::new(), children: BTreeSet::new() }
29    }
30}
31
32/// A graph structure representing a space hierarchy. Contains functionality
33/// for mapping parent-child relationships between rooms, removing cycles and
34/// retrieving top-level parents/roots.
35#[derive(Debug)]
36pub(super) struct SpaceGraph {
37    nodes: BTreeMap<OwnedRoomId, SpaceGraphNode>,
38}
39
40impl Default for SpaceGraph {
41    fn default() -> Self {
42        Self::new()
43    }
44}
45
46impl SpaceGraph {
47    /// Creates a new empty space graph containing no nodes or edges.
48    pub(super) fn new() -> Self {
49        Self { nodes: BTreeMap::new() }
50    }
51
52    /// Returns the root nodes of the graph, which are nodes without any
53    /// parents.
54    pub(super) fn root_nodes(&self) -> Vec<&RoomId> {
55        self.nodes
56            .values()
57            .filter(|node| node.parents.is_empty())
58            .map(|node| node.id.as_ref())
59            .collect()
60    }
61
62    /// Returns the children of a given node. If the node does not exist, it
63    /// returns an empty vector.
64    pub(super) fn children_of(&self, node_id: &RoomId) -> Vec<&RoomId> {
65        self.nodes
66            .get(node_id)
67            .map_or(vec![], |node| node.children.iter().map(|id| id.as_ref()).collect())
68    }
69
70    /// Returns the parents of a given node. If the node does not exist, it
71    /// returns an empty vector.
72    pub(super) fn parents_of(&self, node_id: &RoomId) -> Vec<&RoomId> {
73        self.nodes
74            .get(node_id)
75            .map_or(vec![], |node| node.parents.iter().map(|id| id.as_ref()).collect())
76    }
77
78    /// Adds a node to the graph. If the node already exists, it does nothing.
79    pub(super) fn add_node(&mut self, node_id: OwnedRoomId) {
80        self.nodes.entry(node_id.clone()).or_insert(SpaceGraphNode::new(node_id));
81    }
82
83    /// Returns whether a node exists in the graph.
84    pub(super) fn has_node(&self, node_id: &RoomId) -> bool {
85        self.nodes.contains_key(node_id)
86    }
87
88    /// Adds a directed edge from `parent_id` to `child_id`, creating nodes if
89    /// they do not already exist in the graph.
90    pub(super) fn add_edge(&mut self, parent_id: OwnedRoomId, child_id: OwnedRoomId) {
91        let parent_entry =
92            self.nodes.entry(parent_id.clone()).or_insert(SpaceGraphNode::new(parent_id.clone()));
93        parent_entry.children.insert(child_id.clone());
94
95        let child_entry =
96            self.nodes.entry(child_id.clone()).or_insert(SpaceGraphNode::new(child_id));
97        child_entry.parents.insert(parent_id);
98    }
99
100    /// Returns the subtree of the given node in a bottom-up order.
101    ///
102    /// Does a BFS starting from the given node tracking the visited nodes
103    /// and returning them in the reverse order.
104    pub(super) fn flattened_bottom_up_subtree(&self, node_id: &RoomId) -> Vec<OwnedRoomId> {
105        if !self.has_node(node_id) {
106            return Vec::new();
107        }
108
109        let mut stack = vec![node_id.to_owned()];
110        let mut result = Vec::new();
111
112        while let Some(node) = stack.pop() {
113            result.insert(0, node.clone());
114
115            if let Some(node) = self.nodes.get(&node) {
116                for child in &node.children {
117                    stack.push(child.to_owned());
118                }
119            }
120        }
121
122        result
123    }
124
125    /// Removes cycles in the graph by performing a depth-first search (DFS) and
126    /// remembering the visited nodes. If a node is revisited while still in the
127    /// current path (i.e. it's on the stack), it indicates a cycle.
128    pub(super) fn remove_cycles(&mut self) {
129        let mut visited = BTreeSet::new();
130        let mut stack = BTreeSet::new();
131
132        let mut edges_to_remove = Vec::new();
133
134        for node_id in self.nodes.keys() {
135            self.dfs_remove_cycles(node_id, &mut visited, &mut stack, &mut edges_to_remove);
136        }
137
138        for (parent, child) in edges_to_remove {
139            if let Some(node) = self.nodes.get_mut(&parent) {
140                node.children.remove(&child);
141            }
142            if let Some(node) = self.nodes.get_mut(&child) {
143                node.parents.remove(&parent);
144            }
145        }
146    }
147
148    fn dfs_remove_cycles(
149        &self,
150        node_id: &OwnedRoomId,
151        visited: &mut BTreeSet<OwnedRoomId>,
152        stack: &mut BTreeSet<OwnedRoomId>,
153        edges_to_remove: &mut Vec<(OwnedRoomId, OwnedRoomId)>,
154    ) {
155        if !visited.insert(node_id.clone()) {
156            return;
157        }
158
159        stack.insert(node_id.clone());
160
161        if let Some(node) = self.nodes.get(node_id) {
162            for child in &node.children {
163                if stack.contains(child) {
164                    // Found a cycle → mark this edge for removal
165                    edges_to_remove.push((node_id.clone(), child.clone()));
166                } else {
167                    self.dfs_remove_cycles(child, visited, stack, edges_to_remove);
168                }
169            }
170        }
171
172        stack.remove(node_id);
173    }
174}
175
176#[cfg(test)]
177mod tests {
178    use ruma::{owned_room_id, room_id};
179
180    use super::*;
181
182    #[test]
183    fn test_add_edge_and_root_nodes() {
184        let mut graph = SpaceGraph::new();
185
186        let a = room_id!("!a:example.org").to_owned();
187        let b = room_id!("!b:example.org").to_owned();
188        let c = room_id!("!c:example.org").to_owned();
189
190        graph.add_edge(a.clone(), b.clone());
191        graph.add_edge(a.clone(), c.clone());
192
193        assert_eq!(graph.root_nodes(), vec![&a]);
194
195        assert_eq!(graph.parents_of(&b), vec![&a]);
196        assert_eq!(graph.parents_of(&c), vec![&a]);
197
198        assert_eq!(graph.children_of(&a), vec![&b, &c]);
199    }
200
201    #[test]
202    fn test_remove_cycles() {
203        let mut graph = SpaceGraph::new();
204
205        let a = room_id!("!a:example.org").to_owned();
206        let b = room_id!("!b:example.org").to_owned();
207        let c = room_id!("!c:example.org").to_owned();
208
209        graph.add_edge(a.clone(), b.clone());
210        graph.add_edge(b, c.clone());
211        graph.add_edge(c.clone(), a.clone()); // creates a cycle
212
213        assert!(graph.nodes[&c].children.contains(&a));
214
215        graph.remove_cycles();
216
217        assert!(!graph.nodes[&c].children.contains(&a));
218        assert!(!graph.nodes[&a].parents.contains(&c));
219    }
220
221    #[test]
222    fn test_disconnected_graph_roots() {
223        let mut graph = SpaceGraph::new();
224
225        let a = room_id!("!a:example.org").to_owned();
226        let b = room_id!("!b:example.org").to_owned();
227        graph.add_edge(a.clone(), b);
228
229        let x = room_id!("!x:example.org").to_owned();
230        let y = room_id!("!y:example.org").to_owned();
231        graph.add_edge(x.clone(), y);
232
233        let mut roots = graph.root_nodes();
234        roots.sort_by_key(|key| key.to_string());
235
236        let expected: Vec<&OwnedRoomId> = vec![&a, &x];
237        assert_eq!(roots, expected);
238    }
239
240    #[test]
241    fn test_multiple_parents() {
242        let mut graph = SpaceGraph::new();
243
244        let a = room_id!("!a:example.org").to_owned();
245        let b = room_id!("!b:example.org").to_owned();
246        let c = room_id!("!c:example.org").to_owned();
247        let d = room_id!("!d:example.org").to_owned();
248
249        graph.add_edge(a.clone(), c.clone());
250        graph.add_edge(b.clone(), c.clone());
251        graph.add_edge(c.clone(), d);
252
253        let mut roots = graph.root_nodes();
254        roots.sort_by_key(|key| key.to_string());
255
256        let expected = vec![&a, &b];
257        assert_eq!(roots, expected);
258
259        let c_parents = &graph.nodes[&c].parents;
260        assert!(c_parents.contains(&a));
261        assert!(c_parents.contains(&b));
262    }
263
264    #[test]
265    fn test_flattened_bottom_up_subtree() {
266        let graph = vehicle_graph();
267
268        let children = graph.flattened_bottom_up_subtree(room_id!("!personal:x.y"));
269        let expected = vec![
270            owned_room_id!("!gravel:x.y"),
271            owned_room_id!("!mountain:x.y"),
272            owned_room_id!("!road:x.y"),
273            owned_room_id!("!bicycle:x.y"),
274            owned_room_id!("!car:x.y"),
275            owned_room_id!("!helicopter:x.y"),
276            owned_room_id!("!personal:x.y"),
277        ];
278
279        assert_eq!(children, expected);
280
281        let children = graph.flattened_bottom_up_subtree(room_id!("!shared:x.y"));
282        let expected = vec![
283            owned_room_id!("!bus:x.y"),
284            owned_room_id!("!train:x.y"),
285            owned_room_id!("!shared:x.y"),
286        ];
287
288        assert_eq!(children, expected);
289
290        let children = graph.flattened_bottom_up_subtree(room_id!("!plane:x.y"));
291        let expected = vec![owned_room_id!("!plane:x.y")];
292
293        assert_eq!(children, expected);
294
295        let children = graph.flattened_bottom_up_subtree(room_id!("!floo_powder:x.y"));
296        assert!(children.is_empty());
297    }
298
299    fn vehicle_graph() -> SpaceGraph {
300        // Vehicles
301        // ├── Shared
302        // │   ├── Bus
303        // │   └── Train
304        // ├── Personal
305        // │   ├── Car
306        // │   ├── Bicycle
307        // │   │   ├── Road
308        // │   │   ├── Gravel
309        // │   │   └── Mountain
310        // │   └── Helicopter
311        // └── Cargo
312        //     └── Plane
313
314        let mut graph = SpaceGraph::new();
315
316        graph.add_edge(owned_room_id!("!vehicles:x.y"), owned_room_id!("!shared:x.y"));
317        graph.add_edge(owned_room_id!("!shared:x.y"), owned_room_id!("!bus:x.y"));
318        graph.add_edge(owned_room_id!("!shared:x.y"), owned_room_id!("!train:x.y"));
319
320        graph.add_edge(owned_room_id!("!vehicles:x.y"), owned_room_id!("!personal:x.y"));
321        graph.add_edge(owned_room_id!("!personal:x.y"), owned_room_id!("!car:x.y"));
322
323        graph.add_edge(owned_room_id!("!personal:x.y"), owned_room_id!("!bicycle:x.y"));
324        graph.add_edge(owned_room_id!("!bicycle:x.y"), owned_room_id!("!road:x.y"));
325        graph.add_edge(owned_room_id!("!bicycle:x.y"), owned_room_id!("!gravel:x.y"));
326        graph.add_edge(owned_room_id!("!bicycle:x.y"), owned_room_id!("!mountain:x.y"));
327
328        graph.add_edge(owned_room_id!("!personal:x.y"), owned_room_id!("!helicopter:x.y"));
329
330        graph.add_edge(owned_room_id!("!vehicles:x.y"), owned_room_id!("!cargo:x.y"));
331        graph.add_edge(owned_room_id!("!cargo:x.y"), owned_room_id!("!plane:x.y"));
332
333        graph
334    }
335}
matrix_sdk_ui/spaces/graph.rs

matrix_sdk_ui/spaces/
graph.rs
