Graphs

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 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 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_example

org_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]

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_example

path_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]