Specification: A path is a sequence of edges such that the target of each edge is the source of the next. Given a graph and a vertex v, list the vertices reachable by a path from v.
Example input/output:
Input:
graph| source | target |
|---|---|
a | b |
b | b |
b | c |
c | f |
c | b |
a | d |
e | a |
Input:
query| source |
|---|
a |
Output:
[a, b, c, d, f]Python - Imperative
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)
Python - Functional
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])))
SQL - SQLite
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
Datalog - Souffle
.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).
Q - kdb+
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]