cleveragents/cleveragents-core
4
0
Fork 3
Code Issues 6.0k Pull Requests 115 Actions Packages Projects Releases Wiki Activity

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
Copy Link
Copy Source

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: Epic: Post-MVP Deferred Work (#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
Priority
Backlog
State
Unverified
Type
Bug
 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
HAL9000 added
State
Verified
MoSCoW
Must have
 and removed
State
Unverified
 labels 2026-04-18 10:23:00 +00:00
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
Clear labels
auto/needs-reevaluation
Controller deferred this PR; awaiting Phase 6+ scope-evaluator or operator re-enablement.
 controller-managed
Auto-agents controller manages this PR/issue (see tools/controller/deploy/RUNBOOK.md). Remove this label to abandon controller management.
 overdue
auto/blocked-by-deps
PR blocked by an open issue dependency. Operator must close the dep (or remove the dependency link) before the merge driver can act. Auto-cleared by merge_drive when no open deps remain.
 auto/ci-timeout
Most recent merge cycle hit CI timeout. Driver excludes this PR while last merge_cycle row is < 30 min old; label persists thereafter as visible history.
 auto/claimed-implementer
Currently being processed by an implementer worker.
 auto/claimed-merge
Currently being processed by the merge driver.
 auto/claimed-reviewer
Currently being processed by a reviewer worker.
 auto/driver-down
Merge driver heartbeat stale; pipeline halted. Closed automatically on next clean tick.
 auto/invariant-violation
Detected master commit violating the strict merge invariant. Tracked as an issue (not a PR label); kept here for label completeness.
 auto/last-attempt-tier-0
In-cycle escalation: most recent attempt ran at the Tier 0 slot (`tier-0`). Slot's model defined in .opencode/models/tiers.yaml.
 auto/last-attempt-tier-1
In-cycle escalation: most recent attempt ran at the Tier 1 slot (`tier-1`). Slot's model defined in .opencode/models/tiers.yaml.
 auto/last-attempt-tier-2
In-cycle escalation: most recent attempt ran at the Tier 2 slot (`tier-2`). Slot's model defined in .opencode/models/tiers.yaml. Gated behind IMPLEMENTER_ESCALATION_TIER2_ENABLED.
 auto/last-attempt-tier-min
In-cycle escalation: most recent attempt ran at the Tier -1 slot (`tier-min`). Slot's model defined in .opencode/models/tiers.yaml. Suffix is ``-min`` (not ``--1``) so the Forgejo UI reads naturally.
 Automation Tracking
Tracking issues used by the AI Automation system for agents to communicate and report.
 auto/needs-conflict-resolution
Rebase conflict needs LLM conflict-resolver.
 auto/needs-implementer
Failing CI needs implementer attention.
 auto/postmortem
Documenting a driver incident or rollback.
 auto/ready-to-merge
Reviewer has APPROVED this PR and no later REQUEST_CHANGES is outstanding. The merge driver requires this label to even consider a PR for merging. Set by the reviewer worker on APPROVE; cleared on REQUEST_CHANGES.
 auto/restart-throttled
Train repeatedly lost master-tempo races. Driver excludes via merge_cycle until cooldown elapses; label persists as visible history.
 auto/revert
Revert PR backing out an invariant violation. Fast-tracked through the merge driver.
 auto/sentinel
Sentinel PR duplicated from upstream into a personal fork by tools/duplicate_prs_to_fork.py for pipeline testing. Lives only in the fork; the canonical pipeline never sees it.
 auto/stale-inactivity
No implementer activity for N days. Flagged for human review. Auto-cleared on next push to head branch.
 auto/unstable
Repeatedly fails on current master (>= 3 ci-fail-on-rebased-sha releases in 12 h). Excluded from driver until human triage.
 Blocked
A ticket in a blocked state and unable to complete until some other task is completed first.
Bounty
$100
A bounty of $100 for any open-source contributor who provides a MR that solves this issue
Bounty
$1000
A bounty of $1000 for any open-source contributor who provides a MR that solves this issue
Bounty
$10000
A bounty of $10000 for any open-source contributor who provides a MR that solves this issue
Bounty
$20
A bounty of $20 for any open-source contributor who provides a MR that solves this issue
Bounty
$2000
A bounty of $2000 for any open-source contributor who provides a MR that solves this issue
Bounty
$250
A bounty of $250 for any open-source contributor who provides a MR that solves this issue
Bounty
$50
A bounty of $50 for any open-source contributor who provides a MR that solves this issue
Bounty
$500
A bounty of $500 for any open-source contributor who provides a MR that solves this issue
Bounty
$5000
A bounty of $5000 for any open-source contributor who provides a MR that solves this issue
Bounty
$750
A bounty of $750 for any open-source contributor who provides a MR that solves this issue
MoSCoW
Could have
Could have feature in order to satisfy the epic/legendary.
MoSCoW
Must have
Must have feature in order to satisfy the epic/legendary.
MoSCoW
Should have
Should have feature in order to satisfy the epic/legendary.
Needs Feedback
There are questions in the ticket that can not be completed until the project owner provides clarity.
Points
1
1 man-hours worth of work for an expert with no learning curve.
Points
13
13 man-hours worth of work for an expert with no learning curve.
Points
2
2 man-hours worth of work for an expert with no learning curve.
Points
21
21 man-hours worth of work for an expert with no learning curve.
Points
3
3 man-hours worth of work for an expert with no learning curve.
Points
34
34 man-hours worth of work for an expert with no learning curve.
Points
5
5 man-hours worth of work for an expert with no learning curve.
Points
55
55 man-hours worth of work for an expert with no learning curve.
Points
8
8 man-hours worth of work for an expert with no learning curve.
Points
88
88 man-hours worth of work for an expert with no learning curve.
Priority
Backlog
This ticket has backlogged priority and is not to be worked on yet
Priority
CI Blocker
Critical priority issue that blocks CI/CD pipeline and prevents PR merges
Priority
Critical
The priority is critical
Priority
High
The priority is high
Priority
Low
The priority is low
Priority
Medium
The priority is medium
Signed-off: Owner
When an epic or legendary is in review it must be signed off by owner, tech lead, and scrum master before being marked as completed.
 Signed-off: Scrum Master
When an epic or legendary is in review it must be signed off by owner, tech lead, and scrum master before being marked as completed.
 Signed-off: Tech Lead
When an epic or legendary is in review it must be signed off by owner, tech lead, and scrum master before being marked as completed.
 Spike
A ticket for learning a tool or technology that is needed to be able to do future planning and design.
State
Completed
The ticket has been fully implemented, completed, and merged with the source code. This label should only be applied once a ticket is closed.
State
Duplicate
A ticket that represents the same content as an existing ticket.
State
In Progress
A ticket that is actively being developed.
State
In Review
A ticket that has had some code completed to implement but is waiting to pass peer review and is not yet merged in.
State
Paused
This ticket's work started but wasn't finished. It's on hold (likely in a feature branch) and will be resumed later, either due to a blocker or a delay.
State
Unverified
All new tickets start in this state. A developer may set it to show the ticket is unverified. This means we haven't agreed to work on it. It will either move to a verified state or be closed as wontdo.
State
Verified
The issue has been verified by a developer as legitimate. It will be worked on and verified tickets are now considered part of the backlog.
State
Wont Do
This ticket has been decided it wont be done. This may mean the bug has been determined to not be real (cant verify) or the feature is one we have decided we dont want to adopt.
Type
Automation
Any edits or discussion about the AI automated coding system.
Type
Bug
Something that doesnt work as intended.
Type
Discussion
Anytime a ticket represents a discussion about a subject and doesnt fall into one of the other categories.
Type
Documentation
An error or improvement needed in the documentation.
Type
Epic
Any first tier epic. That is, an epic which contains only issues as children and will not have sub-epics.
Type
Feature
Some new functionality not present.
Type
Legendary
A type of Epic which will contain other Epics.
Type
Refactor
A code change that restructures existing code without changing its external behavior.
Type
Support
Someone needs help using the project.
Type
Task
A generic task that doesnt fit into the other type categories.
Type
Testing
Work exclusively focusing on fixing or expanding testing.
No Label
MoSCoW
Must have
Priority
Backlog
State
Verified
Type
Bug
Milestone
No items
No Milestone
Projects
Clear projects
No project
Assignees
Clear assignees
aditya (Aditya Chhabra) aleenaumair (Aleena Umair) brent.edwards (Brent Edwards) CoreRasurae (Luis Mendes) drew (Drew Morris) eugen.thaci (Eugen Thaci) freemo (Jeffrey Phillips Freeman) HAL9000 (HAL 9000) HAL9001 (HAL9001) hamza.khyari (Hamza Khyari) hurui200320 (Rui Hu) justin.morris khird (Kyle Hird) org.cleveragents
No Assignees
1 Participants
Notifications
Due Date
No due date set.
Blocks
#366 Epic: Post-MVP Deferred Work
cleveragents/cleveragents-core
Reference: cleveragents/cleveragents-core#3670
Delete Branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?