Expressiveness Benchmark

def reachable(graph, query):
  adjacency_list = defaultdict(list)
  for edge in graph:
    adjacency_list[edge["source"]].append(edge["target"])
  source = query[0]["source"]

  visited = set()
  to_visit = set([source])
    
  while len(to_visit) > 0:
    current = to_visit.pop()
    if current in visited:
      continue
    for neighbor in adjacency_list[current]:
      to_visit.add(neighbor)
    visited.add(current)
            
  return list(visited)

def reachable(graph, query):
  def step(visited):
    frontier = set([
      edge["target"]
      for vertex in visited
      for edge in graph
      if vertex == edge["source"]
    ])
    return frontier.union(visited)

  def fix(f, x):
    next = f(x)
    return x if next == x else fix(f, next)

  source = query[0]["source"]
  return list(fix(step, set([source])))

WITH RECURSIVE
closure(source, target) AS (
  SELECT source, source FROM graph
  UNION
  SELECT source, target FROM graph
  UNION
  SELECT edge.source, path.target
  FROM closure as path JOIN graph as edge
  ON edge.target = path.source
)
SELECT S.target FROM closure as S
JOIN query ON S.source = query.source

.decl path(x: symbol, y: symbol)
path(x, y) :- graph(x, y).
path(x, y) :- graph(x, z), path(z, y).
reachable(source) :- query(source).
reachable(x) :- query(source), path(source, x).

graph: (first') each graph;
nodes: asc distinct graph[`source], graph[`target];
adj_list: `source xgroup graph;
adj_matrix: 
  {in[;x] each nodes} each nodes ,' (adj_list each nodes) `target;
iterated_matrix: last ({x | any each (x *\: x)} \) adj_matrix;
query_idx: nodes ? (first first query[`source]);
reachable: nodes where iterated_matrix[query_idx]