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 each vertex u such that there is a path from v to u and u to v.
Example input/output:
Input: `graph`
sourcetarget
`a``b`
`b``b`
`b``c`
`c``b`
`c``a`
`a``d`
Input: `query`
source
`c`
Output: `[a, b, c]`

### Python - Imperative

```def scc(graph, query):
reachable = set()
vertices = set()
for edge in graph:
changed = True
while changed:
changed = False
for edge in graph:
for vertex in vertices:
if ((edge["source"], vertex) not in reachable
and (edge["target"], vertex) in reachable):
changed = True
source = query["source"]
result = []
for vertex in vertices:
if ((source, vertex) in reachable and
(vertex, source) in reachable):
result.append(vertex)
return result```

### Python - Functional

```def scc(graph, query):
def step(relation):
return set([
(source, edge["target"])
for (source, target) in relation
for edge in graph
if target == edge["source"]
]).union(relation)

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

source = query["source"]
init = set([(edge["source"], edge["target"]) for edge in graph])
reachable = fix(step, init)
return list(set([v for (_, v) in reachable
if (v, source) in reachable and (source, v) in reachable]))```

### SQL - SQLite

```WITH RECURSIVE
closure(source, target) AS (
SELECT DISTINCT source, target FROM graph
UNION
SELECT edge.source, path.target
FROM closure as path JOIN graph as edge
ON edge.target = path.source
),
component(v1, v2) AS (
SELECT path.source, path.target
FROM closure as path JOIN closure as path_
ON path.source = path_.target AND path.target = path_.source
)
SELECT S.v2 FROM component as S
JOIN query ON S.v1 = query.source```

### Datalog - Souffle

```.decl scc1(x: symbol, y: symbol)
scc1(x, x) :- vertex(x).
scc1(x, y) :- path(x, y), path(y, x).
.decl path(x: symbol, y: symbol)
path(x, y) :- graph(x, y).
path(x,y) :- graph(x, z), path(z, y).
.decl vertex(x: symbol)
vertex(x)  :- graph(x, _).
vertex(x)  :- graph(_, x).
scc(x) :- query(src), scc1(src, x).```