leptos_helios/graph_features/
algorithms.rs

1//! Graph Algorithms
2//!
3//! This module provides various graph algorithms for analysis and manipulation.
4
5use super::{GraphEdge, GraphNode};
6use std::collections::{HashMap, HashSet, VecDeque};
7
8/// Graph algorithms for various operations
9pub struct GraphAlgorithms;
10
11impl GraphAlgorithms {
12    /// Find all connected components in the graph
13    pub fn find_connected_components(nodes: &[GraphNode], edges: &[GraphEdge]) -> Vec<Vec<String>> {
14        let mut visited = HashSet::new();
15        let mut components = Vec::new();
16
17        for node in nodes {
18            if !visited.contains(&node.id) {
19                let mut component = Vec::new();
20                Self::dfs_component(&node.id, nodes, edges, &mut visited, &mut component);
21                components.push(component);
22            }
23        }
24
25        components
26    }
27
28    /// Depth-first search for connected components
29    fn dfs_component(
30        node_id: &str,
31        nodes: &[GraphNode],
32        edges: &[GraphEdge],
33        visited: &mut HashSet<String>,
34        component: &mut Vec<String>,
35    ) {
36        visited.insert(node_id.to_string());
37        component.push(node_id.to_string());
38
39        for edge in edges {
40            let neighbor = if edge.source == node_id {
41                Some(&edge.target)
42            } else if edge.target == node_id {
43                Some(&edge.source)
44            } else {
45                None
46            };
47
48            if let Some(neighbor_id) = neighbor {
49                if !visited.contains(neighbor_id) {
50                    Self::dfs_component(neighbor_id, nodes, edges, visited, component);
51                }
52            }
53        }
54    }
55
56    /// Find shortest path using Dijkstra's algorithm
57    pub fn dijkstra_shortest_path(
58        source: &str,
59        target: &str,
60        nodes: &[GraphNode],
61        edges: &[GraphEdge],
62    ) -> Option<Vec<String>> {
63        let mut distances: HashMap<String, f64> = nodes
64            .iter()
65            .map(|n| (n.id.clone(), f64::INFINITY))
66            .collect();
67        let mut previous: HashMap<String, Option<String>> =
68            nodes.iter().map(|n| (n.id.clone(), None)).collect();
69        let mut unvisited: HashSet<String> = nodes.iter().map(|n| n.id.clone()).collect();
70
71        distances.insert(source.to_string(), 0.0);
72
73        while !unvisited.is_empty() {
74            // Find unvisited node with minimum distance
75            let current = unvisited
76                .iter()
77                .min_by(|a, b| {
78                    distances
79                        .get(*a)
80                        .unwrap_or(&f64::INFINITY)
81                        .partial_cmp(distances.get(*b).unwrap_or(&f64::INFINITY))
82                        .unwrap()
83                })?
84                .clone();
85
86            if current == target {
87                break;
88            }
89
90            unvisited.remove(&current);
91
92            // Update distances to neighbors
93            for edge in edges {
94                let neighbor = if edge.source == current {
95                    Some(&edge.target)
96                } else if edge.target == current {
97                    Some(&edge.source)
98                } else {
99                    None
100                };
101
102                if let Some(neighbor_id) = neighbor {
103                    if unvisited.contains(neighbor_id) {
104                        let alt = distances.get(&current).unwrap_or(&f64::INFINITY) + edge.weight;
105                        if alt < *distances.get(neighbor_id).unwrap_or(&f64::INFINITY) {
106                            distances.insert(neighbor_id.clone(), alt);
107                            previous.insert(neighbor_id.clone(), Some(current.clone()));
108                        }
109                    }
110                }
111            }
112        }
113
114        // Reconstruct path
115        let mut path = Vec::new();
116        let mut current = target.to_string();
117
118        while let Some(prev) = previous.get(&current)? {
119            path.push(current);
120            current = prev.clone();
121        }
122        path.push(source.to_string());
123        path.reverse();
124
125        Some(path)
126    }
127
128    /// Find minimum spanning tree using Kruskal's algorithm
129    pub fn kruskal_mst(nodes: &[GraphNode], edges: &[GraphEdge]) -> Vec<GraphEdge> {
130        let mut sorted_edges = edges.to_vec();
131        sorted_edges.sort_by(|a, b| a.weight.partial_cmp(&b.weight).unwrap());
132
133        let mut mst = Vec::new();
134        let mut parent: HashMap<String, String> =
135            nodes.iter().map(|n| (n.id.clone(), n.id.clone())).collect();
136
137        for edge in sorted_edges {
138            let root_source = Self::find_root(&edge.source, &parent);
139            let root_target = Self::find_root(&edge.target, &parent);
140
141            if root_source != root_target {
142                mst.push(edge.clone());
143                parent.insert(root_source, root_target);
144            }
145        }
146
147        mst
148    }
149
150    /// Find root of a node in union-find structure
151    fn find_root(node: &str, parent: &HashMap<String, String>) -> String {
152        let mut current = node.to_string();
153        while parent.get(&current) != Some(&current) {
154            current = parent.get(&current).unwrap().clone();
155        }
156        current
157    }
158
159    /// Detect cycles in the graph using DFS
160    pub fn detect_cycle(nodes: &[GraphNode], edges: &[GraphEdge]) -> bool {
161        let mut visited = HashSet::new();
162        let mut rec_stack = HashSet::new();
163
164        for node in nodes {
165            if !visited.contains(&node.id) {
166                if Self::dfs_cycle(&node.id, nodes, edges, &mut visited, &mut rec_stack) {
167                    return true;
168                }
169            }
170        }
171
172        false
173    }
174
175    /// DFS helper for cycle detection
176    fn dfs_cycle(
177        node_id: &str,
178        _nodes: &[GraphNode],
179        edges: &[GraphEdge],
180        visited: &mut HashSet<String>,
181        rec_stack: &mut HashSet<String>,
182    ) -> bool {
183        visited.insert(node_id.to_string());
184        rec_stack.insert(node_id.to_string());
185
186        for edge in edges {
187            let neighbor = if edge.source == node_id {
188                Some(&edge.target)
189            } else if edge.target == node_id {
190                Some(&edge.source)
191            } else {
192                None
193            };
194
195            if let Some(neighbor_id) = neighbor {
196                if !visited.contains(neighbor_id) {
197                    if Self::dfs_cycle(neighbor_id, _nodes, edges, visited, rec_stack) {
198                        return true;
199                    }
200                } else if rec_stack.contains(neighbor_id) {
201                    return true;
202                }
203            }
204        }
205
206        rec_stack.remove(node_id);
207        false
208    }
209
210    /// Topological sort using Kahn's algorithm
211    pub fn topological_sort(nodes: &[GraphNode], edges: &[GraphEdge]) -> Option<Vec<String>> {
212        let mut in_degree: HashMap<String, usize> =
213            nodes.iter().map(|n| (n.id.clone(), 0)).collect();
214
215        // Calculate in-degrees
216        for edge in edges {
217            *in_degree.get_mut(&edge.target).unwrap() += 1;
218        }
219
220        // Find nodes with no incoming edges
221        let mut queue: VecDeque<String> = in_degree
222            .iter()
223            .filter(|(_, &degree)| degree == 0)
224            .map(|(node, _)| node.clone())
225            .collect();
226
227        let mut result = Vec::new();
228
229        while let Some(current) = queue.pop_front() {
230            result.push(current.clone());
231
232            // Update in-degrees of neighbors
233            for edge in edges {
234                if edge.source == current {
235                    let neighbor = &edge.target;
236                    if let Some(degree) = in_degree.get_mut(neighbor) {
237                        *degree -= 1;
238                        if *degree == 0 {
239                            queue.push_back(neighbor.clone());
240                        }
241                    }
242                }
243            }
244        }
245
246        // Check if all nodes were processed
247        if result.len() == nodes.len() {
248            Some(result)
249        } else {
250            None // Cycle detected
251        }
252    }
253
254    /// Find strongly connected components using Tarjan's algorithm
255    pub fn tarjan_scc(nodes: &[GraphNode], edges: &[GraphEdge]) -> Vec<Vec<String>> {
256        let mut index = 0;
257        let mut stack = Vec::new();
258        let mut indices: HashMap<String, usize> = HashMap::new();
259        let mut lowlinks: HashMap<String, usize> = HashMap::new();
260        let mut on_stack: HashSet<String> = HashSet::new();
261        let mut sccs = Vec::new();
262
263        for node in nodes {
264            if !indices.contains_key(&node.id) {
265                Self::tarjan_visit(
266                    &node.id,
267                    nodes,
268                    edges,
269                    &mut index,
270                    &mut stack,
271                    &mut indices,
272                    &mut lowlinks,
273                    &mut on_stack,
274                    &mut sccs,
275                );
276            }
277        }
278
279        sccs
280    }
281
282    /// Tarjan's algorithm helper
283    fn tarjan_visit(
284        node_id: &str,
285        nodes: &[GraphNode],
286        edges: &[GraphEdge],
287        index: &mut usize,
288        stack: &mut Vec<String>,
289        indices: &mut HashMap<String, usize>,
290        lowlinks: &mut HashMap<String, usize>,
291        on_stack: &mut HashSet<String>,
292        sccs: &mut Vec<Vec<String>>,
293    ) {
294        indices.insert(node_id.to_string(), *index);
295        lowlinks.insert(node_id.to_string(), *index);
296        *index += 1;
297        stack.push(node_id.to_string());
298        on_stack.insert(node_id.to_string());
299
300        // Visit neighbors
301        for edge in edges {
302            let neighbor = if edge.source == node_id {
303                Some(&edge.target)
304            } else if edge.target == node_id {
305                Some(&edge.source)
306            } else {
307                None
308            };
309
310            if let Some(neighbor_id) = neighbor {
311                if !indices.contains_key(neighbor_id) {
312                    Self::tarjan_visit(
313                        neighbor_id,
314                        nodes,
315                        edges,
316                        index,
317                        stack,
318                        indices,
319                        lowlinks,
320                        on_stack,
321                        sccs,
322                    );
323                    let lowlink = *lowlinks
324                        .get(node_id)
325                        .unwrap()
326                        .min(lowlinks.get(neighbor_id).unwrap());
327                    lowlinks.insert(node_id.to_string(), lowlink);
328                } else if on_stack.contains(neighbor_id) {
329                    let lowlink = *lowlinks
330                        .get(node_id)
331                        .unwrap()
332                        .min(indices.get(neighbor_id).unwrap());
333                    lowlinks.insert(node_id.to_string(), lowlink);
334                }
335            }
336        }
337
338        // If node is a root node, pop the stack and create an SCC
339        if lowlinks.get(node_id) == indices.get(node_id) {
340            let mut scc = Vec::new();
341            loop {
342                let w = stack.pop().unwrap();
343                on_stack.remove(&w);
344                scc.push(w.clone());
345                if w == *node_id {
346                    break;
347                }
348            }
349            sccs.push(scc);
350        }
351    }
352}
leptos_helios/graph_features/algorithms.rs

leptos_helios/graph_features/
algorithms.rs
