Skip to content

Instantly share code, notes, and snippets.

@the-eater
Created March 20, 2019 11:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save the-eater/5f2ead11817579046908a76b4aecc4a3 to your computer and use it in GitHub Desktop.
Save the-eater/5f2ead11817579046908a76b4aecc4a3 to your computer and use it in GitHub Desktop.
#!/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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment