Topologically Order Tool Calls with Argument Dependencies

hardPROTool Use & Function CallingAI AgentsAI Agents 1

Problem Statement

A set of tool calls reference each other's outputs. Produce a valid execution order (dependencies first), or detect a cycle. Break ties deterministically by step id.

Background

Each call has an integer id and a list of deps (ids it must run after). This is a topological sort. Use Kahn's algorithm: repeatedly emit the ready node (in-degree 0) with the smallest id. If not all nodes are emitted, there is a cycle.

Your Task

Implement:

def order_calls(calls):

calls: list of {"id": int, "deps": [int, ...]}.
Return the ordered list of ids, or the string "CYCLE" if no valid order exists.

Input Format

calls (list of dicts).

Output Format

A list of ints, or "CYCLE".

Sample

print(order_calls([{"id":1,"deps":[2]},{"id":2,"deps":[]}]))

Output:

[2, 1]

Example

Input

print(order_calls([{"id":1,"deps":[2]},{"id":2,"deps":[]}]))

Output

[2, 1]

Reasoning

Initialize dependency tracking: Node 1 depends on Node 2, so Node 1's in-degree is 1 and Node 2's in-degree is 0. The adjacency list records that Node 2 must execute before Node 1.
Identify ready nodes: Only Node 2 has an in-degree of 0, so it is the sole candidate for the first execution step.
Process Node 2: Emit Node 2 to the result list. Decrement the in-degree of its dependent, Node 1, from 1 to 0, making Node 1 ready for execution.
Process Node 1: With Node 1 now having an in-degree of 0, it is emitted next. No further nodes remain in the queue.
Verify completion: The result list contains both nodes (length 2), matching the total number of input calls, confirming no cycle exists.
The final output is [2, 1]

Constraints

Ids are unique ints; deps reference existing ids.
Among ready nodes, always emit the smallest id (deterministic).
Return "CYCLE" if a topological order does not exist.

Learn this in

Tool Use & Function CallingAgent Engineering Study Plan Advanced GraphsDSA Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primerPREVIEW

1. Background Knowledge

This problem is a classic application of topological sorting on a Directed Acyclic Graph (DAG). In the context of tool calling, each tool call is a node, and a dependency (deps) represents a directed edge from the dependency to the dependent call. A valid execution order is a linear ordering of all nodes such that for every directed edge $u \to v$ , node $u$ appears before node $v$ in the sequence. If the graph contains a cycle, no such ordering exists, and the system must report a CYCLE.

The key constraint here is deterministic tie-breaking. Standard topological sorts can produce multiple valid orderings. To ensure a unique, reproducible output, we must always select the ready node (in-degree 0) with the smallest id at each step. This transforms the problem from a simple queue-based traversal into a priority-queue-based selection process.

Kahn’s algorithm is the standard iterative approach for topological sorting. It works by repeatedly removing nodes with no incoming edges (in-degree 0), decrementing the in-degree of their neighbors, and adding newly freed nodes to the "ready" set. If the number of processed nodes is less than the total number of nodes, a cycle exists.

2. Algorithm Approach

Use Kahn’s Algorithm with a min-heap (priority queue) to enforce the deterministic ordering.

Graph Construction: Build an adjacency list and an in-degree count for each node.
Initialization: Identify all nodes with in-degree 0 and push their ids into a min-heap.
Processing Loop:

Extract the smallest id from the heap.
Append it to the result list.
For each neighbor of this node, decrement its in-degree.
If a neighbor’s in-degree becomes 0, push it into the heap.

Cycle Detection: After the loop, if the length of the result list is less than the total number of calls, return "CYCLE". Otherwise, return the result list.

The use of a min-heap ensures that at every step, the smallest available id is processed first, satisfying the tie-breaking requirement.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results