UAT: `PureGraph.topological_order()` returns insertion order instead of a real topological sort, causing incorrect node execution order #3835

New issue

Open

opened 2026-04-06 06:50:44 +00:00 by freemo · 0 comments

freemo commented

2026-04-06 06:50:44 +00:00

Owner

Metadata

Branch: fix/pure-graph-topological-sort
Commit Message: fix(langgraph): implement real topological sort in PureGraph.topological_order()
Milestone: Backlog
Parent Epic: #392

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

Background

The PureGraph.topological_order() method in src/cleveragents/langgraph/pure_graph.py contains an acknowledged placeholder implementation that does not perform a real topological sort. The comment in the code itself reads: "Simple linear order based on insertion; not full topo sort". The execute() method relies on topological_order() to determine execution sequence, meaning any graph whose nodes were added in a different order than their execution dependencies will execute nodes in the wrong order.

What was tested

The PureGraph.topological_order() method in src/cleveragents/langgraph/pure_graph.py and its use in PureGraph.execute().

Expected behavior (from spec)

The spec describes graph-based execution where nodes and edges define the execution flow. A topological sort should return nodes in an order where each node comes after all its predecessors (respecting edge dependencies). For a graph A→B→C, the order should be ["start", "A", "B", "C", "end"] regardless of the order in which nodes were added to the graph.

Actual behavior

The PureGraph.topological_order() method does NOT perform a real topological sort:

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". This means:

If nodes are added in a different order than their execution dependencies, they will execute in the wrong order
For a graph with nodes added as [C, B, A] but edges A→B→C, the execution order will be ["start", "C", "B", "A", "end"] — completely backwards
The execute() method relies on topological_order() to determine execution sequence, so it will execute nodes in the wrong order

Code locations

src/cleveragents/langgraph/pure_graph.py lines 15–19 — topological_order() method
src/cleveragents/langgraph/pure_graph.py lines 21–29 — execute() method (uses topological_order())

Steps to reproduce

from cleveragents.langgraph.pure_graph import PureGraph
from cleveragents.langgraph.nodes import NodeConfig, NodeType, Edge

# Create graph with nodes added in reverse dependency order
graph = PureGraph(
    name="test",
    nodes={
        "start": NodeConfig(name="start", type=NodeType.START),
        "c": NodeConfig(name="c", type=NodeType.FUNCTION, function="step_c"),
        "b": NodeConfig(name="b", type=NodeType.FUNCTION, function="step_b"),
        "a": NodeConfig(name="a", type=NodeType.FUNCTION, function="step_a"),
        "end": NodeConfig(name="end", type=NodeType.END),
    },
    edges=[
        Edge(source="start", target="a"),
        Edge(source="a", target="b"),
        Edge(source="b", target="c"),
        Edge(source="c", target="end"),
    ]
)

# Expected: ["start", "a", "b", "c", "end"]
# Actual:   ["start", "c", "b", "a", "end"]  (insertion order, not topological)
print(graph.topological_order())

Impact

Any code using PureGraph.execute() with nodes added in non-topological insertion order will execute nodes in the wrong sequence. This is a correctness bug in the graph execution engine.

Subtasks

Write a TDD issue-capture Behave scenario (tagged @tdd_expected_fail) that demonstrates the incorrect ordering when nodes are added in non-topological insertion order
Implement a real topological sort (e.g., Kahn's algorithm or DFS-based) in PureGraph.topological_order() using the graph's edges to determine dependency order
Ensure topological_order() raises a descriptive error (e.g., CyclicGraphError) if a cycle is detected in the graph
Remove or update the misleading comment # Simple linear order based on insertion; not full topo sort
Verify PureGraph.execute() correctly uses the new topological order for node execution sequencing
Update or add Behave unit tests (in features/) covering: correct order for linear graph, correct order when nodes added in reverse, branching/diamond graphs, and cycle detection
Run nox to confirm all quality gates pass

Definition of Done

PureGraph.topological_order() returns nodes in a valid topological order respecting all edge dependencies
The method correctly handles nodes added in any insertion order
Cycle detection raises a descriptive exception rather than silently producing incorrect output
PureGraph.execute() executes nodes in the correct dependency-respecting order
All Behave unit tests pass (nox -e unit_tests)
Pyright type checking passes with no errors (nox -e typecheck)
Linting passes (nox -e lint)
All nox stages pass
Coverage >= 97%

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

## Metadata - **Branch**: `fix/pure-graph-topological-sort` - **Commit Message**: `fix(langgraph): implement real topological sort in PureGraph.topological_order()` - **Milestone**: Backlog - **Parent Epic**: #392 > **Backlog note:** This issue was discovered during autonomous operation > on milestone v3.2.0. It does not block milestone completion and has been > placed in the backlog for human review and future milestone assignment. ## Background The `PureGraph.topological_order()` method in `src/cleveragents/langgraph/pure_graph.py` contains an acknowledged placeholder implementation that does **not** perform a real topological sort. The comment in the code itself reads: *"Simple linear order based on insertion; not full topo sort"*. The `execute()` method relies on `topological_order()` to determine execution sequence, meaning any graph whose nodes were added in a different order than their execution dependencies will execute nodes in the wrong order. ## What was tested The `PureGraph.topological_order()` method in `src/cleveragents/langgraph/pure_graph.py` and its use in `PureGraph.execute()`. ## Expected behavior (from spec) The spec describes graph-based execution where nodes and edges define the execution flow. A topological sort should return nodes in an order where each node comes after all its predecessors (respecting edge dependencies). For a graph A→B→C, the order should be `["start", "A", "B", "C", "end"]` regardless of the order in which nodes were added to the graph. ## Actual behavior The `PureGraph.topological_order()` method does **NOT** perform a real topological sort: ```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"*. This means: 1. If nodes are added in a different order than their execution dependencies, they will execute in the wrong order 2. For a graph with nodes added as `[C, B, A]` but edges `A→B→C`, the execution order will be `["start", "C", "B", "A", "end"]` — completely backwards 3. The `execute()` method relies on `topological_order()` to determine execution sequence, so it will execute nodes in the wrong order ## Code locations - `src/cleveragents/langgraph/pure_graph.py` lines 15–19 — `topological_order()` method - `src/cleveragents/langgraph/pure_graph.py` lines 21–29 — `execute()` method (uses `topological_order()`) ## Steps to reproduce ```python from cleveragents.langgraph.pure_graph import PureGraph from cleveragents.langgraph.nodes import NodeConfig, NodeType, Edge # Create graph with nodes added in reverse dependency order graph = PureGraph( name="test", nodes={ "start": NodeConfig(name="start", type=NodeType.START), "c": NodeConfig(name="c", type=NodeType.FUNCTION, function="step_c"), "b": NodeConfig(name="b", type=NodeType.FUNCTION, function="step_b"), "a": NodeConfig(name="a", type=NodeType.FUNCTION, function="step_a"), "end": NodeConfig(name="end", type=NodeType.END), }, edges=[ Edge(source="start", target="a"), Edge(source="a", target="b"), Edge(source="b", target="c"), Edge(source="c", target="end"), ] ) # Expected: ["start", "a", "b", "c", "end"] # Actual: ["start", "c", "b", "a", "end"] (insertion order, not topological) print(graph.topological_order()) ``` ## Impact Any code using `PureGraph.execute()` with nodes added in non-topological insertion order will execute nodes in the wrong sequence. This is a correctness bug in the graph execution engine. ## Subtasks - [ ] Write a TDD issue-capture Behave scenario (tagged `@tdd_expected_fail`) that demonstrates the incorrect ordering when nodes are added in non-topological insertion order - [ ] Implement a real topological sort (e.g., Kahn's algorithm or DFS-based) in `PureGraph.topological_order()` using the graph's `edges` to determine dependency order - [ ] Ensure `topological_order()` raises a descriptive error (e.g., `CyclicGraphError`) if a cycle is detected in the graph - [ ] Remove or update the misleading comment `# Simple linear order based on insertion; not full topo sort` - [ ] Verify `PureGraph.execute()` correctly uses the new topological order for node execution sequencing - [ ] Update or add Behave unit tests (in `features/`) covering: correct order for linear graph, correct order when nodes added in reverse, branching/diamond graphs, and cycle detection - [ ] Run `nox` to confirm all quality gates pass ## Definition of Done - [ ] `PureGraph.topological_order()` returns nodes in a valid topological order respecting all edge dependencies - [ ] The method correctly handles nodes added in any insertion order - [ ] Cycle detection raises a descriptive exception rather than silently producing incorrect output - [ ] `PureGraph.execute()` executes nodes in the correct dependency-respecting order - [ ] All Behave unit tests pass (`nox -e unit_tests`) - [ ] Pyright type checking passes with no errors (`nox -e typecheck`) - [ ] Linting passes (`nox -e lint`) - [ ] All nox stages pass - [ ] Coverage >= 97% --- **Automated by CleverAgents Bot** Supervisor: UAT Testing | Agent: ca-new-issue-creator

freemo added a new dependency

2026-04-06 06:50:57 +00:00

#392 Epic: Actor YAML & Compiler

freemo referenced this issue

2026-04-06 06:55:25 +00:00

[Automated] CleverAgents Build Session - 2026-04-06 #3775

freemo added the

Points

label

2026-04-06 06:56:49 +00:00

freemo referenced this issue

2026-04-06 07:04:26 +00:00