UAT: `PureGraph.topological_order()` uses dict insertion order instead of actual topological sort — ignores edge definitions entirely #3670

New issue

Open

opened 2026-04-05 21:19:40 +00:00 by freemo · 0 comments

freemo commented

2026-04-05 21:19:40 +00:00

Owner

Metadata

Branch: fix/pure-graph-topological-sort
Commit Message: fix(langgraph): implement proper topological sort in PureGraph.topological_order() using edge definitions
Milestone: (none — backlog)
Parent Epic: #366

Background

PureGraph in src/cleveragents/langgraph/pure_graph.py is a utility class for constructing and executing simple directed graphs. Its topological_order() method is supposed to return nodes in topological execution order (respecting edge dependencies).

Current Behavior

PureGraph.topological_order() in src/cleveragents/langgraph/pure_graph.py (lines 18–21) completely ignores the edges field and simply returns nodes in dict insertion order:

def topological_order(self) -> list[str]:
    # Simple linear order based on insertion; not full topo sort
    order: list[str] = [n for n in self.nodes if n not in {"start", "end"}]
    return ["start", *order, "end"]

The comment even acknowledges this: "Simple linear order based on insertion; not full topo sort".

Expected Behavior

topological_order() should perform an actual topological sort using the edges field to determine the correct execution order. For example:

nodes: {start, A, B, C, end}
edges: start→A, start→B, A→C, B→C, C→end

Correct topological order: [start, A, B, C, end] (or [start, B, A, C, end])
Current behavior: [start, A, B, C, end] (happens to be correct only by insertion order coincidence)

But for:

nodes: {start, C, B, A, end}  (inserted in reverse order)
edges: start→A, A→B, B→C, C→end

Correct topological order: [start, A, B, C, end]
Current behavior: [start, C, B, A, end] (WRONG — C is executed before A and B)

Code Location

src/cleveragents/langgraph/pure_graph.py lines 18–21: topological_order()

Impact

PureGraph.execute() (lines 23–32) calls topological_order() to determine execution order. If nodes are not inserted in topological order, functions will execute in the wrong order, producing incorrect results. This is a silent correctness bug — no error is raised, but the output is wrong.

Subtasks

Implement proper topological sort using Kahn's algorithm or DFS-based sort
Use self.edges to build the adjacency list for the sort
Handle cycles gracefully (raise ValueError if a cycle is detected)
Write Behave unit tests verifying correct topological order for various graph shapes
Verify all nox stages pass; coverage ≥ 97%

Definition of Done

topological_order() returns nodes in correct topological order based on edges
Cycles are detected and raise ValueError
Unit tests pass for various graph topologies
All nox stages pass
Coverage >= 97%

Backlog note: This issue was discovered during autonomous operation
on milestone v3.6.0. It does not block milestone completion and has been
placed in the backlog for human review and future milestone assignment.

Automated by CleverAgents Bot
Supervisor: UAT Testing | Agent: ca-new-issue-creator

## Metadata - **Branch**: `fix/pure-graph-topological-sort` - **Commit Message**: `fix(langgraph): implement proper topological sort in PureGraph.topological_order() using edge definitions` - **Milestone**: *(none — backlog)* - **Parent Epic**: #366 ## Background `PureGraph` in `src/cleveragents/langgraph/pure_graph.py` is a utility class for constructing and executing simple directed graphs. Its `topological_order()` method is supposed to return nodes in topological execution order (respecting edge dependencies). ## Current Behavior `PureGraph.topological_order()` in `src/cleveragents/langgraph/pure_graph.py` (lines 18–21) completely ignores the `edges` field and simply returns nodes in dict insertion order: ```python def topological_order(self) -> list[str]: # Simple linear order based on insertion; not full topo sort order: list[str] = [n for n in self.nodes if n not in {"start", "end"}] return ["start", *order, "end"] ``` The comment even acknowledges this: "Simple linear order based on insertion; not full topo sort". ## Expected Behavior `topological_order()` should perform an actual topological sort using the `edges` field to determine the correct execution order. For example: ``` nodes: {start, A, B, C, end} edges: start→A, start→B, A→C, B→C, C→end ``` Correct topological order: `[start, A, B, C, end]` (or `[start, B, A, C, end]`) Current behavior: `[start, A, B, C, end]` (happens to be correct only by insertion order coincidence) But for: ``` nodes: {start, C, B, A, end} (inserted in reverse order) edges: start→A, A→B, B→C, C→end ``` Correct topological order: `[start, A, B, C, end]` Current behavior: `[start, C, B, A, end]` (**WRONG** — C is executed before A and B) ## Code Location - `src/cleveragents/langgraph/pure_graph.py` lines 18–21: `topological_order()` ## Impact `PureGraph.execute()` (lines 23–32) calls `topological_order()` to determine execution order. If nodes are not inserted in topological order, functions will execute in the wrong order, producing incorrect results. This is a silent correctness bug — no error is raised, but the output is wrong. ## Subtasks - [ ] Implement proper topological sort using Kahn's algorithm or DFS-based sort - [ ] Use `self.edges` to build the adjacency list for the sort - [ ] Handle cycles gracefully (raise `ValueError` if a cycle is detected) - [ ] Write Behave unit tests verifying correct topological order for various graph shapes - [ ] Verify all nox stages pass; coverage ≥ 97% ## Definition of Done - [ ] `topological_order()` returns nodes in correct topological order based on edges - [ ] Cycles are detected and raise `ValueError` - [ ] Unit tests pass for various graph topologies - [ ] All nox stages pass - [ ] Coverage >= 97% > **Backlog note:** This issue was discovered during autonomous operation > on milestone v3.6.0. It does not block milestone completion and has been > placed in the backlog for human review and future milestone assignment. --- **Automated by CleverAgents Bot** Supervisor: UAT Testing | Agent: ca-new-issue-creator

freemo added the

labels

2026-04-05 21:19:44 +00:00

freemo added a new dependency

2026-04-05 21:19:47 +00:00

#366 Epic: Post-MVP Deferred Work