Python 基于属性的有序列表

Question

我有以下对象列表，我想根据依赖关系对它们进行排序。首先，没有依赖关系的对象将首先添加到列表中，然后是与添加的第一个批处理有依赖关系的批处理，依此类推，直到所有项目都从列表中删除。

pp = [
    {"name": 'pipeline13', "deps": 'pipeline11' },
    {"name": 'pipeline1', "deps": 'pipeline4' },
    {"name": 'pipeline4'},
    {"name": 'pipeline2', "deps": 'pipeline4'},
    {"name": 'pipeline3'}, 
    {"name": 'pipeline5'},
    {"name": 'pipeline6', "deps": 'pipeline2'},
    {"name": 'pipeline7'},
    {"name": 'pipeline8', "deps": 'pipeline2'},
    {"name": 'pipeline9', "deps": 'pipeline3'},
    {"name": 'pipeline10', "deps": 'pipeline1' },
    {"name": 'pipeline11', "deps": 'pipeline10' }
]

目前，我有下面的代码可以工作，但它不可扩展，也不太Pythonic。

output = []
output_stage_1 = []
output_stage_2 = []
output_stage_3 = []
output_stage_4 = []
output_stage_5 = []


while pp:
    for p in pp:
        if not p.get('deps'):
            output.append(p)
            pp.remove(p)


        if p.get('deps') in [i.get('name') for i in output]:
            output_stage_1.append(p)
            pp.remove(p)


        if p.get('deps') in [i.get('name') for i in output_stage_1]:
            output_stage_2.append(p)
            pp.remove(p)


        if p.get('deps') in [i.get('name') for i in output_stage_2]:
            output_stage_3.append(p)
            pp.remove(p)


        if p.get('deps') in [i.get('name') for i in output_stage_3]:
            output_stage_4.append(p)
            pp.remove(p)


        if p.get('deps') in [i.get('name') for i in output_stage_4]:
            output_stage_5.append(p)
            pp.remove(p)



print(output + output_stage_1 + output_stage_2 + output_stage_3 + output_stage_4 + output_stage_5)

Answer 1

I want to sort into order based on dependencies

这称为topological sorting .

以下是一些资源，可以向您展示如何执行此操作或为您完成工作:

• https://www.geeksforgeeks.org/python-program-for-topological-sorting/
• https://pypi.org/project/toposort/