# Class DependencyGraphSearch

java.lang.Object
com.google.adk.planner.goap.DependencyGraphSearch

public final class DependencyGraphSearch extends Object
Performs a topological search on the dependency graph to find the ordered list of agents that must execute to produce a goal output, given a set of initial preconditions (state keys already available).

The search works backward from the goal: for each unsatisfied dependency, it finds the agent that produces it and recursively resolves that agent's dependencies. Uses recursive DFS to ensure correct topological ordering.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `static com.google.common.collect.ImmutableList<String>`
  `search(GoalOrientedSearchGraph graph, Collection<String> preconditions, String goal)`
  Finds the ordered list of agent names that must execute to produce the goal.
  `static com.google.common.collect.ImmutableList<com.google.common.collect.ImmutableList<String>>`
  `searchGrouped(GoalOrientedSearchGraph graph, List<AgentMetadata> metadata, Collection<String> preconditions, String goal)`
  Groups agents into parallelizable execution levels.

  ### Methods inherited from class Object

  `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- ## Method Details

  - ### search

    public static com.google.common.collect.ImmutableList<String> search(GoalOrientedSearchGraph graph, Collection<String> preconditions, String goal)
    Finds the ordered list of agent names that must execute to produce the goal.
    Parameters:
      `graph` - the dependency graph built from agent metadata
      `preconditions` - state keys already available (no agent needed to produce them)
      `goal` - the target output key to produce
    Returns:
      ordered list of agent names, from first to execute to last
    Throws:
      `IllegalStateException` - if a dependency cannot be resolved or a cycle is detected

  - ### searchGrouped

    public static com.google.common.collect.ImmutableList<com.google.common.collect.ImmutableList<String>> searchGrouped(GoalOrientedSearchGraph graph, List<AgentMetadata> metadata, Collection<String> preconditions, String goal)
    Groups agents into parallelizable execution levels.

    Each group contains agents whose dependencies are all satisfied by agents in earlier groups or by initial preconditions. Agents within the same group are independent and can run in parallel.

    Parameters:
      `graph` - the dependency graph
      `metadata` - agent metadata used to compute dependency levels
      `preconditions` - state keys already available
      `goal` - the target output key
    Returns:
      ordered list of agent groups; agents within each group can run in parallel
    Throws:
      `IllegalStateException` - if a dependency cannot be resolved or a cycle is detected