lc_langgraph/compiled/
validate.rs

1// crates/lc-langgraph/src/compiled/validate.rs
2//! CompiledGraph validation methods: validate, validate_duplicate_edges,
3//! validate_unreachable_nodes, validate_cycles, and helper graph-traversal methods
4
5use super::graph::CompiledGraph;
6use crate::edge::GraphEdge;
7use crate::errors::{GraphError, GraphResult};
8use crate::state::StateSchema;
9use crate::{END, START};
10
11impl<S: StateSchema> CompiledGraph<S> {
12    /// Validate the graph structure: node references, duplicate edges,
13    /// unreachable nodes, and cycles with no path to `END`.
14    pub fn validate(&self) -> GraphResult<()> {
15        for edge in &self.edges {
16            match edge {
17                GraphEdge::Fixed { source, target } => {
18                    if source != START && !self.nodes.contains_key(source) {
19                        return Err(GraphError::ValidationError(format!(
20                            "Source node '{}' not found",
21                            source
22                        )));
23                    }
24                    if target != END && !self.nodes.contains_key(target) {
25                        return Err(GraphError::ValidationError(format!(
26                            "Target node '{}' not found",
27                            target
28                        )));
29                    }
30                    if target == START {
31                        return Err(GraphError::ValidationError(
32                            "Edge cannot target START node".to_string(),
33                        ));
34                    }
35                }
36                GraphEdge::Conditional {
37                    source,
38                    router_name,
39                    targets,
40                    default_target,
41                } => {
42                    if source != START && !self.nodes.contains_key(source) {
43                        return Err(GraphError::ValidationError(format!(
44                            "Source node '{}' not found",
45                            source
46                        )));
47                    }
48                    if !self.conditional_routers.contains_key(router_name) {
49                        return Err(GraphError::ValidationError(format!(
50                            "Router '{}' not found",
51                            router_name
52                        )));
53                    }
54                    for (route, target) in targets {
55                        if target != END && !self.nodes.contains_key(target) {
56                            return Err(GraphError::ValidationError(format!(
57                                "Target '{}' for route '{}' not found",
58                                target, route
59                            )));
60                        }
61                        if target == START {
62                            return Err(GraphError::ValidationError(
63                                "Conditional edge cannot target START node".to_string(),
64                            ));
65                        }
66                    }
67                    if let Some(default) = default_target {
68                        if default != END && !self.nodes.contains_key(default) {
69                            return Err(GraphError::ValidationError(format!(
70                                "Default target '{}' not found",
71                                default
72                            )));
73                        }
74                    }
75                }
76                GraphEdge::FanOut { source, targets } => {
77                    if source != START && !self.nodes.contains_key(source) {
78                        return Err(GraphError::ValidationError(format!(
79                            "FanOut source node '{}' not found",
80                            source
81                        )));
82                    }
83                    for target in targets {
84                        if target != END && !self.nodes.contains_key(target) {
85                            return Err(GraphError::ValidationError(format!(
86                                "FanOut target node '{}' not found",
87                                target
88                            )));
89                        }
90                    }
91                }
92                GraphEdge::FanIn { sources, target } => {
93                    for source in sources {
94                        if source != START && !self.nodes.contains_key(source) {
95                            return Err(GraphError::ValidationError(format!(
96                                "FanIn source node '{}' not found",
97                                source
98                            )));
99                        }
100                    }
101                    if target != END && !self.nodes.contains_key(target) {
102                        return Err(GraphError::ValidationError(format!(
103                            "FanIn target node '{}' not found",
104                            target
105                        )));
106                    }
107                }
108            }
109        }
110
111        self.validate_duplicate_edges()?;
112        self.validate_unreachable_nodes()?;
113        self.validate_cycles()?;
114
115        Ok(())
116    }
117
118    fn validate_duplicate_edges(&self) -> GraphResult<()> {
119        let mut seen_fixed: std::collections::HashSet<(String, String)> =
120            std::collections::HashSet::new();
121
122        for edge in &self.edges {
123            if let GraphEdge::Fixed { source, target } = edge {
124                let key = (source.clone(), target.clone());
125                if seen_fixed.contains(&key) {
126                    return Err(GraphError::DuplicateEdgeError(format!(
127                        "Duplicate edge: {} -> {}",
128                        source, target
129                    )));
130                }
131                seen_fixed.insert(key);
132            }
133        }
134        Ok(())
135    }
136
137    fn validate_unreachable_nodes(&self) -> GraphResult<()> {
138        let reachable = self.compute_reachable_nodes();
139
140        for node_name in self.nodes.keys() {
141            if !reachable.contains(node_name) {
142                return Err(GraphError::OrphanNodeError(format!(
143                    "Unreachable node: {}",
144                    node_name
145                )));
146            }
147        }
148        Ok(())
149    }
150
151    fn compute_reachable_nodes(&self) -> std::collections::HashSet<String> {
152        let mut reachable: std::collections::HashSet<String> = std::collections::HashSet::new();
153        let mut to_visit: Vec<String> = vec![self.entry_point.clone()];
154
155        while let Some(current) = to_visit.pop() {
156            if reachable.contains(&current) || current == END {
157                continue;
158            }
159            reachable.insert(current.clone());
160
161            for edge in &self.edges {
162                // 0.22.0 H-A10 fix: FanIn edges carry multiple sources, so
163                // `edge.source()` (constant `"__fanin__"`) never matches a
164                // node name and a standard fan-out+fan-in topology was
165                // rejected as "Unreachable node". Handle FanIn on every pass:
166                // its target is reachable once all of its sources are.
167                if let GraphEdge::FanIn { sources, target } = edge {
168                    if sources.iter().all(|s| reachable.contains(s))
169                        && !reachable.contains(target)
170                        && target != END
171                    {
172                        to_visit.push(target.clone());
173                    }
174                    continue;
175                }
176                if edge.source() == current {
177                    match edge {
178                        GraphEdge::Fixed { target, .. } => {
179                            if !reachable.contains(target) && target != END {
180                                to_visit.push(target.clone());
181                            }
182                        }
183                        GraphEdge::Conditional {
184                            targets,
185                            default_target,
186                            ..
187                        } => {
188                            for target in targets.values() {
189                                if !reachable.contains(target) && target != END {
190                                    to_visit.push(target.clone());
191                                }
192                            }
193                            if let Some(default) = default_target {
194                                if !reachable.contains(default) && default != END {
195                                    to_visit.push(default.clone());
196                                }
197                            }
198                        }
199                        GraphEdge::FanOut { targets, .. } => {
200                            for target in targets {
201                                if !reachable.contains(target) && target != END {
202                                    to_visit.push(target.clone());
203                                }
204                            }
205                        }
206                        GraphEdge::FanIn { .. } => {}
207                    }
208                }
209            }
210        }
211        reachable
212    }
213
214    fn validate_cycles(&self) -> GraphResult<()> {
215        let reachable = self.compute_reachable_nodes();
216        let end_reachable = self.compute_end_reachable_nodes();
217
218        for node in &reachable {
219            if !end_reachable.contains(node) {
220                return Err(GraphError::InfiniteCycleError(format!(
221                    "Node '{}' in cycle with no path to END",
222                    node
223                )));
224            }
225        }
226        Ok(())
227    }
228
229    fn compute_end_reachable_nodes(&self) -> std::collections::HashSet<String> {
230        let mut end_reachable: std::collections::HashSet<String> = std::collections::HashSet::new();
231        end_reachable.insert(END.to_string());
232
233        let mut changed = true;
234        while changed {
235            changed = false;
236            for edge in &self.edges {
237                match edge {
238                    GraphEdge::Fixed { source, target } => {
239                        if end_reachable.contains(target) && !end_reachable.contains(source) {
240                            end_reachable.insert(source.clone());
241                            changed = true;
242                        }
243                    }
244                    GraphEdge::Conditional {
245                        source,
246                        targets,
247                        default_target,
248                        ..
249                    } => {
250                        let any_target_reaches_end =
251                            targets.values().any(|t| end_reachable.contains(t))
252                                || default_target
253                                    .as_ref()
254                                    .is_some_and(|d| end_reachable.contains(d));
255                        if any_target_reaches_end && !end_reachable.contains(source) {
256                            end_reachable.insert(source.clone());
257                            changed = true;
258                        }
259                    }
260                    GraphEdge::FanOut { source, targets } => {
261                        let all_targets_reach_end =
262                            targets.iter().all(|t| end_reachable.contains(t));
263                        if all_targets_reach_end && !end_reachable.contains(source) {
264                            end_reachable.insert(source.clone());
265                            changed = true;
266                        }
267                    }
268                    GraphEdge::FanIn { sources, target } => {
269                        if end_reachable.contains(target) {
270                            for source in sources {
271                                if !end_reachable.contains(source) {
272                                    end_reachable.insert(source.clone());
273                                    changed = true;
274                                }
275                            }
276                        }
277                    }
278                }
279            }
280        }
281        end_reachable
282    }
283}
lc_langgraph/compiled/validate.rs

lc_langgraph/compiled/
validate.rs
