Topological sort returns an ordered list of blocks.
    Sorting guarantee is that if block A is upstream of block B, block A will come before block B in the sorted list.
    Sorting is implemented by first building a shadow copy of the graph and then removing items from the shadow graph
    one by one as we find items without predecessors.
    See Knuth volume 1, 2.2.3 (p. 265 in the third edition).

    For most graph topologies and data sets in this framework, we don't actually need to guarantee any particular
    ordering. But for some (e.g. test_one_time_output_with_intermediaries), it was difficult to figure out how to
    make it work (and continue to have other graphs work) without such a guarantee.

def topological_sort(channels):
    """
    Topological sort returns an ordered list of blocks.
    Sorting guarantee is that if block A is upstream of block B, block A will come before block B in the sorted list.
    Sorting is implemented by first building a shadow copy of the graph and then removing items from the shadow graph
    one by one as we find items without predecessors.
    See Knuth volume 1, 2.2.3 (p. 265 in the third edition).

    For most graph topologies and data sets in this framework, we don't actually need to guarantee any particular
    ordering. But for some (e.g. test_one_time_output_with_intermediaries), it was difficult to figure out how to
    make it work (and continue to have other graphs work) without such a guarantee.
    """
    sorted_shadow_blocks = []
    block_table = {}
    shadow_table = {}
    blocks_without_predecessors = set()
    graph_heads = []

    # Create shadow version of the graph. This makes it easier to implement an algorithm that removes nodes from the
    # graph as it goes.
    for channel in channels:
        source = channel.producer
        shadow_source = get_shadow_node(block_table, shadow_table, source)
        if source.has_no_inputs():
            blocks_without_predecessors.add(shadow_source)
            graph_heads.append(source)

        for destination in channel.consumers:
            shadow_destination = get_shadow_node(block_table, shadow_table, destination)
            shadow_source.outputs.append(shadow_destination)
            shadow_destination.inputs.append(shadow_source)

    # Walk through the graph by selecting and removing all blocks without predecessors and potentially adding any of
    # their successors that have no predecessors in the graph that is newly created by the removal.
    while blocks_without_predecessors:
        shadow_block = blocks_without_predecessors.pop()
        sorted_shadow_blocks.append(shadow_block)
        for shadow_destination in shadow_block.outputs:
            shadow_destination.inputs.remove(shadow_block)
            if not shadow_destination.inputs:
                blocks_without_predecessors.add(shadow_destination)

    sorted_blocks = [block_table[x] for x in sorted_shadow_blocks]
    return sorted_blocks, graph_heads