Generate a Semantic Dependency Graph from Tool Schemas

Problem Statement

Modern workflow automation agents rely on tool catalogs where the output of one tool can satisfy the input requirements of another. Given a list of tool specifications with simplified JSON schemas for inputs and outputs, build a dependency graph generator.

Each tool is defined as follows:

• name: A unique identifier string for the tool.
• inputs: A dictionary where each key is a parameter name and the value is an object {"type": str, "required": bool}.
• outputs: A dictionary where each key is a property path and the value is an object {"type": str}.

Two fields match if and only if:

1. Semantic Field Match: Their canonical field names match. The canonical form of a field name is obtained by taking the leaf property name (after the last . if dot-notated), removing all underscores (_) and hyphens (-), and converting to lowercase. For example, payload.user_id and userId both canonicalize to userid.
2. Type Compatibility: The output field's type must be identical to the input field's type.

A directed dependency exists from Tool A to Tool B if Tool A can provide at least one input field for Tool B (A != B).

Write a function generate_dependency_graph(tools: list[dict]) -> dict that returns:

• "edges": A list of unique directed connections formatted as {"from_tool": str, "to_tool": str, "matches": [{"output_field": str, "input_field": str}]}. Sort edges alphabetically by from_tool, then to_tool. Sort matches within an edge by input_field.
• "unresolved_inputs": A dictionary mapping each tool name to a sorted list of its required input field names that cannot be satisfied by any other tool in the catalog.

Example

tools = [
    {
        "name": "getUser",
        "inputs": {"username": {"type": "string", "required": True}},
        "outputs": {"data.user_id": {"type": "integer"}, "email": {"type": "string"}}
    },
    {
        "name": "sendEmail",
        "inputs": {
            "email_address": {"type": "string", "required": True},
            "userId": {"type": "integer", "required": False}
        },
        "outputs": {"status": {"type": "string"}}
    }
]

# Canonical names:
# getUser outputs: data.user_id -> 'userid', email -> 'email'
# sendEmail inputs: email_address -> 'emailaddress', userId -> 'userid'
# Match: getUser.data.user_id (integer) -> sendEmail.userId (integer)

Output:

{
  "edges": [
    {
      "from_tool": "getUser",
      "to_tool": "sendEmail",
      "matches": [
        {"output_field": "data.user_id", "input_field": "userId"}
      ]
    }
  ],
  "unresolved_inputs": {
    "getUser": ["username"],
    "sendEmail": ["email_address"]
  }
}

Constraints

• 1 <= len(tools) <= 200
• Each tool has at most 50 input fields and 50 output fields.
• Field types are limited to "string", "integer", "boolean", and "number".
• A tool cannot depend on itself.