layer_sort.py

#!/usr/bin/env python3
import sys


def add_layer(last_layer, fulfilled, dependencies, parents):
    layer = set()
    for item in last_layer:
        if item not in parents:
            # Current item is a stub
            continue

        # Check for new dependencies that might have come free
        children = parents[item]

        for child in children:
            # Check if all dependencies are fulfilled
            if dependencies[child] <= fulfilled:
                layer.add(child)

    return layer


dependencies = dict()
parents = dict()
entities = set()
tree = dict()

for line in sys.stdin:
    items = line.strip().split(' ')

    entity = items[0].strip()

    if entity == '':
        continue

    entities.add(entity)

    if len(items) == 1:
        continue

    dep = items[1].strip()

    if dep == '':
        continue

    entities.add(dep)

    # Make a symmetric dictionary of what depends on what
    # And what needs what
    if dep not in dependencies:
        dependencies[dep] = set()

    dependencies[dep].add(entity)

    if entity not in parents:
        parents[entity] = set()

    parents[entity].add(dep)

# Get all items without dependencies
top = dependencies.keys() ^ entities
layers = [top]
fulfilled = set(top)

prev_layer = top

while True:
    next_layer = add_layer(prev_layer, fulfilled, dependencies, parents)

    if len(next_layer) == 0:
        break

    fulfilled |= next_layer
    layers.append(next_layer)
    prev_layer = next_layer

for layer in layers:
    print(' | '.join(layer))