adapted from mypy mypybuild py under the mit license compute strongly connected components of a directed graph args vertices the labels for the vertices edges for each vertex gives the target vertices of its outgoing edges returns an iterator yielding strongly connected components each represented as a set of vertices each input vertex will occur exactly once vertices not part of a scc are returned as singleton sets from http code activestate comrecipes578507 topological sort args data a map from sccs represented as frozen sets of strings to sets of sccs its dependencies note this data structure is modified in place for normalization purposes selfdependencies are removed and entries representing orphans are added returns an iterator yielding sets of sccs that have an equivalent ordering note the algorithm doesn t care about the internal structure of sccs example suppose the input has the following structure a b c b d c d this is normalized to a b c b d c d d the algorithm will yield the following values d b c a from http code activestate comrecipes577413 todo use a faster algorithm find cycles in scc emanating from start yields lists of the form a b c a which means there s a path from a b c a the first item is always the start argument but the last item may be another element e g a b c b means there s a path from a to b and there s a cycle from b to c and back basic input checks reduce the graph to nodes in the scc recursive helper that yields cycles adapted from mypy mypy build py under the mit license compute strongly connected components of a directed graph args vertices the labels for the vertices edges for each vertex gives the target vertices of its outgoing edges returns an iterator yielding strongly connected components each represented as a set of vertices each input vertex will occur exactly once vertices not part of a scc are returned as singleton sets from http code activestate com recipes 578507 topological sort args data a map from sccs represented as frozen sets of strings to sets of sccs its dependencies note this data structure is modified in place for normalization purposes self dependencies are removed and entries representing orphans are added returns an iterator yielding sets of sccs that have an equivalent ordering note the algorithm doesn t care about the internal structure of sccs example suppose the input has the following structure a b c b d c d this is normalized to a b c b d c d d the algorithm will yield the following values d b c a from http code activestate com recipes 577413 todo use a faster algorithm ignore self dependencies find cycles in scc emanating from start yields lists of the form a b c a which means there s a path from a b c a the first item is always the start argument but the last item may be another element e g a b c b means there s a path from a to b and there s a cycle from b to c and back basic input checks reduce the graph to nodes in the scc recursive helper that yields cycles todo make this not quadratic
from typing import *


def strongly_connected_components(
    vertices: AbstractSet[str], edges: Dict[str, AbstractSet[str]]
) -> Iterator[AbstractSet[str]]:
    
    identified: Set[str] = set()
    stack: List[str] = []
    index: Dict[str, int] = {}
    boundaries: List[int] = []

    def dfs(v: str) -> Iterator[Set[str]]:
        index[v] = len(stack)
        stack.append(v)
        boundaries.append(index[v])

        for w in edges[v]:
            if w not in index:
                yield from dfs(w)
            elif w not in identified:
                while index[w] < boundaries[-1]:
                    boundaries.pop()

        if boundaries[-1] == index[v]:
            boundaries.pop()
            scc = set(stack[index[v] :])
            del stack[index[v] :]
            identified.update(scc)
            yield scc

    for v in vertices:
        if v not in index:
            yield from dfs(v)


def topsort(
    data: Dict[AbstractSet[str], Set[AbstractSet[str]]]
) -> Iterable[AbstractSet[AbstractSet[str]]]:
    
    
    for k, v in data.items():
        v.discard(k)  
    for item in set.union(*data.values()) - set(data.keys()):
        data[item] = set()
    while True:
        ready = {item for item, dep in data.items() if not dep}
        if not ready:
            break
        yield ready
        data = {item: (dep - ready) for item, dep in data.items() if item not in ready}
    assert not data, "A cyclic dependency exists amongst %r" % data


def find_cycles_in_scc(
    graph: Dict[str, AbstractSet[str]], scc: AbstractSet[str], start: str
) -> Iterable[List[str]]:
    
    
    assert start in scc, (start, scc)
    assert scc <= graph.keys(), scc - graph.keys()

    
    graph = {src: {dst for dst in dsts if dst in scc} for src, dsts in graph.items() if src in scc}
    assert start in graph

    
    def dfs(node: str, path: List[str]) -> Iterator[List[str]]:
        if node in path:
            yield path + [node]
            return
        path = path + [node]  
        for child in graph[node]:
            yield from dfs(child, path)

    yield from dfs(start, [])