Find leaf nodes (nodes that no other nodes depend on) and build dependency trees showing the full dependency chain from each leaf back to the ultimate dependencies. The graph uses natural dependency direction: - If A depends on B, the graph has an edge A → B - Leaf nodes ar
(graph: Dict[str, Set[str]], components: Dict[str, Node])
| 269 | # Only include dependencies that are actual components in our repository |
| 270 | if dep_id in components: |
| 271 | graph[comp_id].add(dep_id) |
| 272 | |
| 273 | return graph |
| 274 | |
| 275 | |
| 276 | def get_leaf_nodes(graph: Dict[str, Set[str]], components: Dict[str, Node]) -> List[str]: |
| 277 | """ |
| 278 | Find leaf nodes (nodes that no other nodes depend on) and build dependency trees |
| 279 | showing the full dependency chain from each leaf back to the ultimate dependencies. |
| 280 | |
| 281 | The graph uses natural dependency direction: |
| 282 | - If A depends on B, the graph has an edge A → B |
| 283 | - Leaf nodes are nodes that appear in no other node's dependency set |
| 284 | - Each tree shows the dependency chain: leaf → its dependencies → their dependencies, etc. |
| 285 | |
| 286 | Args: |
| 287 | graph: A dependency graph with natural direction (A→B if A depends on B) |
| 288 | |
| 289 | Returns: |
| 290 | A list of leaf nodes |
| 291 | """ |
| 292 | # First, resolve cycles to ensure we have a DAG |
| 293 | acyclic_graph = resolve_cycles(graph) |
| 294 | |
| 295 | # Find leaf nodes (nodes that no other nodes depend on) |
| 296 | leaf_nodes = set(acyclic_graph.keys()) |
| 297 | |
| 298 | valid_types = compute_valid_leaf_types(components) |
| 299 | |
| 300 | def concise_node(leaf_nodes: Set[str]) -> Set[str]: |
| 301 | concise_leaf_nodes = set() |
| 302 | for node in leaf_nodes: |
| 303 | if node.endswith("__init__"): |
| 304 | # replace by class name |
| 305 | concise_leaf_nodes.add(node.replace(".__init__", "")) |
| 306 | else: |
| 307 | concise_leaf_nodes.add(node) |
| 308 | |
| 309 | return filter_leaf_nodes(concise_leaf_nodes, components, valid_types) |
| 310 | |
| 311 | concise_leaf_nodes = concise_node(leaf_nodes) |
| 312 | if len(concise_leaf_nodes) >= LEAF_REDUCTION_THRESHOLD: |
| 313 | logger.debug(f"Leaf nodes are too many ({len(concise_leaf_nodes)}), removing dependencies of other nodes") |
| 314 | # Remove nodes that are dependencies of other nodes |
| 315 | for node, deps in acyclic_graph.items(): |
| 316 | for dep in deps: |
| 317 | leaf_nodes.discard(dep) |
| 318 | |
| 319 | concise_leaf_nodes = concise_node(leaf_nodes) |
| 320 | |
| 321 | if not leaf_nodes: |
| 322 | logger.warning("No leaf nodes found in the graph") |
| 323 | return [] |
| 324 | |
| 325 | return concise_leaf_nodes |
no test coverage detected