# Graph Built-ins

| Function | Description | Meta |
| --- | --- | --- |
| `graph.reachable` | `output := graph.reachable(graph, initial)`  Computes the set of reachable nodes in the graph from a set of starting nodes.  **Arguments:**  `graph` (object\[any: any<array\[any\], set\[any\]>\])  object containing a set or array of neighboring vertices  `initial` (any<array\[any\], set\[any\]>)  set or array of root vertices  **Returns:**  `output` (set\[any\])  set of vertices reachable from the `initial` vertices in the directed `graph` | [v0.20.0](https://github.com/open-policy-agent/opa/releases/v0.20.0) Wasm |
| `graph.reachable_paths` | `output := graph.reachable_paths(graph, initial)`  Computes the set of reachable paths in the graph from a set of starting nodes.  **Arguments:**  `graph` (object\[any: any<array\[any\], set\[any\]>\])  object containing a set or array of root vertices  `initial` (any<array\[any\], set\[any\]>)  initial paths  **Returns:**  `output` (set\[array\[any\]\])  paths reachable from the `initial` vertices in the directed `graph` | [v0.37.0](https://github.com/open-policy-agent/opa/releases/v0.37.0) SDK-dependent |
| `walk` | `walk(x, output)`  Generates `[path, value]` tuples for all nested documents of `x` (recursively). Queries can use `walk` to traverse documents nested under `x`.  **Arguments:**  `x` (any)  value to walk  **Returns:**  `output` (array<array\[any\], any>)  pairs of `path` and `value`: `path` is an array representing the pointer to `value` in `x`. If `path` is assigned a wildcard (`_`), the `walk` function will skip path creation entirely for faster evaluation. | Wasm |

Graph Reachable

A common class of recursive rules can be reduced to a graph reachability problem, so `graph.reachable` is useful for more than just graph analysis. This usually requires some pre- and postprocessing. The following example shows you how to "flatten" a hierarchy of access permissions.

data.json

```
{}
```

input.json

```
{}
```

```
package graph_reachable_exampleorg_chart_data := {        "ceo": {},        "human_resources": {"owner": "ceo", "access": ["salaries", "complaints"]},        "staffing": {"owner": "human_resources", "access": ["interviews"]},        "internships": {"owner": "staffing", "access": ["blog"]},}org_chart_graph[entity_name] := edges if {        org_chart_data[entity_name]        edges := {neighbor | org_chart_data[neighbor].owner == entity_name}}org_chart_permissions[entity_name] := access if {        org_chart_data[entity_name]        reachable := graph.reachable(org_chart_graph, {entity_name})        access := {item | reachable[k]; item := org_chart_data[k].access[_]}}result contains org_chart_permissions[entity_name]
```

Output

\[
  \[
    "blog"
  \],
  \[
    "blog",
    "complaints",
    "interviews",
    "salaries"
  \],
  \[
    "blog",
    "interviews"
  \]
\]

Graph Reachable Paths

It may be useful to find all reachable paths from a root element. `graph.reachable_paths` can be used for this. Note that cyclical paths will terminate on the repeated node. If an element references a nonexistent element, the path will be terminated, and excludes the nonexistent node.

data.json

```
{}
```

input.json

```
{}
```

```
package graph_reachable_paths_examplepath_data := {        "aTop": [],        "cMiddle": ["aTop"],        "bBottom": ["cMiddle"],        "dIgnored": [],}all_paths[root] := paths if {        path_data[root]        paths := graph.reachable_paths(path_data, {root})}result contains all_paths[entity_name]
```

Output

\[
  \[
    \[
      "aTop"
    \]
  \],
  \[
    \[
      "bBottom",
      "cMiddle",
      "aTop"
    \]
  \],
  \[
    \[
      "cMiddle",
      "aTop"
    \]
  \],
  \[
    \[
      "dIgnored"
    \]
  \]
\]