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    /// Adds a node to the graph. If the node already exists, it does nothing.
71    pub(super) fn add_node(&mut self, node_id: OwnedRoomId) {
72        self.nodes.entry(node_id.clone()).or_insert(SpaceGraphNode::new(node_id));
73    }
74
75    /// Returns whether a node exists in the graph.
76    pub(super) fn has_node(&self, node_id: &RoomId) -> bool {
77        self.nodes.contains_key(node_id)
78    }
79
80    /// Adds a directed edge from `parent_id` to `child_id`, creating nodes if
81    /// they do not already exist in the graph.
82    pub(super) fn add_edge(&mut self, parent_id: OwnedRoomId, child_id: OwnedRoomId) {
83        let parent_entry =
84            self.nodes.entry(parent_id.clone()).or_insert(SpaceGraphNode::new(parent_id.clone()));
85        parent_entry.children.insert(child_id.clone());
86
87        let child_entry =
88            self.nodes.entry(child_id.clone()).or_insert(SpaceGraphNode::new(child_id));
89        child_entry.parents.insert(parent_id);
90    }
91
92    /// Returns the subtree of the given node in a bottom-up order.
93    ///
94    /// Does a BFS starting from the given node tracking the visited nodes
95    /// and returning them in the reverse order.
96    pub(super) fn flattened_bottom_up_subtree(&self, node_id: &RoomId) -> Vec<OwnedRoomId> {
97        if !self.has_node(node_id) {
98            return Vec::new();
99        }
100
101        let mut stack = vec![node_id.to_owned()];
102        let mut result = Vec::new();
103
104        while let Some(node) = stack.pop() {
105            result.insert(0, node.clone());
106
107            if let Some(node) = self.nodes.get(&node) {
108                for child in &node.children {
109                    stack.push(child.to_owned());
110                }
111            }
112        }
113
114        result
115    }
116
117    /// Removes cycles in the graph by performing a depth-first search (DFS) and
118    /// remembering the visited nodes. If a node is revisited while still in the
119    /// current path (i.e. it's on the stack), it indicates a cycle.
120    pub(super) fn remove_cycles(&mut self) {
121        let mut visited = BTreeSet::new();
122        let mut stack = BTreeSet::new();
123
124        let mut edges_to_remove = Vec::new();
125
126        for node_id in self.nodes.keys() {
127            self.dfs_remove_cycles(node_id, &mut visited, &mut stack, &mut edges_to_remove);
128        }
129
130        for (parent, child) in edges_to_remove {
131            if let Some(node) = self.nodes.get_mut(&parent) {
132                node.children.remove(&child);
133            }
134            if let Some(node) = self.nodes.get_mut(&child) {
135                node.parents.remove(&parent);
136            }
137        }
138    }
139
140    fn dfs_remove_cycles(
141        &self,
142        node_id: &OwnedRoomId,
143        visited: &mut BTreeSet<OwnedRoomId>,
144        stack: &mut BTreeSet<OwnedRoomId>,
145        edges_to_remove: &mut Vec<(OwnedRoomId, OwnedRoomId)>,
146    ) {
147        if !visited.insert(node_id.clone()) {
148            return;
149        }
150
151        stack.insert(node_id.clone());
152
153        if let Some(node) = self.nodes.get(node_id) {
154            for child in &node.children {
155                if stack.contains(child) {
156                    // Found a cycle → mark this edge for removal
157                    edges_to_remove.push((node_id.clone(), child.clone()));
158                } else {
159                    self.dfs_remove_cycles(child, visited, stack, edges_to_remove);
160                }
161            }
162        }
163
164        stack.remove(node_id);
165    }
166}
167
168#[cfg(test)]
169mod tests {
170    use ruma::{owned_room_id, room_id};
171
172    use super::*;
173
174    #[test]
175    fn test_add_edge_and_root_nodes() {
176        let mut graph = SpaceGraph::new();
177
178        let a = room_id!("!a:example.org").to_owned();
179        let b = room_id!("!b:example.org").to_owned();
180        let c = room_id!("!c:example.org").to_owned();
181
182        graph.add_edge(a.clone(), b.clone());
183        graph.add_edge(a.clone(), c.clone());
184
185        assert_eq!(graph.root_nodes(), vec![&a]);
186
187        assert!(graph.nodes[&b].parents.contains(&a));
188        assert!(graph.nodes[&c].parents.contains(&a));
189
190        assert_eq!(graph.children_of(&a), vec![&b, &c]);
191    }
192
193    #[test]
194    fn test_remove_cycles() {
195        let mut graph = SpaceGraph::new();
196
197        let a = room_id!("!a:example.org").to_owned();
198        let b = room_id!("!b:example.org").to_owned();
199        let c = room_id!("!c:example.org").to_owned();
200
201        graph.add_edge(a.clone(), b.clone());
202        graph.add_edge(b, c.clone());
203        graph.add_edge(c.clone(), a.clone()); // creates a cycle
204
205        assert!(graph.nodes[&c].children.contains(&a));
206
207        graph.remove_cycles();
208
209        assert!(!graph.nodes[&c].children.contains(&a));
210        assert!(!graph.nodes[&a].parents.contains(&c));
211    }
212
213    #[test]
214    fn test_disconnected_graph_roots() {
215        let mut graph = SpaceGraph::new();
216
217        let a = room_id!("!a:example.org").to_owned();
218        let b = room_id!("!b:example.org").to_owned();
219        graph.add_edge(a.clone(), b);
220
221        let x = room_id!("!x:example.org").to_owned();
222        let y = room_id!("!y:example.org").to_owned();
223        graph.add_edge(x.clone(), y);
224
225        let mut roots = graph.root_nodes();
226        roots.sort_by_key(|key| key.to_string());
227
228        let expected: Vec<&OwnedRoomId> = vec![&a, &x];
229        assert_eq!(roots, expected);
230    }
231
232    #[test]
233    fn test_multiple_parents() {
234        let mut graph = SpaceGraph::new();
235
236        let a = room_id!("!a:example.org").to_owned();
237        let b = room_id!("!b:example.org").to_owned();
238        let c = room_id!("!c:example.org").to_owned();
239        let d = room_id!("!d:example.org").to_owned();
240
241        graph.add_edge(a.clone(), c.clone());
242        graph.add_edge(b.clone(), c.clone());
243        graph.add_edge(c.clone(), d);
244
245        let mut roots = graph.root_nodes();
246        roots.sort_by_key(|key| key.to_string());
247
248        let expected = vec![&a, &b];
249        assert_eq!(roots, expected);
250
251        let c_parents = &graph.nodes[&c].parents;
252        assert!(c_parents.contains(&a));
253        assert!(c_parents.contains(&b));
254    }
255
256    #[test]
257    fn test_flattened_bottom_up_subtree() {
258        let graph = vehicle_graph();
259
260        let children = graph.flattened_bottom_up_subtree(room_id!("!personal:x.y"));
261        let expected = vec![
262            owned_room_id!("!gravel:x.y"),
263            owned_room_id!("!mountain:x.y"),
264            owned_room_id!("!road:x.y"),
265            owned_room_id!("!bicycle:x.y"),
266            owned_room_id!("!car:x.y"),
267            owned_room_id!("!helicopter:x.y"),
268            owned_room_id!("!personal:x.y"),
269        ];
270
271        assert_eq!(children, expected);
272
273        let children = graph.flattened_bottom_up_subtree(room_id!("!shared:x.y"));
274        let expected = vec![
275            owned_room_id!("!bus:x.y"),
276            owned_room_id!("!train:x.y"),
277            owned_room_id!("!shared:x.y"),
278        ];
279
280        assert_eq!(children, expected);
281
282        let children = graph.flattened_bottom_up_subtree(room_id!("!plane:x.y"));
283        let expected = vec![owned_room_id!("!plane:x.y")];
284
285        assert_eq!(children, expected);
286
287        let children = graph.flattened_bottom_up_subtree(room_id!("!floo_powder:x.y"));
288        assert!(children.is_empty());
289    }
290
291    fn vehicle_graph() -> SpaceGraph {
292        // Vehicles
293        // ├── Shared
294        // │   ├── Bus
295        // │   └── Train
296        // ├── Personal
297        // │   ├── Car
298        // │   ├── Bicycle
299        // │   │   ├── Road
300        // │   │   ├── Gravel
301        // │   │   └── Mountain
302        // │   └── Helicopter
303        // └── Cargo
304        //     └── Plane
305
306        let mut graph = SpaceGraph::new();
307
308        graph.add_edge(owned_room_id!("!vehicles:x.y"), owned_room_id!("!shared:x.y"));
309        graph.add_edge(owned_room_id!("!shared:x.y"), owned_room_id!("!bus:x.y"));
310        graph.add_edge(owned_room_id!("!shared:x.y"), owned_room_id!("!train:x.y"));
311
312        graph.add_edge(owned_room_id!("!vehicles:x.y"), owned_room_id!("!personal:x.y"));
313        graph.add_edge(owned_room_id!("!personal:x.y"), owned_room_id!("!car:x.y"));
314
315        graph.add_edge(owned_room_id!("!personal:x.y"), owned_room_id!("!bicycle:x.y"));
316        graph.add_edge(owned_room_id!("!bicycle:x.y"), owned_room_id!("!road:x.y"));
317        graph.add_edge(owned_room_id!("!bicycle:x.y"), owned_room_id!("!gravel:x.y"));
318        graph.add_edge(owned_room_id!("!bicycle:x.y"), owned_room_id!("!mountain:x.y"));
319
320        graph.add_edge(owned_room_id!("!personal:x.y"), owned_room_id!("!helicopter:x.y"));
321
322        graph.add_edge(owned_room_id!("!vehicles:x.y"), owned_room_id!("!cargo:x.y"));
323        graph.add_edge(owned_room_id!("!cargo:x.y"), owned_room_id!("!plane:x.y"));
324
325        graph
326    }
327}
matrix_sdk_ui/spaces/graph.rs

matrix_sdk_ui/spaces/
graph.rs
