Skip to content

[Enhancement] Optimize edge traversal using Adjacency Lists O(1) lookup for large codebases #4

Description

@Gopesh111

Hi @userhimanshuverma ,

In models.py, the KnowledgeGraph stores edges as a flat list (edges: List[Edge]). Currently, methods like get_edges_for_node() and get_incoming_edges() use list comprehensions to iterate over the entire self.edges array.

For enterprise-scale codebases with thousands of functions and imports, this creates an $O(E)$ linear scan bottleneck every time an LLM calls the dependencies tool.

Proposed Solution

We should migrate from a flat edge list to an Adjacency List representation internally.

# Instead of a flat list, we can maintain:
outgoing_edges: Dict[str, List[Edge]] 
incoming_edges: Dict[str, List[Edge]]

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions