detours.py

#!/usr/bin/env python3

def build_rgraph(graph):
    rgraph = {k: set() for k in graph.keys()}
    for u in graph.keys():
        for v in graph[u]:
            rgraph[v].add(u)
    return rgraph

def dfs(graph, seen, val, start):
    stack = [start]

    while stack:
        v = stack.pop()
        if v in seen: continue
        seen[v] = val
        stack.extend(graph[v])

    return seen

def detours_search(graph, rgraph, path):
    ti = {}
    for i in range(len(path)):
        dfs(rgraph, ti, i, path[i])

    fi = {}
    for i in reversed(range(len(path))):
        dfs(graph, fi, i, path[i])

    nobes = set()
    for u in graph.keys():
        if u in ti and u in fi and ti[u] <= fi[u]:
            nobes.add(u)

    return nobes

def detours(graph, path):
    return detours_search(graph, build_rgraph(graph), path)

####

test_graph = {
    'a': {'b'},
    'b': {'c', 'f'},
    'c': {'d'},
    'd': {'e'},
    'e': set(),
    'f': {'g'},
    'g': {'d', 'h'},
    'h': {'f', 'i'},
    'i': {'h'}
}
test_path = "abfgde"