Strongly connected components algorithm
You iterate twice over the children in both branches. Avoid that by combining these lines

children = [child for child in getChildren(current) if child not in removed]
stack.extend((child, 0) for child in children)


to

stack.extend((child, 0) for child in getChildren(current) if child not in removed)


and these

children = [child for child in getChildren(current) if child not in removed]
for child in children:


to 

for child in getChildren(current):
    if child not in removed:






Instead of looping in Python and moving one item at a time here

    scc = []
    while not scc or scc[-1] != current:
        scc.append(subtree.pop())
    sccs.append(tuple(scc))


try to use slicing like this. A possible disadvantage is that index searches from the beginning.

    i = subtree.index(current)
    scc = tuple(reversed(subtree[i:]))
    del subtree[i:]
    sccs.append(scc)

Use local variables to reduce dictionary lookups. You can also bind methods such as stack.pop to local variables to avoid attribute lookup inside the loop.
Also to reduce dictionary lookups, you could combine index and lowlink dictionaries. Put the pair of values in as a tuple or a list to take advantage of unpacking into local variables:

next_index = next(indexCounter)
index[current] = [next_index, next_index]
...
index_current, lowlink_current = index[current]