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    /// Adds a directed edge from `parent_id` to `child_id`, creating nodes if
76    /// they do not already exist in the graph.
77    pub(super) fn add_edge(&mut self, parent_id: OwnedRoomId, child_id: OwnedRoomId) {
78        let parent_entry =
79            self.nodes.entry(parent_id.clone()).or_insert(SpaceGraphNode::new(parent_id.clone()));
80        parent_entry.children.insert(child_id.clone());
81
82        let child_entry =
83            self.nodes.entry(child_id.clone()).or_insert(SpaceGraphNode::new(child_id));
84        child_entry.parents.insert(parent_id);
85    }
86
87    /// Removes cycles in the graph by performing a depth-first search (DFS) and
88    /// remembering the visited nodes. If a node is revisited while still in the
89    /// current path (i.e. it's on the stack), it indicates a cycle.
90    pub(super) fn remove_cycles(&mut self) {
91        let mut visited = BTreeSet::new();
92        let mut stack = BTreeSet::new();
93
94        let mut edges_to_remove = Vec::new();
95
96        for node_id in self.nodes.keys() {
97            self.dfs_remove_cycles(node_id, &mut visited, &mut stack, &mut edges_to_remove);
98        }
99
100        for (parent, child) in edges_to_remove {
101            if let Some(node) = self.nodes.get_mut(&parent) {
102                node.children.remove(&child);
103            }
104            if let Some(node) = self.nodes.get_mut(&child) {
105                node.parents.remove(&parent);
106            }
107        }
108    }
109
110    fn dfs_remove_cycles(
111        &self,
112        node_id: &OwnedRoomId,
113        visited: &mut BTreeSet<OwnedRoomId>,
114        stack: &mut BTreeSet<OwnedRoomId>,
115        edges_to_remove: &mut Vec<(OwnedRoomId, OwnedRoomId)>,
116    ) {
117        if !visited.insert(node_id.clone()) {
118            return;
119        }
120
121        stack.insert(node_id.clone());
122
123        if let Some(node) = self.nodes.get(node_id) {
124            for child in &node.children {
125                if stack.contains(child) {
126                    // Found a cycle → mark this edge for removal
127                    edges_to_remove.push((node_id.clone(), child.clone()));
128                } else {
129                    self.dfs_remove_cycles(child, visited, stack, edges_to_remove);
130                }
131            }
132        }
133
134        stack.remove(node_id);
135    }
136}
137
138#[cfg(test)]
139mod tests {
140    use ruma::room_id;
141
142    use super::*;
143
144    #[test]
145    fn test_add_edge_and_root_nodes() {
146        let mut graph = SpaceGraph::new();
147
148        let a = room_id!("!a:example.org").to_owned();
149        let b = room_id!("!b:example.org").to_owned();
150        let c = room_id!("!c:example.org").to_owned();
151
152        graph.add_edge(a.clone(), b.clone());
153        graph.add_edge(a.clone(), c.clone());
154
155        assert_eq!(graph.root_nodes(), vec![&a]);
156
157        assert!(graph.nodes[&b].parents.contains(&a));
158        assert!(graph.nodes[&c].parents.contains(&a));
159
160        assert_eq!(graph.children_of(&a), vec![&b, &c]);
161    }
162
163    #[test]
164    fn test_remove_cycles() {
165        let mut graph = SpaceGraph::new();
166
167        let a = room_id!("!a:example.org").to_owned();
168        let b = room_id!("!b:example.org").to_owned();
169        let c = room_id!("!c:example.org").to_owned();
170
171        graph.add_edge(a.clone(), b.clone());
172        graph.add_edge(b, c.clone());
173        graph.add_edge(c.clone(), a.clone()); // creates a cycle
174
175        assert!(graph.nodes[&c].children.contains(&a));
176
177        graph.remove_cycles();
178
179        assert!(!graph.nodes[&c].children.contains(&a));
180        assert!(!graph.nodes[&a].parents.contains(&c));
181    }
182
183    #[test]
184    fn test_disconnected_graph_roots() {
185        let mut graph = SpaceGraph::new();
186
187        let a = room_id!("!a:example.org").to_owned();
188        let b = room_id!("!b:example.org").to_owned();
189        graph.add_edge(a.clone(), b);
190
191        let x = room_id!("!x:example.org").to_owned();
192        let y = room_id!("!y:example.org").to_owned();
193        graph.add_edge(x.clone(), y);
194
195        let mut roots = graph.root_nodes();
196        roots.sort_by_key(|key| key.to_string());
197
198        let expected: Vec<&OwnedRoomId> = vec![&a, &x];
199        assert_eq!(roots, expected);
200    }
201
202    #[test]
203    fn test_multiple_parents() {
204        let mut graph = SpaceGraph::new();
205
206        let a = room_id!("!a:example.org").to_owned();
207        let b = room_id!("!b:example.org").to_owned();
208        let c = room_id!("!c:example.org").to_owned();
209        let d = room_id!("!d:example.org").to_owned();
210
211        graph.add_edge(a.clone(), c.clone());
212        graph.add_edge(b.clone(), c.clone());
213        graph.add_edge(c.clone(), d);
214
215        let mut roots = graph.root_nodes();
216        roots.sort_by_key(|key| key.to_string());
217
218        let expected = vec![&a, &b];
219        assert_eq!(roots, expected);
220
221        let c_parents = &graph.nodes[&c].parents;
222        assert!(c_parents.contains(&a));
223        assert!(c_parents.contains(&b));
224    }
225}
matrix_sdk_ui/spaces/graph.rs

matrix_sdk_ui/spaces/
graph.rs
