ลำดับการเรียงลำดับ/กราฟของรายการวัตถุที่ขึ้นอยู่กับแต่ละอื่นๆ [ซ้ำกัน]

ฉันมีคลาสเช่น Foo ด้านล่างซึ่งมีแอตทริบิวต์ "depends_on" ซึ่งเป็นอาร์เรย์ของอินสแตนซ์ Foo อื่นๆ ฉันต้องการที่จะนำรายการ Foos และเรียงลำดับโดยที่ foo ซึ่งขึ้นอยู่กับ foo อื่นนั้นยิ่งใหญ่กว่านั้น เช่น ถ้า foo b ขึ้นอยู่กับ foo a อาร์เรย์ควรอยู่ในลำดับ [a,b] ฉันคิดว่ามันจะดีกว่าถ้าให้ foo แต่ละฟิลด์ order และเรียงลำดับในฟิลด์นั้นแทนที่จะใช้ __lt__

class Foo(object):
    def __init__(self, name, depends_on=[]):
        self.order = 0
        self.name = name
        self.depends_on = depends_on

a = Foo('a')
b = Foo('b', [a])
c = Foo('c', [b])
d = Foo('d')
e = Foo('e')
f = Foo('f', [e])
g = Foo('g', [f, b])

foos = [a,b,c,d,e,f,g]

ฉันได้สร้างฟังก์ชันแบบเรียกซ้ำที่คล้ายกันนี้และดูเหมือนว่าจะใช้งานได้ แต่ฉันคิดว่ามีวิธีที่ดีกว่า

ในช่วงแรก ฉันจะเปรียบเทียบทุกอ็อบเจ็กต์ในอาร์เรย์ด้วยกัน หากวัตถุ x ขึ้นอยู่กับวัตถุ y ฉันจะเพิ่มฟิลด์ order ของวัตถุ x ทีละหนึ่ง

ในการผ่านครั้งที่สอง ฉันเปรียบเทียบเฉพาะ foos กับ order มากกว่าหรือเท่ากับ 1; กล่าวคือ foos ที่ขึ้นอยู่กับ foo อื่นอย่างน้อยหนึ่งตัว อีกครั้ง ฉันจะเพิ่มฟิลด์ order ของชุดย่อยของ foos นี้ หากพวกมันขึ้นอยู่กับกันและกัน

ฉันทำรูปแบบนี้ต่อไปจนกว่าจะไม่มีการเปรียบเทียบอีกต่อไป

def recursive_order(order=0):
    compared = 0
    for fooa in [foo for foo in foos if foo.order >= order]:
        for foob in [foo for foo in foos if foo.order >= order]:
            compared += 1
            if fooa in foob.depends_on:
                foob.order += 1
    if compared == 0:
        return
    recursive_order(order + 1)

recursive_order()
foos.sort(key=lambda foo: foo.order)
print [(foo.name, foo.order) for foo in foos]

[('a', 0), ('d', 0), ('e', 0), ('b', 1), ('f', 1), ('c', 2), ('g', 2)]

ฉันต้องการรายการ foo ที่คำนึงถึง "ลำดับการพึ่งพา" เช่น foo a และ foo b ไม่มีการขึ้นต่อกันจึงเท่ากัน Foo b ขึ้นอยู่กับ Foo a ดังนั้น foo a ‹ foo b ([a,b] Foo c ขึ้นอยู่กับ Foo b ดังนั้น [a,b,c]

แก้ไข

ขอบคุณ Martijn Pieters สำหรับลิงก์ไปยังการเรียงลำดับทอพอโลยี นี่คือการใช้งานของฉัน:

def topological_sort(foos):
    provided = set()
    while foos:
        remaining_foos = []
        emitted = False

        for foo in foos:
            if set(foo.depends_on).issubset(provided):
                yield foo
                provided.add(foo)
                emitted = True
            else:
                remaining_foos.append(foo)

        if not emitted:
            raise raise ValueError("cyclic dependency detected")

        foos = remaining_foos

print [foo.name for foo in topological_sort(foos)]

['e', 'd', 'a', 'f', 'b', 'g', 'c']