cleveragents/cleveragents-core

Fork 3

UAT: PureGraph.topological_order() uses dict insertion order instead of actual topological sort — graph edges are ignored #1899

New issue

Open

opened 2026-04-03 00:09:59 +00:00 by freemo · 2 comments

freemo commented

2026-04-03 00:09:59 +00:00

Owner

Metadata

Branch: fix/m6-pure-graph-topological-order
Commit Message: fix(langgraph): implement real topological sort in PureGraph.topological_order()
Milestone: v3.5.0
Parent Epic: #390

Background and Context

The PureGraph.topological_order() method in src/cleveragents/langgraph/pure_graph.py does not perform a real topological sort. Instead, it returns nodes in their dictionary insertion order, completely ignoring the graph's edge definitions. The method comment even acknowledges this: # Simple linear order based on insertion; not full topo sort.

This is a correctness bug in the graph execution engine. Any use of PureGraph.execute() where nodes are not inserted in topological order will produce incorrect results — functions are called in the wrong sequence, yielding wrong outputs.

File: src/cleveragents/langgraph/pure_graph.py
Lines: 14–17

Buggy code:

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"]

Current Behavior

topological_order() returns nodes in dict insertion order, ignoring edge definitions entirely.

Steps to reproduce:

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

# Nodes inserted in order c, a, b — but graph edges define a -> b -> c
graph = PureGraph(
    name='test',
    nodes={
        'c': NodeConfig(name='c', type=NodeType.FUNCTION, function='func_c'),
        'a': NodeConfig(name='a', type=NodeType.FUNCTION, function='func_a'),
        'b': NodeConfig(name='b', type=NodeType.FUNCTION, function='func_b'),
    },
    edges=[
        Edge(source='start', target='a'),
        Edge(source='a', target='b'),
        Edge(source='b', target='c'),
        Edge(source='c', target='end'),
    ]
)

order = graph.topological_order()
print(f'Order: {order}')  # Actual: ['start', 'c', 'a', 'b', 'end'] — WRONG!
                           # Expected: ['start', 'a', 'b', 'c', 'end']

results = []
fn_registry = {
    'func_a': lambda v: (results.append('a'), v + 1)[1],
    'func_b': lambda v: (results.append('b'), v * 2)[1],
    'func_c': lambda v: (results.append('c'), v - 1)[1],
}
result = graph.execute(fn_registry, initial=5)
print(f'Execution order: {results}')  # Actual: ['c', 'a', 'b'] — WRONG!
                                       # Expected: ['a', 'b', 'c']
print(f'Result: {result}')  # Actual: 10 (wrong), Expected: 11 (5+1=6, 6*2=12, 12-1=11)

Actual behavior: Returns nodes in dict insertion order (['start', 'c', 'a', 'b', 'end']), ignoring the edges. execute() calls functions in the wrong order, producing incorrect results.

Expected Behavior

topological_order() should return nodes in a valid topological order respecting the graph's edge definitions. For the example above: ['start', 'a', 'b', 'c', 'end'].

Root cause: The implementation is a known stub that needs to be replaced with a proper topological sort algorithm (e.g., Kahn's algorithm or DFS-based).

Impact: Any use of PureGraph.execute() where nodes are not inserted in topological order will produce incorrect results. This is a correctness bug in the graph execution engine.

Discovery: Found by UAT tester instance uat-tester-3994408-1775170787 testing the LangGraph integration feature area.

Acceptance Criteria

PureGraph.topological_order() returns nodes in a valid topological order that respects all edge definitions in the graph.
The method correctly handles graphs where nodes are inserted in any order (not just topological order).
The method detects and raises an appropriate error for graphs with cycles (which are invalid for topological sort).
PureGraph.execute() produces correct results when nodes are inserted in non-topological order.
All existing tests continue to pass.

Supporting Information

File: src/cleveragents/langgraph/pure_graph.py, lines 14–17
Suggested algorithms: Kahn's algorithm (BFS-based) or DFS-based topological sort
The edges field on PureGraph contains the full edge list needed to build the adjacency graph for sorting

Subtasks

Implement a proper topological sort algorithm (Kahn's or DFS-based) in PureGraph.topological_order() using the graph's edges field
Add cycle detection with a descriptive error raised for cyclic graphs
Tests (Behave): Add BDD scenario — nodes inserted in non-topological order are returned in correct topological order
Tests (Behave): Add BDD scenario — cyclic graph raises an appropriate error
Tests (Behave): Add BDD scenario — execute() produces correct results when nodes are in non-topological insertion order
Tests (Robot): Add integration test verifying end-to-end execution order correctness
Verify coverage >= 97% via nox -s coverage_report
Run nox (all default sessions), fix any errors

Definition of Done

This issue is complete when:

All subtasks above are completed and checked off.
PureGraph.topological_order() correctly respects edge definitions regardless of node insertion order.
A Git commit is created where the first line of the commit message matches the Commit Message in Metadata exactly, followed by a blank line, then additional lines providing relevant details about the implementation.
The commit is pushed to the remote on the branch matching the Branch in Metadata exactly.
The commit is submitted as a pull request to master, reviewed, and merged before this issue is marked done.
All nox stages pass.
Coverage >= 97%

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

## Metadata - **Branch**: `fix/m6-pure-graph-topological-order` - **Commit Message**: `fix(langgraph): implement real topological sort in PureGraph.topological_order()` - **Milestone**: v3.5.0 - **Parent Epic**: #390 ## Background and Context The `PureGraph.topological_order()` method in `src/cleveragents/langgraph/pure_graph.py` does not perform a real topological sort. Instead, it returns nodes in their dictionary insertion order, completely ignoring the graph's edge definitions. The method comment even acknowledges this: `# Simple linear order based on insertion; not full topo sort`. This is a correctness bug in the graph execution engine. Any use of `PureGraph.execute()` where nodes are not inserted in topological order will produce incorrect results — functions are called in the wrong sequence, yielding wrong outputs. **File**: `src/cleveragents/langgraph/pure_graph.py` **Lines**: 14–17 **Buggy code**: ```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"] ``` ## Current Behavior `topological_order()` returns nodes in dict insertion order, ignoring edge definitions entirely. **Steps to reproduce**: ```python from cleveragents.langgraph.pure_graph import PureGraph from cleveragents.langgraph.nodes import NodeConfig, NodeType, Edge # Nodes inserted in order c, a, b — but graph edges define a -> b -> c graph = PureGraph( name='test', nodes={ 'c': NodeConfig(name='c', type=NodeType.FUNCTION, function='func_c'), 'a': NodeConfig(name='a', type=NodeType.FUNCTION, function='func_a'), 'b': NodeConfig(name='b', type=NodeType.FUNCTION, function='func_b'), }, edges=[ Edge(source='start', target='a'), Edge(source='a', target='b'), Edge(source='b', target='c'), Edge(source='c', target='end'), ] ) order = graph.topological_order() print(f'Order: {order}') # Actual: ['start', 'c', 'a', 'b', 'end'] — WRONG! # Expected: ['start', 'a', 'b', 'c', 'end'] results = [] fn_registry = { 'func_a': lambda v: (results.append('a'), v + 1)[1], 'func_b': lambda v: (results.append('b'), v * 2)[1], 'func_c': lambda v: (results.append('c'), v - 1)[1], } result = graph.execute(fn_registry, initial=5) print(f'Execution order: {results}') # Actual: ['c', 'a', 'b'] — WRONG! # Expected: ['a', 'b', 'c'] print(f'Result: {result}') # Actual: 10 (wrong), Expected: 11 (5+1=6, 6*2=12, 12-1=11) ``` **Actual behavior**: Returns nodes in dict insertion order (`['start', 'c', 'a', 'b', 'end']`), ignoring the edges. `execute()` calls functions in the wrong order, producing incorrect results. ## Expected Behavior `topological_order()` should return nodes in a valid topological order respecting the graph's edge definitions. For the example above: `['start', 'a', 'b', 'c', 'end']`. **Root cause**: The implementation is a known stub that needs to be replaced with a proper topological sort algorithm (e.g., Kahn's algorithm or DFS-based). **Impact**: Any use of `PureGraph.execute()` where nodes are not inserted in topological order will produce incorrect results. This is a correctness bug in the graph execution engine. **Discovery**: Found by UAT tester instance `uat-tester-3994408-1775170787` testing the LangGraph integration feature area. ## Acceptance Criteria - `PureGraph.topological_order()` returns nodes in a valid topological order that respects all edge definitions in the graph. - The method correctly handles graphs where nodes are inserted in any order (not just topological order). - The method detects and raises an appropriate error for graphs with cycles (which are invalid for topological sort). - `PureGraph.execute()` produces correct results when nodes are inserted in non-topological order. - All existing tests continue to pass. ## Supporting Information - **File**: `src/cleveragents/langgraph/pure_graph.py`, lines 14–17 - Suggested algorithms: Kahn's algorithm (BFS-based) or DFS-based topological sort - The `edges` field on `PureGraph` contains the full edge list needed to build the adjacency graph for sorting ## Subtasks - [ ] Implement a proper topological sort algorithm (Kahn's or DFS-based) in `PureGraph.topological_order()` using the graph's `edges` field - [ ] Add cycle detection with a descriptive error raised for cyclic graphs - [ ] Tests (Behave): Add BDD scenario — nodes inserted in non-topological order are returned in correct topological order - [ ] Tests (Behave): Add BDD scenario — cyclic graph raises an appropriate error - [ ] Tests (Behave): Add BDD scenario — `execute()` produces correct results when nodes are in non-topological insertion order - [ ] Tests (Robot): Add integration test verifying end-to-end execution order correctness - [ ] Verify coverage >= 97% via `nox -s coverage_report` - [ ] Run `nox` (all default sessions), fix any errors ## Definition of Done This issue is complete when: - All subtasks above are completed and checked off. - `PureGraph.topological_order()` correctly respects edge definitions regardless of node insertion order. - A Git commit is created where the **first line** of the commit message matches the Commit Message in Metadata exactly, followed by a blank line, then additional lines providing relevant details about the implementation. - The commit is pushed to the remote on the branch matching the **Branch** in Metadata exactly. - The commit is submitted as a **pull request** to `master`, reviewed, and **merged** before this issue is marked done. - All nox stages pass. - Coverage >= 97% --- **Automated by CleverAgents Bot** Supervisor: UAT Testing | Agent: ca-new-issue-creator

freemo added this to the v3.5.0 milestone

2026-04-03 00:10:31 +00:00

freemo commented

2026-04-03 00:12:57 +00:00

Author

Owner

Issue triaged by project owner:

State: Verified
MoSCoW: MoSCoW/Should Have — bug or error handling improvement.

Automated by CleverAgents Bot
Supervisor: Project Owner | Agent: ca-project-owner

Issue triaged by project owner: - **State**: Verified - **MoSCoW**: MoSCoW/Should Have — bug or error handling improvement. --- **Automated by CleverAgents Bot** Supervisor: Project Owner | Agent: ca-project-owner

freemo added a new dependency

2026-04-03 00:14:27 +00:00

#390 Legendary: Autonomy Hardening & Server Infrastructure (M6)

freemo referenced this issue

2026-04-03 00:18:37 +00:00

[UAT-SUPERVISOR] Progress Report — Cycle 481 — v3.7.0 #1938

freemo commented

2026-04-03 00:19:52 +00:00

Author

Owner

Issue triaged by project owner: